Algorithmes de recherche pour la résolution de

problèmes
Mondher Bouden
Maître assistant

Semestre 5
2017
 Algorithmes de
recherche pour la résolution de problèmes
• Le but de ce chapitre est de présenter les
différents types des algorithmes de recherche
pour la résolution des problèmes.

• Nous commençons par une définition formelle

d’un problème (et d’une solution), et ensuite nous
verrons un nombre d’exemples spécifiques pour
illustrer cette définition.

2
 Définition formelle d’un problème
• Un problème est défini par les cinq éléments suivants :

1. Un état initial.
2. Un ensemble d’actions.
3. Une fonction de successeur, qui définit l’état résultant de
l’exécution d’une action dans un état.
4. Un ensemble d’états buts.
5. Une fonction de coût, associant à chaque action un
nombre non-négative (le coût de l’action).

3
 Définition formelle d’un problème
• Nous pouvons voir un problème comme un graphe
orienté où les nœuds sont des états accessibles depuis
l’état initial et où les arcs sont des actions.

• Nous appellerons ce graphe l’espace des états.

• Une solution sera un chemin de l’état initial à un état but.

• On dit qu’une solution est optimale si la somme des coûts

des actions du chemin est minimale parmi toutes les
solutions du problème.
4
 Exemples de problèmes
• Exemple1: Le taquin est une sorte de puzzle. Nous commençons
avec une grille 3x3 de neuf cases où sont placées huit tuiles
étiquetées par les nombres 1 à 8, une des cases restante est vide.
Une tuile située à côté de la case vide peut être déplacée vers cette
case.

• L’objectif du jeu est d’arriver à obtenir une certaine configuration

des tuiles dans la grille.

5
 Exemple1: Le taquin
• Voici une formalisation de ce problème :

• Des états sont des configurations des huit tuiles dans les neuf cases
de la grille.

• Etat initial: N’importe quel état pourrait être choisi comme l’état
initial.

• Actions: Il y aura 4 actions possibles correspondant aux quatre

façons de changer la position du carré vide : haut, bas, gauche,
droite (remarquez que dans certaines configurations, il n’y aura
que 2 ou 3 actions possibles).

6
 Exemple1: Le taquin
• Fonction de successeur: Cette fonction spécifie les états résultants
des différentes actions. Par exemple, la fonction va nous dire que
l’exécution de l’action droite dans le premier état de la figure
suivante produira le deuxième état de cette figure:

7
 Exemple1: Le taquin
• Test de but: L’état but est unique et fixé au début du jeu (n’importe
quel état peut être choisi comme état but, même si en pratique il
s’agit de remettre les nombres dans l’ordre).
• Coût des actions: Chaque déplacement d’une tuile a un coût de 1
(pour trouver une solution avec le moins de déplacements).

• Le taquin est souvent utilisé pour tester les algorithmes de

recherche. En augmentant la taille de la grille, nous pouvons créer
les problèmes de plus en plus complexes.
• Les algorithmes d’aujourd’hui arrivent à résoudre les taquins 3 x 3
et 4 x 4 (qui ont des espaces d’états de taille 181440 et d’environ
1,3 milliard respectivement), mais les instances du taquin 5x 5
(avec un espace d’états de taille 1025) restent difficiles.
8
 Exemple2: Huit reines
