Je regardais ce que les gars de la Concours Mario AI Certains d'entre eux ont construit de superbes robots Mario en utilisant l'algorithme de cheminement A* (A-Star).
( Vidéo de Mario A* Bot en action )
Ma question est la suivante : comment A-Star se compare-t-il à Dijkstra ? En les regardant, ils semblent similaires.
Pourquoi utiliser l'un plutôt que l'autre ? En particulier dans le contexte du cheminement dans les jeux ?
Dans dijkstra, on ne considère que la distance de la source, non ? Et on prend en compte le sommet minimum ?
Je pensais que A* était un cas spécial pour Dijkstra où ils utilisent une heuristique. Puisque Dijkstra était le premier à exister, je crois.
Il a une fonction de coût, qui est la valeur du coût réel de la source à chaque nœud : f(x)=g(x) .
Il trouve le chemin le plus court de la source à chaque autre nœud en ne considérant que le coût réel.
Il a deux fonctions de coût.
g(x) : même chose que Dijkstra. Le coût réel pour atteindre un noeud x .h(x) : coût approximatif du nœud x au nœud de but. Il s'agit d'une fonction heuristique. Cette fonction heuristique ne doit jamais surestimer le coût. Cela signifie que le coût réel pour atteindre le nœud d'objectif à partir du nœud x doit être supérieure ou égale à h(x) . Elle est appelée heuristique admissible.Le coût total de chaque nœud est calculé par f(x)=g(x)+h(x)
La recherche A* ne développe un nœud que s'il semble prometteur. Elle se concentre uniquement sur l'atteinte du nœud cible à partir du nœud actuel, et non sur l'atteinte de tous les autres nœuds. Elle est optimale, si la fonction heuristique est admissible.
Ainsi, si votre fonction heuristique permet d'approximer le coût futur, vous devrez explorer beaucoup moins de nœuds que Dijkstra.
Ce que l'affiche précédente a dit, plus le fait que Dijkstra n'a pas d'heuristique et choisit à chaque étape les bords avec le plus petit coût, il a tendance à "couvrir" plus de votre graphique. Pour cette raison, Dijkstra peut être plus utile que A*. Un bon exemple est lorsque vous avez plusieurs nœuds cibles candidats, mais que vous ne savez pas lequel est le plus proche (dans le cas de A*, vous devriez l'exécuter plusieurs fois : une fois pour chaque nœud candidat).
L'algorithme de Dijkstra ne sera jamais utilisé pour la recherche de chemin. L'utilisation de A* est une évidence si vous pouvez trouver une heuristique décente (généralement facile pour les jeux, surtout dans les mondes en 2D). Selon l'espace de recherche, l'approfondissement itératif de A* est parfois préférable car il utilise moins de mémoire.
Pourquoi la méthode de Dijkstra ne serait-elle jamais utilisée pour la recherche de chemin ? Pouvez-vous nous en dire plus ?
Parce que même si vous parvenez à trouver une heuristique minable, vous ferez mieux que Dijkstra. Parfois même si c'est inadmissible. Cela dépend du domaine. Dijkstra ne fonctionnera pas non plus dans les situations à faible mémoire, alors qu'IDA* le fera.
J'ai trouvé les diapositives ici : webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Courses/657/Notes/
Ce n'est pas vrai. Le Dijkstra standard est utilisé pour donner le chemin le plus court entre deux points.
Ne vous méprenez pas, la méthode de Dijkstra donne le résultat de s à tous les autres sommets. Il fonctionne donc plus lentement.
Je seconde le commentaire de @Emil. Tout ce que vous devez faire est de vous arrêter lorsque vous retirez le nœud de destination de la file d'attente prioritaire et vous avez le chemin le plus court de la source à la destination. C'était l'algorithme original en fait.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
50 votes
xkcd.com/342
3 votes
@SLaks A* utilise plus de mémoire que dijkstra ? Comment se fait-il que A* n'emprunte que des chemins prometteurs alors que dijkstra les essaie tous ?