Définitif
Dans la file
Arêtes examinées

  • Actuel
  • Dans la file
  • Définitif
  • Chemin
  • Estimation en ligne droite
Un clic sur un nœud choisit

En savoir plus sur la recherche A*

Recherche A*

La recherche A* trouve un plus court chemin d'un départ à une cible, comme l'algorithme de Dijkstra, mais elle sait à peu près où se trouve la cible. Chaque nœud reçoit une estimation de la distance restante, la ligne droite jusqu'à la cible, et la recherche repart toujours du nœud dont la distance jusqu'ici plus cette estimation est la plus petite. Cliquez sur un nœud pour partir de lui, choisissez une cible et avancez pas à pas pour voir la recherche se diriger vers la cible et laisser des coins entiers du graphe intacts. Appuyez sur Lecture pour suivre la recherche, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Cliquez sur un nœud pour en faire le départ ; basculez le clic sur Cible et cliquez sur un autre nœud pour en faire la cible. Le nombre sur chaque arête est sa longueur, le nombre sur chaque nœud sa distance jusqu'ici, et la ligne pointillée l'estimation en ligne droite de la distance restante. La ligne sous le graphe est la file, du plus petit score au plus grand, avec le score de chacun : la distance jusqu'ici plus l'estimation. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Cliquez sur un nœud pour en faire le départ. Basculez le clic sur Cible et cliquez sur un autre nœud pour en faire la cible.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où dans la recherche.
  3. Observez les scores dans la file et l'estimation en ligne droite en pointillés. À la fin, comparez les nœuds qu'il a fallu à A* et à l'algorithme de Dijkstra.

Comment fonctionne la recherche A*

Donnez au départ la distance 0 et placez-le dans une file. Chaque nœud de la file a un score : sa distance jusqu'ici plus une estimation de la distance restante. Répétez : prenez le nœud au plus petit score et rendez sa distance définitive. Si c'est la cible, arrêtez. Sinon, pour chaque voisin qui n'est pas définitif, ajoutez la longueur de l'arête à la distance du nœud ; si c'est plus court que la distance jusqu'ici du voisin, abaissez-la, retenez le nœud comme chemin pour y arriver, et placez le voisin dans la file avec son nouveau score.

Pourquoi l'estimation ne doit jamais être trop longue

A* trouve un plus court chemin tant que l'estimation ne dit jamais que la cible est plus loin qu'elle ne l'est vraiment : c'est une estimation admissible. La ligne droite en est une, car aucune route entre deux lieux n'est plus courte que la ligne droite. Une estimation trop longue peut faire manquer à A* le meilleur trajet ; une estimation de 0 partout fait de A* l'algorithme de Dijkstra, qui est sûr mais cherche dans toutes les directions. Meilleure est l'estimation, moins A* a besoin de nœuds. Dans l'application, chaque arête a la longueur de son tracé, arrondie à l'entier supérieur, donc la ligne droite est une estimation sûre.

Questions fréquemment posées

Qu'est-ce que la recherche A* ?

Un algorithme de recherche de chemin qui trouve un plus court chemin d'un départ à une cible. Il fonctionne comme l'algorithme de Dijkstra, mais trie sa file selon la distance jusqu'ici plus une estimation de la distance restante : il se dirige ainsi vers la cible au lieu de s'étendre dans toutes les directions.

Qu'est-ce qu'une heuristique admissible ?

Une estimation de la distance jusqu'à la cible qui n'est jamais plus longue que la vraie plus courte distance. Avec une estimation admissible, A* trouve toujours un plus court chemin. La distance à vol d'oiseau sur une carte en est l'exemple classique.

A* est-il plus rapide que l'algorithme de Dijkstra ?

En général, oui, quand vous cherchez le chemin vers une seule cible et disposez d'une bonne estimation : A* rend moins de nœuds définitifs, car les nœuds éloignés de la cible reçoivent des scores élevés. Avec une estimation de 0, il fait exactement comme l'algorithme de Dijkstra. L'algorithme de Dijkstra est le meilleur choix quand vous avez besoin des distances vers tous les nœuds.

Où utilise-t-on A* ?

Dans les jeux vidéo pour faire contourner des obstacles aux personnages, dans les calculateurs d'itinéraire, dans la planification des mouvements de robots, et dans les solveurs de casse-tête comme le 15-puzzle (taquin), où l'estimation compte à quelle distance les pièces sont de leur place.

Mon graphe est-il envoyé quelque part ?

Non. Le graphe est créé et parcouru dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur