Bidirectionnel A * (A-star) Recherche

Question

J'implémente une recherche bidirectionnelle A * (bidirectionnelle car la recherche est effectuée à la fois à partir de l'origine et de la destination, et quand ces deux recherches se rencontrent, je vais avoir ma plus courte chemin - au moins avec un peu de logique supplémentaire jeté).

Quelqu'un a-t-il de l'expérience avec un A * unidirectionnel et un bidirectionnel (!), Quel genre de gain de performance puis-je espérer obtenir? Je comptais sur cela plus ou moins réduire de moitié le temps de recherche, au minimum - mais puis-je voir des gains plus importants? J'utilise l'algorithme pour déterminer les routes les plus courtes sur un réseau routier - si cela est pertinent (j'ai lu à propos de l'algorithme "Reach" de MS, mais je veux faire des pas dans cette direction plutôt que de sauter tout droit).

Answer 1

Dans le meilleur des cas, il serait exécuté dans O (b^(n/2)) au lieu de O (b^n), mais c'est que si vous êtes chanceux :)

(où b est votre facteur de branchement et n est le nombre de nœuds qu'un A * unidirectionnel considérerait)

Tout dépend de la facilité avec laquelle les deux recherches se rencontrent, si elles se trouvent à mi-chemin au début de la recherche que vous avez vous avez fini avec beaucoup de temps de recherche, mais si elles se divisent en directions follement différentes, vous pouvez vous retrouver avec quelque chose de plus lent que le simple A * (à cause de toute la comptabilité supplémentaire)

Answer 2

ant d'essayer http://sourceforge.net/projects/tway/ il y a un script d'analyse comparative qui compare cela avec Astar norme (pour les routes de la ville de New York données, il semble donner un avantage de temps de 30%)

Answer 3

ont mis en œuvre 3 différents bidirectionnel A * recherche algos (voir cskit) .

• net.coderodde.cskit.graph.p2psp.general.FastSuboptimalFinder est le plus rapide, mais pas généralement optimal;
• net.coderodde.cskit.graph.p2psp.general.BHPAFinder est optimal et assez rapide; si l'optimalité est une exigence, j'utiliserais celle-ci;
• net.coderodde.cskit.graph.p2psp.general.WhangboFinder pas particulièrement bon.

Pour voir les algorithmes en action, à partir de la racine du projet, tapez mvn exec:java (nécessite Maven). Bonne chance!

(Modifier. This library propose 3 différents bidirectionnel A * algorithmes Tous les trois sont optimales.)

Answer 4

Vous pouvez envisager le regroupement d'appoint autant plus efficace. Voir aussi this article