algorithm - manhattan - Búsqueda bidireccional A*(A-star)

que es la búsqueda a-estrella(a*)

Question

Estoy implementando una búsqueda A * bidireccional (la búsqueda bidireccional se realiza tanto desde el origen como desde el destino simultáneamente, y cuando estas dos búsquedas se encuentren, tendré mi camino más corto, al menos con un poco de lógica adicional) ).

¿Alguien tiene alguna experiencia en tomar un A * unidireccional y bidireccional (?) ¿Qué tipo de ganancia de rendimiento puedo esperar? Me di cuenta de que más o menos la mitad del tiempo de búsqueda, como mínimo, ¿pero puedo ver mayores ganancias que esto? Estoy usando el algoritmo para determinar las rutas más cortas en una red de carreteras, si eso es de alguna manera relevante (he leído sobre el algoritmo "Alcance" de MS, pero quiero dar pequeños pasos hacia esto en lugar de saltar directamente).

Answer 1

En el mejor de los casos posible, se ejecutaría en O (b ^ (n / 2)) en lugar de O (b ^ n), pero solo si tienes suerte :)

(donde b es su factor de ramificación yn es el número de nodos que consideraría un A * unidireccional)

Todo depende de la facilidad con la que se encuentren las dos búsquedas, si se encuentran entre sí en un buen punto medio al comienzo de la búsqueda, se eliminó una gran cantidad de tiempo de búsqueda, pero si se ramifican en direcciones totalmente diferentes, puede terminar con algo más lento que el simple A * (debido a toda la contabilidad adicional)

Answer 2

Es posible que desee probar http://sourceforge.net/projects/tway/ hay un script de evaluación comparativa que lo compara con el estándar astar (para los datos de carreteras de la ciudad de Nueva York parece que ofrece un beneficio de tiempo del 30%)

Answer 3

Puede considerar la agrupación como un refuerzo mucho más eficiente. También vea este artículo

Answer 4

Se han implementado 3 algos de búsqueda A * bidireccionales diferentes (ver cskit ).

• net.coderodde.cskit.graph.p2psp.general.FastSuboptimalFinder es el más rápido, pero en general no es óptimo;
• net.coderodde.cskit.graph.p2psp.general.BHPAFinder es óptimo y bastante rápido; si la optimalidad es un requisito, usaría este;
• net.coderodde.cskit.graph.p2psp.general.WhangboFinder no es particularmente bueno.

Para ver los algoritmos en acción, desde la raíz del proyecto escriba mvn exec:java (requiere Maven). ¡Buena suerte!

( Editar : esta biblioteca proporciona 3 algoritmos A * bidireccionales diferentes. Los tres son óptimos.)