Est-ce que A* est vraiment meilleur que Dijkstra dans la recherche de chemin dans le monde réel?
je développe un programme de recherche de chemin. On dit théoriquement que A* est meilleur que Dijkstra. En fait, ce dernier est un cas particulier de l'ancien. Cependant, lors de tests dans le monde réel, je commence à douter que c'est Un* vraiment mieux?
j'ai utilisé les données de la Ville de New York, à partir de 9 DIMACS de mise en Œuvre de Défi - plus courts Chemins, dans laquelle la latitude et la longitude de chaque nœud sont indiquées.
lors de l'application d'un*, je dois calculer le distance sphérique entre deux points, en utilisant Formule Haversine, qui implique le péché, cos, arcsin, racine carrée. Tous ceux qui sont très très chronophage.
Le résultat est le suivant:
en utilisant Dijkstra: 39.953 ms, agrandi 256540 noeuds.
en utilisant un*, 108.475 ms, agrandi 255135 noeuds.
remarquant que dans A*, Nous avons augmenté moins de 1405 noeuds. Cependant, le temps de calculer un heuristique est beaucoup plus que cela économisé.
à mon comprendre, la raison est que dans un très grand graphe réel, le poids de l'heuristique sera très faible, et l'effet de celui-ci peut être ignoré, alors que le temps de calcul est dominant.
5 réponses
je pense que vous êtes plus ou moins à côté de la question d'Un*. Il est destiné à être un algorithme très performant, en partie en faisant intentionnellement plus de travail, mais avec heuristique bon marché, et vous êtes en quelque sorte de déchirer que de bits en le surchargeant avec un lourd heuristique de prédiction extrêmement précise.
pour la sélection des noeuds dans un*, vous devez juste utiliser une approximation de la distance. Il suffit d'utiliser (latdiff^2)+(lngdiff^2) comme distance approximative pour rendre votre algorithme beaucoup plus performante que Dijkstra, et ne donne pas de résultats bien pires dans n'importe quel scénario du monde réel. En fait, les résultats devraient être exactement les mêmes si vous calculez la distance parcourue sur un noeud correctement avec L'Haversine. Il suffit d'utiliser un algorithme bon marché pour sélectionner la prochaine traversée potentielle.
A* peut être réduit à Dijkstra en définissant quelques paramètres triviaux. Il y a trois façons possibles de ne pas améliorer Dijkstra:
- L'heuristique utilisée est incorrecte: il n'est pas un soi-disant recevable heuristique.
A*devrait utiliser un heuristique qui ne surestime pas la distance à l'objectif dans le cadre de sa fonction de coût. - L'heuristique est trop cher pour calculer.
- la structure des graphes du monde réel est spéciale.
dans ce dernier cas, vous devriez essayer de construire sur la recherche existante, par exemple "l'Autoroute de la Dimension, plus courts Chemins, et Prouvable Algorithmes Efficaces" par Abraham et al.
tout autre chose dans l'univers, il y a un compromis. Vous pouvez prendre l'algorithme de dijkstra à précisément calculez l'heuristique, mais cela irait à l'encontre du but, n'est-ce pas?
A* est un grand algorithme en ce qu'il vous fait pencher vers le but ayant un geneal idée de quelle direction pour l'agrandir. Cela dit, vous devriez garder l'heuristique aussi simple que possible parce que tout ce que vous avez besoin est un général direction.
en fait, des calculs géométriques plus précis qui ne sont pas basés sur les données réelles ne vous donnent pas nécessairement une meilleure direction. Aussi longtemps qu'elles ne sont pas basées sur les données, toutes ces heuristiques vous donnent juste une direction qui sont toutes également (in)correctes.
en général A* est plus performant que Dijkstra mais cela dépend vraiment de la fonction heuristique que vous utilisez dans a*. Vous voulez un h (n) qui est optimiste et trouve le chemin le plus bas coût, h(N) devrait être moins que le coût réel. Si h (n) >= coût, alors vous finirez dans une situation comme celle que vous avez décrite.
pouvez-vous afficher votre fonction heuristique?
Également garder à l'esprit que les performances de ces algorithmes dépend fortement de la nature du graphe, qui est étroitement liée à la précision de l'heuristique.
si vous comparez Dijkstra vs A* lors de la navigation hors d'un labyrinthe où chaque passage correspond à un seul bord de graphe, il y a probablement très peu de différence dans la performance. D'autre part, si le graphe a beaucoup d'arêtes entre "loin de" nœuds, la différence peut être assez spectaculaire. Pensez à un robot (ou un AI-caractère de jeu d'ordinateur contrôlé) naviguant dans le terrain presque ouvert avec quelques obstacles.
mon point est que, même si L'ensemble de données de New York que vous avez utilisé est certainement un bon exemple de "graphe du monde réel", il n'est pas représentatif de tous les problèmes de chemin du monde réel.