• Exemple2: Huit reines. L’objectif de ce jeu est de placer huit reines
sur un échiquier (une grille 8 x 8) tel qu’ aucune reine attaque une
autre reine, c’est `a dire qu’il n’y a pas deux reines sur la même
colonne, la même ligne, ou sur la même diagonale.
• La configuration donnée dans la figure à gauche n’est donc pas une
solution parce qu’il y a deux reines sur la même diagonale. Par
contre, la figure à droite représente une bonne solution.

9
 Exemple2: Huit reines
• Voici une formalisation du problème:

• Etats: Toute configuration de 0 à 8 reines sur la grille.

• Etat initial: La grille vide.
• Actions: Ajouter une reine sur n’importe quelle case vide de la
grille.
• Fonction de successeur: La configuration qui résulte de l’ajout
d’une reine à une case spécifié à la configuration courante.
• Test de but: Une configuration de huit reines avec aucune reine
sous attaque.
• Coûts des actions: Ce pourrait être 0, ou un coût constant pour
chaque action - nous nous intéressons pas ici du chemin, seulement
l’état but obtenu.
10
 Exemple2: Huit reines
• On peut réduire l’espace d’états
drastiquement (de 3 x 1014 à 2057!).

– Il est inutile de continuer de développer des

configurations où il y a déjà un conflit
(comme on ne peut pas résoudre le conflit en
ajoutant des reines supplémentaires).

11
 Exemples de problèmes
• Nous remarquons que ces deux problèmes sont de nature assez
différentes.

• Avec le taquin, nous savons depuis le début quel état nous voulons,
et la difficulté est de trouver une séquence d’actions pour
l’atteindre.

• En ce qui concerne le problème des huit reines, nous ne sommes

pas intéressés par le chemin mais seulement par l’état but obtenu.

• Ces deux jeux sont des exemples de deux grandes classes de

problèmes étudiés en IA : des problèmes de planification et des
problèmes de satisfaction de contraintes. Nous examinons plus
en détail ces deux classes.
12
 Les problèmes de planification
• Les problèmes de planification sont courants dans la vie de tous les
jours.
• Par exemple, considérons le problème de trouver le chemin le plus
court pour atteindre une destination. C’est un problème tellement
courant qu’il y a maintenant des GPS dédiés à cette tâche.
• Citons également les systèmes de planification de voyage qui
cherchent des itinéraires en transports en commun, en train ou en
avion. Formalisons ce dernier exemple :
• Etas: Chaque état est composé d’un aéroport et la date et l’heure
actuelle.
• Etat initial: L’aéroport d’où part le client, la date de départ
souhaitée, et l’heure à partir de laquelle le client peut partir.
• Actions: Ce sont des vols d’un aéroport à un autre.
13
 Planification de voyages
• Fonction de successeur: Les actions possibles sont des vols qui
partent de l’aéroport de l’état actuel, plus tard que l’heure actuelle
(en fait, nous devrons aussi exiger une certaine durée entre
l’arrivée dans un aéroport et le prochain vol, sinon le client risque
de rater sa correspondance ! ).

• Test de but: Les états où le client est à l’aéroport de sa destination.

• Coût des actions: Cela va dépendre des préférences du client. Ce

pourrait être 1 pour chaque action (pour minimiser la nombre de
connections), ou la durée des vols (pour minimiser la durée du
voyage), ou le prix des trajets (pour trouver le voyage le moins
cher).
14
 Les problèmes de satisfaction de contraintes
• Un problème de satisfaction de contraintes consiste:
– En un ensemble de variables,
– Des ensembles de valeurs permises pour chaque variable,
– Un ensemble de contraintes (sur les combinaisons des valeurs des variables).
• L’objectif est de trouver une valuation telle que chaque contrainte
est satisfaite.
• Par exemple:
– Gérer des pistes d’atterrissage à l’aéroport,
– Trouver un plan de table pour un mariage,
– Créer un emploi du temps à l’université.
• Les variables sont des cours, des valeurs possibles sont des triplets (jour,
heure, salle), et des contraintes de toute sorte (eg. il faut qu’un cours soit
enseigné le vendredi, il faut pas mettre deux cours en même temps, etc.).
Nous donnons une formalisation de cet exemple.
15
 Créer un emploi du temps à l’université
• Etats: Un emploi de temps partiel (c’est `a dire, un choix d’un
triplet (jour, heure, salle) pour un sous-ensemble des cours).

• Etat initial: Un emploi de temps vide.

• Actions: Choisir un triplet (jour, heure, salle) pour un cours qui

n’est pas encore sur la grille.

• Fonction de successeur: L’emploi de temps résultant.

• Test de but: Un emploi de temps contenant tous les cours et

satisfaisant toutes les contraintes.

• Coût des actions: Un coût constant. 16

 Les jeux à plusieurs joueurs
• Dans tous les problèmes considérés jusqu’à présent, il n’y avait
qu’un seul agent (c’est un terme important en IA qui désigne une
entité capable d’interagir avec son environnement) qui pouvait
choisir librement ses actions.
– Mais souvent nos décisions sont conditionnées par les actions
des autres. C’est notamment le cas pour les jeux à plusieurs
joueurs.

• Ces jeux sont plus compliqués, car l’agent ne peut pas choisir les
actions des autres joueurs.
– Au lieu de chercher un chemin qui relie l’état initial à un état but
(qui contiendrait des actions des adversaires, dont nous n’avons
pas le contrôle), nous allons chercher une stratégie, c.a.d. un
choix d’action pour chaque état où pourrait se trouver l’agent.
17
 Les jeux à plusieurs joueurs
