Différence et avantages entre dijkstra et une étoile [dupliquer]

il est dit A* est plus rapide que l'utilisation de dijkstra et utilise best-first-search pour d'accélérer les choses.

A* est fondamentalement une variation informée de Dijkstra.

A* est considéré comme une "meilleure première recherche" parce qu'il choisit avidement quel vertex explorer ensuite, selon la valeur de f(v) [ f(v) = h(v) + g(v) ] - où h est le heuristique et g est le coût jusqu'à présent.

notez que si vous utilisez une fonction heuristique non informative: h(v) = 0 pour chaque v : vous obtenez que A* choisit le vertex à développer en fonction du" so far cost "( g(v) ) seulement, identique à L'algorithme de Dijkstra - donc si h(v) = 0 , A* par défaut à L'algorithme de Dijkstra.

si j'ai besoin de l'algorithme pour tourner en millisecondes, quand un * devient les plus éminents choix.

Not tout à fait, cela dépend de beaucoup de choses. Si vous avez une fonction heuristique de descente - de mon expérience personnelle, greedy best premier (En choisissant selon la fonction heuristique seul) - est généralement beaucoup plus rapide que A* (mais n'est même pas quasi optimale).

D'après ce que j'ai compris, il ne retourne pas nécessairement le meilleur résultat.

A* est à la fois complet (trouve un chemin s'il en existe un) et optimal (trouve toujours le chemin le plus court) si vous utilisez une fonction heuristique Admissible . Si votre fonction n'est pas recevable, tous les paris sont éteints.

Si j'ai besoin de résultats rapides, il est préférable de pré-calculer les chemins? Il peut prenez des mégaoctets d'espace pour les stocker.

il s'agit d'une optimisation courante faite sur certains problèmes, par exemple sur le 15-puzzle problème , mais il est plus avancé. Un chemin de le point A au point B est appelé Macro. Certains chemins sont très utiles et devraient être souvenu. Une composante D'apprentissage Machine est ajoutée à l'algorithme afin d'accélérer les choses en mémorisant ces Macros.

notez que le chemin du point A au point B ici n'est généralement pas sur le graphique des États - mais dans le problème lui-même (par exemple, comment déplacer un carré de la ligne inférieure à la ligne supérieure...)

pour accélérer les choses:

si vous avez un heuristique et vous le trouvez trop lent, et vous voulez une solution plus rapide, même si pas optimale - a* Epsilon est généralement plus rapide que A*, tout en vous donnant une limite sur l'optimalité du chemin (à quel point il est proche d'être optimal).

Dijkstra est un cas particulier pour A* (Lorsque l'heuristique est zéro).

* recherche:

il a deux fonctions de coût.

g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.

le coût total de chaque noeud est calculé par f (n)=g (n)+h (n)

Dijkstra:

il a une fonction de coût, qui est la valeur de coût réel de la source à chaque noeud: f (n)=g(n) Il trouve le chemin le plus court de la source à chaque autre noeud en considérant seulement coût réel.

ces algorithmes peuvent être utilisés dans l'orientation et la traversée de graphe, le processus de tracer un chemin efficacement dirigé entre plusieurs points, appelé noeuds.

formule pour a* is f =g + h. , g signifie coût réel et " h " signifie coût heuristique. la formule pour Dijktras est f = g . il n'y a pas d'heuristique coût. quand nous utilisons a* et si le coût heuristique est 0 alors il sera égal à algorithme de Dijktras.

a* est tout comme Dijkstra , la seule différence est que A* tente de chercher un meilleur chemin en utilisant une fonction heuristique qui donne la priorité aux noeuds qui sont censés être meilleurs que les autres tandis que Dijkstra explore juste tous les chemins possibles.

son optimalité dépend de la fonction heuristique utilisée, donc oui il peut rendre un résultat non optimal à cause de cela et en même temps mieux l'heuristique pour votre la disposition spécifique, et mieux seront les résultats (et peut-être la vitesse).

il est censé être plus rapide que Dijkstra même si elle nécessite plus de mémoire et plus d'opérations par noeud car il explore beaucoup moins de noeuds et le gain est bon dans tous les cas.

Précomputer les chemins pourrait être le seul moyen si vous avez besoin de résultats en temps réel et le graphique est assez grand, mais généralement vous souhaitez trouver le chemin moins fréquemment (je suppose que vous voulez le calculer souvent.)

courte réponse: * Utilise des heuristiques pour optimiser la recherche. Qui est, vous êtes en mesure de définir une fonction qui, à un certain degré peut estimer le coût d'un nœud à la cible. Ceci est particulièrement utile lorsque vous recherchez un chemin sur une représentation géographique (map) où vous pouvez, par exemple, deviner la distance de la cible à partir d'un noeud graphique donné. Par conséquent, typiquement A* est utilisé pour la recherche de chemin dans les jeux, etc. Où Djikstra est utilisé dans des cas plus génériques.

Non, A* ne donnera pas toujours le meilleur chemin. Si heuristique est la distance "géographique", l'exemple suivant pourrait donner le chemin non optimal.

[airport] - [road] - [start] -> [road] -> [road] -> [road] -> [road] -> [target] - [airport]
        |----------------------------------------------------------------|