Scribd
Importer
30 vues2 pages

Explication Mathématique A

L'algorithme A* utilise la fonction d'évaluation f(n) = g(n) + h(n) pour déterminer le meilleur chemin à explorer, où g(n) représente le coût réel et h(n) une estimation heuristique. Il choisit les nœuds à explorer en fonction de leur score f(n) dans une liste de priorité et met à jour les coûts des nœuds voisins selon un processus de relaxation. A* est un algorithme déterministe qui ne repose pas sur des probabilités, mais sur des priorités pour garantir l'efficacité de la recherche du chemin optimal.

Transféré par

tomamattle
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
30 vues2 pages

Explication Mathématique A

L'algorithme A* utilise la fonction d'évaluation f(n) = g(n) + h(n) pour déterminer le meilleur chemin à explorer, où g(n) représente le coût réel et h(n) une estimation heuristique. Il choisit les nœuds à explorer en fonction de leur score f(n) dans une liste de priorité et met à jour les coûts des nœuds voisins selon un processus de relaxation. A* est un algorithme déterministe qui ne repose pas sur des probabilités, mais sur des priorités pour garantir l'efficacité de la recherche du chemin optimal.

Transféré par

tomamattle
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Principes Mathématiques de l’Algorithme A*

Explication Concise

1. La Formule d’Évaluation Clé


L’algorithme A* évalue chaque nœud (case) n à l’aide de la fonction :

f (n) = g(n) + h(n)

• g(n) – Coût Réel : Coût exact connu depuis le nœud Start jusqu’au nœud n.

• h(n) – Heuristique : Coût estimé (supposé) depuis le nœud n jusqu’au nœud Goal.

• f (n) – Score Total : Estimation du coût total du chemin passant par n.

2. Calcul de l’Heuristique h(n)


Soit ∆x = |nx − goalx | et ∆y = |ny − goaly |.

Manhattan (Mouvements 4 directions)


Utilisé quand les diagonales ne sont pas permises.

h(n) = ∆x + ∆y

Euclidienne (Mouvements 8 directions)


La distance ”à vol d’oiseau”. p
h(n) = (∆x)2 + (∆y)2

Diagonale / Octile (Mouvements 8 directions)


√
Très précise si les coûts sont 1 (droit) et
2 (diagonale).
√
h(n) = max(∆x, ∆y) + ( 2 − 1) × min(∆x, ∆y)

3. Le Processus de Choix (Priorité, pas Probabilité)


A* n’utilise ni probabilité ni combinatoire. C’est un algorithme déterministe (il refera toujours
le même choix dans la même situation) basé sur la priorité.
Il utilise deux listes :

• Open Set (O): Une file de priorité (min-heap). Contient tous les nœuds découverts mais
pas encore visités.

• Closed Set (C): Un ensemble. Contient tous les nœuds déjà visités.

1
La Règle de Choix
À chaque étape, l’algorithme choisit le nœud nactuel qui est dans l’Open Set O et qui a le plus
petit score f (n).
nactuel = arg min(f (n))
n∈O

C’est ainsi qu’il choisit le ”meilleur” chemin à explorer : celui qui semble être le plus court.

4. La Mise à Jour (Relaxation)


Une fois nactuel choisi, il est déplacé de O vers C. L’algorithme regarde alors ses voisins m.
Pour chaque voisin m de nactuel (qui n’est pas un mur ou dans C) :

1. Calculer le coût pour atteindre m en passant par n:

gtentatif = g(nactuel ) + coût(nactuel , m)


√
(coût vaut 1 ou 2)

2. Vérifier si ce nouveau chemin est meilleur :

SI gtentatif < g(m) (ou si m est nouveau)

3. Si oui, mettre à jour m :

• parent(m) ← nactuel
• g(m) ← gtentatif
• f (m) ← g(m) + h(m)
• Ajouter m à l’Open Set O (pour qu’il soit considéré lors d’un futur choix).

Vous aimerez peut-être aussi