• Voici une formalisation d’un jeu à plusieurs joueurs :
• Etats: Des configurations du jeu plus le nom de joueur dont c’est
le tour.
• Etat initial: La configuration initiale plus le nom du joueur qui
commence.
• Actions: Les coups légaux pour le joueur dont c’est le tour.
• Fonction de successeur: La nouvelle configuration du jeu, et le
nom de joueur dont c’est le tour.
• Test de but: Les configurations gagnantes pour le joueur.
• Coût des actions: Cela dépendra du jeu en question. Par exemple,
pour le jeu d’échecs, nous pouvons les mettre à 1 pour chercher
18
les coups qui amènent le plus vite à une configuration gagnante.
 Structure générale d’un algorithme de recherche
• La plupart des algorithmes de recherche suivent à peu près le
même schéma : nous commençons toujours dans l’état initial et
puis nous exécutons les étapes suivantes en boucle jusqu’à
terminaison :
– S’il n’y a plus d’états à traiter, renvoyez échec.
– Sinon, choisir un des états à traiter (*).
• Si l’état est un état but, renvoyez la solution correspondante.
• Sinon, supprimer cet état de l’ensemble des états à traiter, et
le remplacer par ses états successeurs.

• Ce qui va différencier les différents algorithmes est la manière dont

on effectue le choix à l’étape (*).

19
 Évaluation des algorithmes de recherche
• Voici quatre critères qui sont souvent utilisés pour comparer les
différents algorithmes de recherche :

– Complexité en temps: Combien du temps prend l’algorithme

pour trouver la solution (comportement asymptotique) ?

– Complexité en espace: Combien de mémoire est utilisée lors de

la recherche d’une solution ?

– Complétude: Est-ce que l’algorithme trouve toujours une

solution s’il y en a une ?

– Optimalité: Est-ce que l’algorithme renvoie toujours des

solutions optimales ?
20
 Les Algorithmes de recherche non informées.

• Ces algorithmes ne disposent pas d’informations

supplémentaires pour pouvoir distinguer des états
prometteurs.
– Ce n’est pas le cas par exemple des programmes joueurs
d’échecs qui ne peuvent explorer toutes les possibilités, et se
concentrent donc à chaque étape sur un petit nombre de coups
qui leur semblent être les meilleurs.
– En l’absence de telles informations, ces algorithmes font une
recherche exhaustive de tous les chemins possibles depuis
l’état initial.
– Exemple:
• Parcours en largeur.
• Parcours en profondeur. 21
 Parcours en largeur

• L’algorithme de recherche par contagion ou en largeur

(Breadth-First Search ou BFS) est à la base de la
résolution de problèmes tels que celui du chemin
minimum.

• Le principe: si l'on suppose que tout un groupe de

personnes entreprennent l'exploration d’une ville, à
chaque carrefour, le groupe pourra se partager pour aller
dans toutes les directions à la fois.

22
 Parcours en largeur

1. Initialiser (mettre à « faux ») une marque (une valeur booléenne)

associée à chaque nœud.

2. Enfiler et marquer (mettre sa marque à « vrai ») le nœud de départ.

3. Tant et aussi longtemps que la file n’est pas vide:
a) Défiler le prochain nœud.
b) Pour chaque voisin qui n’est pas marqué:
i. Le marquer
ii. L’enfiler.

Remarque: S’il s’agit d’un parcours fait pour retrouver un chemin

comportant le plus petit nombre d’étapes entre deux nœuds donnés, alors
on peut s’arrêter dès qu’on atteint le nœud d’arrivée. Aussi, si on veut la
description de ce chemin, il faut mémoriser le meilleur précédent pour
chaque nœud.
 Parcours en largeur

()
()
✓ () F
Nœud de E
départ A

B D
() ()
() G
C
()
File

A
 Parcours en largeur

()
()
✓ ()
Nœud de F E
départ A

B D
() ()
() G
C
()
File

Défilé: A
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
()
G ✓ (A)
✓ (A)
C
()
File

G ; B ; F

Défilé: A
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
()
G ✓ (A)
✓ (A)
C
()
File

B ; F

Défilé: G
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
()
G ✓ (A)
✓ (A)
C
()
File

Défilé: B
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D

✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

F ; C ; D

Défilé: B
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

C ; D

Défilé: F
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Défilé: C
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Défilé: D
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D

✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Meilleur chemin entre A et D:

D
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D

✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Meilleur chemin entre A et D:

