Bidireccional A * (A-star) Buscar

Question

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

¿Alguien tiene alguna experiencia con tomar un A * unidireccional y bidireccionalizarlo (!) - ¿qué tipo de ganancia de rendimiento puedo esperar? Había calculado, más o menos, reducir a la mitad el 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 de "Alcance" de MS, pero quiero dar pequeños pasos hacia esto en lugar de saltar directamente).

Answer 1

En el mejor de los casos es posible que hubiera corrido en O (b^(n/2)) en lugar de O (b^n), pero eso es sólo si tiene 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 cuán fácilmente se encuentren las dos búsquedas, si se encuentran en un buen punto intermedio al principio de la búsqueda que usted tiene eliminado un montón 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

Usted puede w hormiga para tratar http://sourceforge.net/projects/tway/ hay un script de benchmarking que compara esto con Astar estándar (por NY datos de carreteras de la ciudad parece dar una ventaja de tiempo de 30%)

Answer 3

han implementado 3 bidireccional diferente A * algos de búsqueda (ver cskit) .

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

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

(Editar:. This library proporciona 3 diferentes algoritmos bidireccional * A los tres son óptimas.)

Answer 4

Usted puede considerar como agrupación mucho más eficiente de refuerzo. También vea this article