BHFFA*: Un nuevo algoritmo admisible de búsqueda bidireccional

Abstract

A pesar de que inicialmente hubo un gran interés en los algoritmos de búsqueda bidireccionales, muy pronto se pensó que garantizar la optimalidad de las soluciones encontradas de este modo era muy complicado, y por ello se desestimó esta línea de investigación. En este artículo se muestra, sin embargo, que es posible superar los principales inconvenientes de la búsqueda bidireccional y desarrollar un nuevo algoritmo admisible, con una heurística consistente, y en términos muy sencillos. Además, a diferencia de otras implementaciones bidireccionales, la que se muestra aquí puede resultar en reducciones del tiempo necesario y de la memoria consumida de hasta el 99%, y siempre superior a su implementación unidireccional. Para constatarlo, se han estudiado dos dominios radicalmente diferentes: el grafo del Metro de Madrid y el juego del N-‘Puzle’.