D
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Meilleur chemin entre A et D:

B D
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Meilleur chemin entre A et D:

B D
 Parcours en largeur

✓ (A) ()
✓ ()
Nœud de F E
départ A

B D
✓ (A) ✓ (B)
G
✓ (A)
C
File ✓ (B)

Meilleur chemin entre A et D:

A B D
 Parcours en largeur

Questions
– Est-ce que tout graphe peut être parcouru par cet
algorithme ?
1 1
2 2
4 5 5
4

3 3

• Comment modifier l’algorithme pour que tout graphe soit parcouru ?

• Comment est-ce que l’algorithme s’arrêtera ?
• Pourquoi est-ce que ça marche bien pour trouver le chemin le plus court ?
 Parcours en profondeur

L'algorithme de recherche par sondage ou en profondeur

(Depth-First Search ou DFS) permet:

– d'explorer un graphe,
– d'en déterminer les composantes connexes,
– de découvrir s'il contient des cycles.

Cet algorithme de parcours dans un graphe a été mis au point par Trémaux
au siècle dernier pour résoudre le problème de la sortie d'un labyrinthe.
Trémaux qui n'avait pas la possibilité d’utiliser la récursivité à l'époque
utilisait un ''fil d'Ariane'' lui permettant de se souvenir par où il était
arrivé à cet endroit dans le labyrinthe.

L'algorithme utilise une pile pour le parcours du graphe à partir d'un

sommet donné. On progresse le long d'un de ces arcs et, si l’on ne
trouve pas ce que l’on cherche, on progressera alors le long d'un autre de ces
arcs.
 Parcours en profondeur

1. Initialiser (mettre à « faux ») une marque (une valeur booléenne)

associée à chaque sommet pour dire qu’il n’a pas été parcouru.
2. Empiler et marquer le nœud de départ.
3. Tant et aussi longtemps que la pile n’est pas vide:
a) Dépiler un nœud, et lui faire le traitement voulu pour le parcours
(par exemple, afficher sa valeur à l’écran).
b) Pour chacun de ses voisins qui n’est pas marqué:
i. Le marquer.
ii. L’empiler.

Remarque: Ce parcours n’est pas approprié pour retrouver le

chemin le plus court entre deux nœuds donnés. Il est cependant
très facile à implanter par une fonction récursive.
Parcours en profondeur
 Parcours en profondeur

Une approche par « BackTracking »

 Parcours en profondeur

✓ F
Nœud de E
départ A

B D

G
C
Pile

A
 Parcours en profondeur

✓ F
Nœud de E
départ A

B D

G
C
Pile

Dépilé: A
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓
✓ G
C
Pile

G ; B ; F

Dépilé: A
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓
✓ G
C
Pile

G ; B

Dépilé: F
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓
✓ G
C
Pile

Dépilé: B
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓ ✓
✓ G
C
✓
Pile

G ; C ; D

Dépilé: B
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B
D
✓ ✓
✓ G
C
✓
Pile

G ; C

Dépilé: D
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓ ✓
✓ G
C
✓
Pile

Dépilé: C
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓ ✓
✓ G
C
✓
Pile

Dépilé: G
 Parcours en profondeur

✓
✓ F
Nœud de E
départ A

B D
✓ ✓
✓ G
C
✓
Pile

FIN
 Parcours en profondeur

Questions

– Peut-on parcourir tout un graphe avec ce type de parcours ?

– Comment l’algorithme s’aperçoit-il qu’il est dans un cul-de-sac et
qu’il doit faire du retour-arrière (« backtracking ») ?
– Est-ce que ce parcours peut être utilisé pour trouver le chemin le
plus court ?
 Comparaison des deux parcours

Le graphe correspondant est obtenu en plaçant un sommet en chaque point du labyrinthe où il y a plus d'un chemin
possible et, ensuite, en connectant les sommets conformément à l'architecture du labyrinthe.
Comparaison des deux parcours
 Exemple: Backtracking

Exemple. Calcul du trajet du robot

Il s'agit de concevoir un algorithme qui permet à un robot

de trouver un chemin menant à la sortie d'un labyrinthe.
Pour ce faire le robot explore systématiquement les quatre
directions vers lesquelles il peut se déplacer. De plus, afin
d'éviter que le robot ne se retrouve sur des cases déjà
explorées chacune de celles-ci seront marquées à mesure
qu'elles sont visitées. C'est de façon récursive que les
cases faisant partie du chemin seront identifiées.
 Programmation du trajet d’un robot mobile

