Pourquoi un * plus rapide que Dijkstra

Question

Je sais que cette question a déjà été posée, mais il n'a pas répondu à ma question. Je comprends comment fonctionne l'Algorithme Dijkstra et l'algorithme A * et que A * est le cas général de Dijkstra.

On dit communément que A * trouve la solution plus rapide quel type de logique que vous utilisez une heuristique qui accélère le processus/réduit le facteur de ramification efficace.

Mais je me souviens bien, de faire un * retourner le résultat optimal, vous devez rechercher tous les nœuds qui ont des coûts qui sont inférieurs aux coûts de l'objectif. Ceci assure l'optimalité et aussi il est dit qu'il ne peut y avoir un algorithme qui soit plus rapide, parce que A * regarde tous les noeuds < = objectif-coûts que chaque algorithme au moins doit.

Mais qu'en est-Dijkstra? Il dépense également seulement les noeuds < = objectif-coûts car il élargit le chemin minimal possible à chaque étape.

Quelle est la bonne heuristique A * car si vous avez d'étendre les autres nœuds de toute façon à assurer optimalité? également les deux algorithmes semblent avoir la complexité d'exécution de n log n

quelqu'un L'espoir peut éclaircir ce :)

Answer 1

algorithme Dijkstra n'utilise pas une fonction Heuristique pour développer le nœud à la frontière, il ne cherche que le chemin qui minimise le coût pour atteindre un nœud non visité directement connecté aux nœuds déjà visités, il trouvera enfin le chemin le plus court, mais devra explorer tous les nœuds non directement connectés au puits. A * à l'aide d'une bonne fonction heuristique (doit être une heuristique admissible: ne jamais surestimer le coût pour atteindre le but) pourrait atteindre immédiatement le puits en étendant toujours le nœud droit à la frontière. Donc si g(n)=cost to reach node n et h(n)=an admissible heuristic function nous obtenons f(n)=g(n)+h(n) la fonction d'évaluation utilisée par A *. Au lieu de cela Dijkstra ne connaît que sa frontière et manque l'information heuristique, ainsi cela fonctionne aussi bien que A * quand l'heuristique est faible.