∑
MathTCG
#053 / 100•Space, Chance & Computation•MathTCG #453 / 500•★★Peu commune•⊦Maths Discrètes•Méthode & Idée

Algorithme A*

Période historique : 1968

Recherche de plus court chemin guidée par une heuristique admissible combinant coût passé et distance estimée.

Contenu & Formulation mathématique

Principe de la démarche
Recherche de plus court chemin guidée par une heuristique admissible combinant coût passé et distance estimée.
Champs d'application canoniques
Démonstration mathématique
f(n)=g(n)+h(n),h(n)≤c(n,p)+h(p)  (consistance)  ⟹  optimaliteˊf(n) = g(n) + h(n), \quad h(n) \le c(n, p) + h(p) \; (\text{consistance}) \implies \text{optimalité}

Genèse & Portée historique

Développé pour le robot Shakey par Peter Hart, Nils Nilsson et Bertram Raphael en 1968, A* étend l'algorithme de Dijkstra en ordonnant les nœuds selon f(n) = g(n) + h(n), où g(n) est le coût exact depuis le départ et h(n) une estimation admissible (ne surestimant jamais le coût réel restant). Il est garanti de trouver le chemin optimal tout en explorant un nombre minimal de nœuds.

Shakey le robot fut le premier robot autonome mobile capable de délibérer sur ses propres actions, naviguant dans les couloirs du Stanford Research Institute grâce à A*.

« L'intuition heuristique guide le pas pour n'explorer que les sentiers prometteurs. »

Filiations & Relations conceptuelles (1)

Généralise#410

Algorithme de Dijkstra

A* étend Dijkstra par une heuristique admissible h(n).

Objet de collection MathTCG

#453
★★Peu commune
⊦

Algorithme A*

Maths Discrètes•MÉTHODE

Principe : Recherche de plus court chemin guidée par une heuristique admissible combinant coût passé et distance estimée.

f(n)=g(n)+h(n),h(n)≤c(n,p)+h(p)  (consistance)  ⟹  optimaliteˊf(n) = g(n) + h(n), \quad h(n) \le c(n, p) + h(p) \; (\text{consistance}) \implies \text{optimalité}
1968

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#053 / 100)
Numéro global MathTCG : MathTCG #453 / 500
Rareté officielle : Peu commune (★★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : algorithme-a-star
Consulter mon classeurExplorer tout le recueil