#define Y 9 /* Les dimensions du labyrinthe */

#define X 7
char laby[X][Y] = { {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
{'X', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X'},
{'X', ' ', 'X', 'X', ' ', 'X', 'X', ' ', 'X'},
{'X', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X'},
{'X', 'X', 'X', ' ', 'X', ' ', 'X', ' ', 'X'},
{'X', 's', ' ', ' ', ' ', ' ', ' ', ' ', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}};
int main()
{
int i, j;
bool Parcours(int x, int y);
if (Parcours(1,1)) {
// Imprimer le résultat de la recherche
for (i = 0; i < X; i++, cout<<endl)
for (j = 0; j < Y; j++)
cout<<laby[i][j]; }
else
cout<<"Il n'existe aucun chemin.\n";

return 0;
}
Programmation du trajet d’un robot mobile (suite)

bool Parcours(int x, int y)

{
if (laby[x][y] == 's') { /* on a trouvé la sortie */
laby[x][y] = 'S';
return true;
} else if (laby[x][y] == ' ') { /* la case est libre */
laby[x][y] = 'o'; /* marquer la case visitée */
if (Parcours(x-1, y)) /* Parcours nord */
return(true);
else if (Parcours(x+1, y)) /* Parcours sud */
return(true);
else if (Parcours(x, y+1)) /* Parcours est */
return(true);
else if (Parcours(x, y-1)) /* Parcours ouest */
return(true);
else
laby[x][y] = '-'; /* on laisse une marque */
}
return false;
}
 Retour en arrière - exercice

0 1 2 3 4 5 6 7 8 9

• Quel est le chemin

parcouru? Combien de
A

retours en arrière? B S
• Utiliser des appels C
récursifs et l’ordre d’appel
suivant: D

– Nord E
– Sud
– Est F
E
– Ouest
G

J
 Retour en arrière - exercice

bool Parcours(int x, int y) 0 1 2 3 4 5 6 7 8 9

{
if (laby[x][y] == 's') {
A

laby[x][y] = 'S'; B
return true; S
} else if (laby[x][y] == ' ') { C
laby[x][y] = 'o';
if (Parcours(x-1, y)) D
return(true);
else if (Parcours(x+1, y))
E

return(true); F
else if (Parcours(x, y+1)) E
return(true); G
else if (Parcours(x, y-1))
return(true); H
else
laby[x][y] = '-';
I

} J
return false;
}
Retour en arrière - réponse

0 1 2 3 4 5 6 7 8 9

B
X
o X
o S o X
o
C
X
o o o X
o
D
o o o
E
o o o o
F
o E o
G
o X
o o o o
H
o o o o
I
o o o o o
J
 Les algorithmes de recherche heuristique

• Les algorithmes que nous venons de voir font une

recherche exhaustive de tous les chemins possibles, ce
qui les rend inefficaces voire inutilisables sur les
problèmes de grande taille.

• Nous présentons maintenant les algorithmes de

recherche heuristiques1 qui utilisent des informations
supplémentaires pour pouvoir mieux guider la recherche.

1Les heuristiques sont des règles empiriques permettant de faire un

calcul fournissant une solution approchée, pas nécessairement
optimale, pour un problème d'optimisation difficile.
62
 Algorithme A*
• L'algorithme de recherche A* est un algorithme de
planification. Il a été créé pour que la première solution
trouvée soit l'une des meilleures, c'est pourquoi il est célèbre
dans des applications comme les jeux vidéo privilégiant la
vitesse de calcul sur l'exactitude des résultats.

• Cet algorithme a été proposé pour la première fois par Peter

E. Hart, Nils John Nilsson et Bertram Raphael en 1968. Il
s'agit d'une extension de l'algorithme de Dijkstra de 1959.

63
Algorithme de Dijkstra

 L’algorithme est basée sur la technique de relâchement

 C’est une méthode qui diminue progressivement le poids du plus cours chemin
pour chaque sommet jusqu’à ce qu’il soit égal au poids du plus court chemin.
 Pour chaque sommet i  v , on maintient à jour un attribut yi : une estimation
de la pondération d’un plus court chemin:

 État initial :
 ys = 0 (s étant la source)
 yi = + avec i  s
 À chaque étape : essayer de minimiser les yi
 État final : yi = lpcc(s,i) (lpcc: le plus court chemin)
Algorithme de Dijkstra

 RELÂCHER (a,b, c (a,b))

 Si yb > ya + c (a,b) Alors yb  ya + c (a,b)

5 2 9 5 2 6
a b a b
Relâcher(a,b, c(a,b)) Relâcher(a,b, c(a,b))
5 7 5 6
a 2 b a 2 b
 Algorithme de Dijkstra

 
b d
4 5
6

0 a 1 8 2 f 
2 3
10
c e
 
V, S, T a b c d e f
V: ensemble des sommets
S: les sommets solutionnés Y 0     
T: une file d’attente (suivant le coût)
Y: tableau des coûts P - - - - - -
P: tableau des sommets précédents
 Algorithme de Dijkstra

 
b d
4 5
6

0 a 1 8 2 f 
2 3
10
c e
 
V, S, T a b c d e f

Y 0     
P - - - - - -
 Algorithme de Dijkstra

4 (a) 
b d
4 5
6

0 a 1 8 2 f 
2 3
10
c e
2 (a) 

V, S, T a c b d e f

Y 0 2 4   
P - a a - - -
 Algorithme de Dijkstra

3 (c) 10 (c)
b d
4 5
6

0 a 1 8 2 f 
2 3
10
c e
2 (a) 12 (c)

V, S, T a c b d e f

Y 0 2 3 10 12 
P - a c c c -
 Algorithme de Dijkstra

3 (c) 8 (b)
b d
4 5
6

0 a 1 8 2 f 
2 3
10
c e
2 (a) 12 (c)

V, S, T a c b d e f

Y 0 2 3 8 12 
P - a c b c -
 Algorithme de Dijkstra

3 (c) 8 (b)
b d
4 5
6

0 a 1 8 2 f 14 (d)
2 3
10
c e
2 (a) 10 (d)

V, S, T a c b d e f

Y 0 2 3 8 10 14
P - a c b d d
 Algorithme de Dijkstra

3 (c) 8 (b)
b d
4 5
6

0 a 1 8 2 f 13 (e)
2 3
10
c e
2 (a) 10 (d)

V, S, T a c b d e f

Y 0 2 3 8 10 13
P - a c b d e
 Algorithme de Dijkstra

3 (c) 8 (b)
b d
4 5
6

0 a 1 8 2 f 13 (e)
2 3
10
c e
2 (a) 10 (d)

V, S, T a c b d e f

Y 0 2 3 8 10 13
P - a c b d e
 Algorithme A*

Principe général : évaluation du coût total d’un sommet

Coût total (F) = Coût depuis la source(G) + Coût vers la destination(H)

G : Coût depuis la source

• Algorithmes classiques (Ford, Bellman, Dijkstra)

H : Coût vers la destination

• Difficile puisque le reste du chemin (vers la destination) est encore inconnu.
 Algorithme A*

Pourquoi évaluer un coût vers la destination ?

Afin de resserrer l’ensemble des sommets à explorer en privilégiant les
sommets « qui semblent » nous rapprocher de la destination.

Remarque
Dans le cas d’un algorithme de recherche plus classique (Dijsktra), on effectue
une recherche exhaustive parmi TOUS les sommets candidats.

Conséquence
l’algorithme A* est plus performant que n’importe quel autre algorithme
puisqu’il diminue l’ensemble des sommets à explorer.
 Algorithme A*

Comment évaluer un coût vers la destination ?

En utilisant des heuristiques (prédictions) afin d’évaluer un coût vers la
destination INFERIEUR au coût réel (encore inconnu). À ce titre, A* est un
algorithme dit optimiste.

Remarque
Si l’heuristique était supérieur au coût réel, on risquerait de générer un chemin
qui ne soit pas minimal.
 Heuristiques: Algorithme A*

Théorème de Pythagore
S
40
H 2 = (Coté oppose) 2 +

H (Coté adjacent) 2
20

H 2 = 40 2 + 20 2
D
= 2000

H = 20 x (5) 1/2

Distance euclidienne
 Heuristiques: Algorithme A*

S
Nombre de cellules, en horizontal et en
vertical entre la source et la destination.

Plus conforme à la nature des déplacements

D autorisés (haut, bas, gauche, droite)

Distance de Manhattan
 Recherche de chemins de coût minimal
avec l’algorithme A*

Jeux vidéo
• Animation des personnages non joueurs
• Déplacement réaliste d’un personnage contrôlé par le joueur vers un objectif
désigné par le joueur

Simulation – vie artificielle

• Etude du comportement d’une foule, du trafic automobile, …
• Effets spéciaux (scènes de bataille, …)