Systèmes intelligents: représentation et

résolution de problèmes en intelligence

artificielle

Pr: MAJDOUB Soufyane

Université Privé de Fès

[Link]@[Link]
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 1 / 57
Concepts fondamentaux

• Agent : entité qui perçoit son environnement et agit pour atteindre

un but.
• Environnement : espace dans lequel l’agent évolue (grille, graphe,
puzzle...).
• État : description complète de la situation à un instant donné.
• État initial : point de départ du problème.
• État but : état qui satisfait le test de but (objectif atteint).

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 2 / 57

Actions, transitions et espace d’états

• Action : opération permettant de passer d’un état à un autre.

• Fonction de transition :

T (s, a) = s′ (état obtenu après action)

• Espace d’états : ensemble de tous les états possibles.

• Chemin : séquence d’états obtenue par application successive
d’actions.
s0 → s1 → · · · → sk

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 3 / 57

Solutions et optimalité

• Solution : un chemin menant de l’état initial à un état but.

• Coût du chemin : somme des coûts des actions effectuées.
X
C(chemin) = coût(ai )

• Solution optimale : solution ayant le coût total minimal.

Solution optimale = arg min C(chemin)

• Exemple :
• Plus court chemin (GPS)
• Moins de mouvements (Taquin)

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 4 / 57

Qu’est-ce qu’un problème en IA ?

• Un problème en IA est une situation où un agent doit atteindre un

objectif.
• Il est défini par :
• un état initial (point de départ),
• un état but (objectif à atteindre),
• un ensemble d’actions possibles,
• une fonction de transition (comment les actions changent l’état),
• un test de but.
• L’objectif est de trouver une séquence d’actions menant du départ
au but.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 5 / 57

Structure formelle d’un problème

• Un problème de recherche est défini par le tuple :

P = (S0 , A, T , G, C)

où :
• S0 : état initial
• A : liste des actions possibles
• T (s, a) : fonction de transition
• G(s) : test de but (vrai si l’état est solution)
• C : fonction coût du chemin (optionnel)
• Le rôle d’un algorithme de recherche :

Trouver un chemin solution S0 → · · · → Sfinal

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 6 / 57

Exemple 1 : Problème du GPS (Recherche de
chemin)

• État initial : position actuelle (maison)

• État but : arriver à l’université
• Actions : avancer, tourner à gauche/droite, prendre une rue
• Transition : nouvelle position après chaque mouvement
• Test de but : GPS détecte que la destination est atteinte
• Coût : distance ou temps

Problème pour étudiants

Trouver le plus court chemin dans une carte de 5 intersections :

A→B→C→D→E

Quelle séquence minimise la distance ?

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 7 / 57

Exemple 2 : Problème du Taquin (8-puzzle)
• État initial : disposition mélangée des tuiles
• État but : disposition ordonnée :

1 2 3
4 5 6
7 8 □
• Actions : déplacer la case vide (□)
• Test de but : puzzle résolu
• Coût : 1 mouvement

Problème pour étudiants

Quel est le minimum de déplacements pour passer de :

1 3 6
5 □ 2
4 7 8

à l’état final ?
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 8 / 57
Problème de recherche en IA

• Un problème de recherche en IA permet à un agent de trouver une

séquence d’actions menant d’un état initial à un état but.
• Il est défini par le 5-uplet :

P = (S0 , A, T , G, C)

• Éléments :
• S0 : état initial
• A : actions possibles
• T (s, a) : fonction de transition (nouvel état)
• G(s) : test de but (objectif atteint si vrai)
• C : coût du chemin (optionnel)
• Objectif : trouver
• une solution (chemin menant au but),
• ou une solution optimale (coût minimal).

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 9 / 57

Méthode de résolution en IA

• Une méthode de résolution en IA est une stratégie ou un algorithme

permettant à un agent de :
• explorer l’espace d’états,
• appliquer des actions,
• évaluer les alternatives possibles,
• trouver une solution menant de l’état initial à l’état but.
• Elle définit comment un agent cherche une solution dans un
problème formalisé.
• Objectif : obtenir une solution correcte, efficace et éventuellement
optimale.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 10 / 57

Deux grandes familles de méthodes

• Méthodes de recherche non informées (aveugles)

• N’utilisent aucune information sur la position du but.
• Exemples :
• Recherche en largeur (BFS)
• Recherche en profondeur (DFS)
• Uniform Cost Search (UCS)
• Recherche en profondeur itérative (IDDFS)
• Méthodes de recherche informées (avec heuristique)
• Utilisent une fonction heuristique estimant la distance au but.
• Exemples :
• Best-First Search
• A* (A-star)
• Recherche gloutonne

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 11 / 57

Rôle d’une méthode de résolution

• Une méthode de résolution décide :

• de l’ordre d’exploration des états,
• de la vitesse de convergence,
• de la qualité de la solution trouvée,
• des ressources nécessaires (temps, mémoire).
• Elle influence donc directement :
• l’efficacité du système,
• l’optimalité de la solution,
• la capacité à résoudre des problèmes complexes.
• Les méthodes sont au cœur des algorithmes de recherche :
BFS, DFS, UCS, A∗ , Best-First, ...

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 12 / 57

Recherche en largeur (BFS) : principe

• BFS (Breadth-First Search) = recherche en largeur.

• Explore les états par niveau de profondeur :
• d’abord tous les voisins de l’état initial,
• puis les voisins de ces voisins, etc.
• Utilise une file FIFO (First In, First Out).
• Propriétés :
• Complète si l’espace d’états est fini.
• Optimale si tous les coûts des actions valent 1.
• Intuition :
• le premier chemin qui atteint le but est un chemin le plus court en
nombre d’arêtes.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 13 / 57

Algorithme BFS (Recherche en largeur)

Algorithm 1: BFS simplifié (Recherche en largeur)

Input: État initial s0 , état but g
Output: Chemin solution ou message d’échec
Liste A Traiter;
A [Link](s0 );
DéjàVisité ← {s0 };
Parent[s0 ] ← rien;
while A Traiter n’est pas vide do
n ← premier élément de A Traiter;
retirer le premier élément de A Traiter;
if n = g then
retourner le chemin reconstruit via Parent;
foreach voisin v de n do
/ DéjàVisité then
if v ∈
ajouter v à DéjàVisité;
Parent[v ] ← n;
A [Link](v );

retourner "Aucun chemin trouvé";

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 14 / 57

Exemple BFS : graphe et 1re itération
On cherche un chemin de S vers G.

A C

S
D G

B E

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 15 / 57

Exemple BFS : graphe et 1re itération

Initialisation Itération 1 : développement de S

A Traiter [S] A Traiter (avant) [S]
DéjàVisité { S } voisin(S) [ A, B ]
Parent Parent[S] = – DéjàVisité (après) { S, A, B }
Parent Parent[A]=S, Parent[B]=S
A Traiter (après) [ A, B ]

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 16 / 57

Exemple BFS : 2e itération et chemin optimal

Début de l’itération 2 Atteinte de G (plus tard)

A Traiter [ A, B ]
Noeud Parent
DéjàVisité { S, A, B }
S –
Parent S :–, A :S, B :S
A S
C A
Itération 2 : développement de A G C
A Traiter (avant) [ A, B ]
voisin(A) [ C, D ]
DéjàVisité (après) { S, A, B, C, D }
Parent Parent[C]=A, Parent[D]=A
A Traiter (après) [ B, C, D ]

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 17 / 57

Exemple BFS : itérations 3 et 4

Début de l’itération 3 Début de l’itération 4

A Traiter [ B, C, D ] A Traiter [ C, D, E ]
DéjàVisité { S, A, B, C, D } DéjàVisité { S, A, B, C, D, E }
Parent[S] = – Parent[S] = –
Parent[A] = S Parent[A] = S
Parent Parent[B] = S Parent[B] = S
Parent
Parent[C] = A Parent[C] = A
Parent[D] = A Parent[D] = A
Parent[E] = B
Itération 3 : développement de B
Itération 4 : développement de C
A Traiter (avant) [ B, C, D ]
voisin(B) [E] A Traiter (avant) [ C, D, E ]
DéjàVisité (après) { S, A, B, C, D, E } voisin(C) [G]
Parent Parent[E] = B DéjàVisité (après) { S, A, B, C, D, E, G }
A Traiter (après) [ C, D, E ] Parent Parent[G] = C
A Traiter (après) [ D, E, G ]

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 18 / 57

Résumé des itérations et chemin optimal
Évolution de A Traiter et DéjàVisité à chaque itération
Itération A Traiter (début) DéjàVisité (début)
Initial [S] {S}
1 [S] {S}
Développement de S ⇒ A Traiter = [ A, B ], DéjàVisité = { S, A, B }
2 [ A, B ] { S, A, B }
Développement de A ⇒ A Traiter = [ B, C, D ], DéjàVisité = { S, A, B, C, D }
3 [ B, C, D ] { S, A, B, C, D }
Développement de B ⇒ A Traiter = [ C, D, E ], DéjàVisité = { S, A, B, C, D, E }
4 [ C, D, E ] { S, A, B, C, D, E }
Développement de C, découverte de G ⇒ DéjàVisité = { S, A, B, C, D, E, G }
Table des parents au moment où G est découvert :
Noeud n Parent[n]
S –
A S
B S
C A
D A
E B
G C
Chemin optimal reconstruit en remontant Parent :
G←C←A←S ⇒ S→A→C→G
Ce chemin est de longueur minimale (3 arêtes) entre S et G, ce qui est garanti par la recherche en largeur
(BFS).
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 19 / 57
Recherche en profondeur (DFS)

Définition : La recherche en profondeur (DFS : Depth First Search) est une méthode d’exploration de
graphe qui consiste à suivre un chemin le plus loin possible avant de revenir en arrière.
Elle fonctionne selon le principe suivant :
• On part du nœud initial.
• On explore toujours le voisin suivant non visité le plus profond.
• Lorsqu’on arrive à un nœud sans nouveaux voisins, on revient en arrière (backtracking).
• L’exploration continue jusqu’à trouver le but ou avoir tout visité.
Caractéristiques importantes :
• Elle utilise une pile (LIFO) : on traite toujours le dernier ajouté.
• DFS ne garantit pas un chemin de longueur minimale.
• Très utile pour explorer des structures profondes : arbres, labyrinthes, détection de cycles, analyse
de chemins.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 20 / 57

Algorithme DFS (Recherche en profondeur)

Algorithm 2: DFS simplifié

Input: État initial s0 , état but g
Output: Chemin solution ou message d’échec
Pile ← [ s0 ];
DéjàVisité ← { };
Parent[s0 ] ← rien;
while Pile n’est pas vide do
n ← dernier élément de Pile;
retirer ce dernier élément;
if n = g then
retourner le chemin reconstruit via Parent;
ajouter n à DéjàVisité;
foreach voisin v de n do
/ DéjàVisité then
if v ∈
Parent[v ] ← n;
ajouter v à la fin de Pile;

retourner "Aucun chemin trouvé";

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 21 / 57

Exemple DFS : graphe et initialisation
On cherche un chemin de S vers G avec une recherche en profondeur (DFS).

A C

S
D G

B E F

Initialisation

Pile (DFS) [S]

DéjàVisité {}
Parent vide

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 22 / 57

Exemple DFS : itération 1

Début de l’itération 1

Pile (début) [S]

DéjàVisité {}
Parent –

Développement de S

voisin(S) [ A, B ]
DéjàVisité {S}
Parent[A] S
Parent[B] S
Pile (après) [ A, B ]

DFS va explorer en profondeur → le dernier élément de la pile est B ou A ?

Pour donner un ordre cohérent : On ajoute les voisins dans l’ordre ”(A puis B)” → Le dernier ajouté est ”B”,
donc DFS développe ”B en premier”.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 23 / 57

Exemple DFS : itération 2

Début de l’itération 2

Pile [ A, B ]
DéjàVisité {S}
Parent A :S, B :S

Développement de B

voisin(B) [E]
DéjàVisité (après) { S, B, E }
Parent[E] B
Pile (avant) [ A, B ]
Pile (après) [ A, E ]

DFS descend maintenant vers ”E”.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 24 / 57

Exemple DFS : itération 3

Début de l’itération 3

Pile [ A, E ]
DéjàVisité { S, B, E }
Parent A :S, B :S, E :B

Développement de E

voisin(E) [F]
DéjàVisité (après) { S, B, E, F }
Parent[F] E
Pile (avant) [ A, E ]
Pile (après) [ A, F ]

DFS descend maintenant vers ”F”.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 25 / 57

Exemple DFS : itération 4

Début de l’itération 4

Pile [ A, F ]
DéjàVisité { S, B, E, F }
Parent A :S, B :S, E :B, F :E

Développement de F
F n’a aucun voisin non visité � c’est un cul-de-sac. On retire F de la pile et on remonte.

Pile (après) [A]

DéjàVisité { S, B, E, F }

DFS remonte vers ”A”.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 26 / 57

Exemple DFS : itération 5

Début de l’itération 5

Pile [A]
DéjàVisité { S, B, E, F }
Parent A :S, B :S, E :B, F :E

Développement de A

voisin(A) [ C, D ]
DéjàVisité (après) { S, B, E, F, A, C, D }
Parent[C] A
Parent[D] A
Pile (après) [ C, D ]

DFS va développer ”D” (dernier ajouté).

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 27 / 57

Exemple DFS : itération 6 — découverte de G

Début de l’itération 6

Pile [ C, D ]
DéjàVisité { S, B, E, F, A, C, D }
A :S, B :S, E :B, F :E,
Parent
C :A, D :A

Développement de D

voisin(D) [G]
DéjàVisité (après) { S, B, E, F, A, C, D, G }
Parent[G] D
Pile (après) [ C, G ]

G est atteint par DFS via le chemin :

S→A→D→G

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 28 / 57

Algorithme de Dijkstra : Principe

• Dijkstra est un algorithme de recherche du plus court chemin (PCC).

• Il permet de trouver les chemins de coût minimum depuis un nœud
source unique vers tous les autres nœuds d’un graphe.
• Il fonctionne sur des graphes avec des poids d’arêtes non négatifs
(positifs ou nuls).
• Utilise une file à priorité : le nœud à développer est toujours celui
avec le coût cumulé minimal jusqu’à présent.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 29 / 57

Dijkstra : Fonctionnement et Propriétés

• Exploration : Il explore les nœuds par ordre croissant de leur

distance (coût) par rapport à la source.
• Mise à jour : Pour chaque voisin v d’un nœud u développé, il calcule
un nouveau coût potentiel :

distance[u] + poids(u, v )

• Si ce nouveau coût est inférieur à la distance actuelle enregistrée

pour v , la distance est mise à jour (relaxation) et v est mis à jour dans
la file à priorité.
• Propriétés :
• Complète si le graphe est fini.
• Optimale : Trouve toujours le chemin de coût minimal, à condition que
tous les poids d’arêtes soient ≥ 0.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 30 / 57

Algorithme de Dijkstra (Version simplifiée)

Algorithm 3: Dijkstra simplifié

Input: Graphe G = (V , E), nœud de départ s, poids des arêtes
Output: Distance minimale de s vers chaque nœud, et les parents
foreach nœud v ∈ V do
Distance[v ] ← ∞;
Parent[v ] ← rien;
Distance[s] ← 0;
ListeTriée ← liste contenant tous les nœuds,
triés selon Distance[v ];
while ListeTriée n’est pas vide do
u ← nœud avec la plus petite Distance dans ListeTriée;
retirer u de ListeTriée;
foreach voisin v de u do
nouveauDist ← Distance[u] + poids(u, v );
if nouveauDist ¡ Distance[v ] then
Distance[v ] ← nouveauDist;
Parent[v ] ← u;
réordonner ListeTriée selon Distance[v ];

retourner Distance, Parent;

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 31 / 57

Exemple Dijkstra : graphe et initialisation
On cherche les distances minimales à partir du nœud A.

2 5
A B

D E
1

Initialisation de Dijkstra :
MAJDOUB Soufyane (UPF) Nœud Distance initiale
Systèmes intelligents Parent 16 décembre 2025 32 / 57
Exemple Dijkstra : itération 1 (développement de A)

Début de l’itération 1

ListeTriée (début) [ A(0), B(∞), C(∞), D(∞), E(∞) ]

Nœud extrait A (distance 0)

Voisins de A : B et D.
Avant mise à jour Après relaxation des arêtes de A
Nœud Distance Parent Nœud Distance Parent
A 0 – A 0 –
B ∞ Null B 2 A
C ∞ Null C ∞ Null
D ∞ Null D 6 A
E ∞ Null E ∞ Null

Nouvelle ListeTriée (A est retiré) :

ListeTriée = [ B(2), D(6), C(∞), E(∞) ]

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 33 / 57

Exemple Dijkstra : itération 2 (développement de B)

Début de l’itération 2

ListeTriée (début) [ B(2), D(6), C(∞), E(∞) ]

Nœud extrait B (distance 2)

Voisins de B : C et D.
Avant mise à jour Après relaxation des arêtes de B
Nœud Distance Parent Nœud Distance Parent
A 0 – A 0 –
B 2 A B 2 A
C ∞ Null C 5 B
D 6 A D 3 B
E ∞ Null E ∞ Null

Nouvelle ListeTriée (B est retiré) :

ListeTriée = [ D(3), C(5), E(∞) ]

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 34 / 57

Exemple Dijkstra : itérations 3 et 4

Itération 3 : développement de D

ListeTriée (début) [ D(3), C(5), E(∞) ]

Nœud extrait D (distance 3)
Voisin de D E

Nœud Distance (avant) Distance (après) / Parent

E ∞ 4 (Parent[E] = D)

Nouvelle ListeTriée (D est retiré) :

ListeTriée = [ E(4), C(5) ]

Itération 4 : développement de E

ListeTriée (début) [ E(4), C(5) ]

Nœud extrait E (distance 4)
Voisins de E aucun nouveau voisin

La ListeTriée devient :
ListeTriée = [ C(5) ]

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 35 / 57

Exemple Dijkstra : fin de l’algorithme et distances
finales
Itération 5 : développement de C

ListeTriée (début) [ C(5) ]

Nœud extrait C (distance 5)
Voisin de C E

On calcule une nouvelle distance pour E :

nouvelle distance = D[C] + 5 = 5 + 5 = 10 > D[E] = 4

Donc aucune mise à jour pour E.

Distances finales à partir de A :

Nœud Distance minimale depuis A Parent

A 0 –
B 2 A
C 5 B
D 3 B
E 4 D

Exemple de chemin le plus court jusqu’à E :

A→B→D→E (coût 2 + 1 + 1 = 4)

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 36 / 57

Algorithme A* : principe

• A* (A-star) est un algorithme de recherche du plus court chemin

dans un graphe.
• C’est une extension de l’algorithme de Dijkstra qui utilise des
heuristiques pour guider la recherche.
• Il est considéré comme un algorithme de recherche informée ou
heuristique.
• À chaque étape, A* évalue les nœuds à explorer en utilisant la
fonction d’évaluation f (n).
• Propriétés (avec une heuristique admissible et consistante) :
• Complète (si l’espace est fini).
• Optimale (trouve toujours le chemin de coût minimum).

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 37 / 57

La fonction d’évaluation f (n)

• La fonction d’évaluation f (n) est utilisée pour déterminer quel nœud

étendre ensuite.
• Elle est définie comme la somme de deux composantes :

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

• g(n) (Coût réel) :
• Représente le coût du meilleur chemin trouvé jusqu’à présent depuis
l’état initial (s0 ) jusqu’au nœud actuel (n).
• h(n) (Heuristique) :
• Estime le coût du chemin le moins cher du nœud actuel (n) à l’état but
(g).
• C’est une estimation, une ”devinette” du coût restant.
• Intuition : f (n) estime le coût total du chemin passant par n.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 38 / 57

Algorithme A* (version simplifiée)
Algorithm 4: A* simplifié
Input: État de départ s0 , état but g, heuristique h(n)
Output: Chemin solution ou message d’échec
ListeOuverte ← { s0 } ; // États à explorer
ListeFermée ← ∅ ; // États déjà explorés
foreach état n do
g[n] ← ∞ ; // coût depuis s0
f [n] ← ∞ ; // f (n) = g(n) + h(n)
Parent[n] ← rien;
g[s0 ] ← 0;
f [s0 ] ← g[s0 ] + h(s0 );
while ListeOuverte n’est pas vide do
choisir n dans ListeOuverte avec la plus petite valeur f [n];
retirer n de ListeOuverte;
ajouter n à ListeFermée;
if n = g then
retourner le chemin reconstruit en remontant Parent;
foreach voisin v de n do
if v ∈ ListeFermée then
continuer avec le voisin suivant;
nouveauG ← g[n] + cout action(n, v );
/ ListeOuverte then
if v ∈
ajouter v à ListeOuverte;
if nouveauG ¡ g[v] then
Parent[v ] ← n;
g[v ] ← nouveauG;
f [v ] ← g[v ] + h(v );

retourner "Pas de chemin trouvé";

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 39 / 57

Conditions d’optimalité : Heuristique

• L’optimalité de A* dépend des propriétés de l’heuristique h(n).

• Heuristique Admissible :
• Une heuristique est admissible si elle ne surestime jamais le coût réel
pour atteindre le but :

h(n) ≤ coût réel(n → g)

• Si h(n) est admissible, A* est optimal.
• Heuristique Consistante (ou Monotone) :
• Une heuristique est consistante si le coût estimé entre n et g n’est pas
supérieur au coût réel d’une étape plus le coût estimé du nœud suivant :

h(n) ≤ coût(n → v ) + h(v )

(où v est un successeur de n).

• La consistance implique l’admissibilité (si h(g) = 0).
• Si h(n) est consistante, A* peut être implémenté sans vérifier les nœuds
visités (comme Dijkstra), et il est toujours optimal.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 40 / 57

Définition du problème labyrinthe

Objectif : Trouver le plus court chemin entre un point de départ S et un point d’arrivée E dans une grille
contenant des murs.

Caractéristiques du problème :
• L’environnement est une grille 4x4.
• Certaines cellules sont des murs (notés #) : on ne peut pas les traverser.
• Un mouvement possible : haut, bas, gauche, droite.
• Chaque mouvement a un coût identique : 1.

But de la démonstration
Appliquer l’algorithme A* pour calculer le chemin de coût minimal entre S et E dans ce labyrinthe.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 41 / 57

Principe de l’algorithme A*

A* est une recherche informée : il choisit en priorité les nœuds qui semblent les plus prometteurs.

A* utilise une fonction d’évaluation :

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

• g(n) : coût réel du chemin parcouru depuis le départ jusqu’à n

• h(n) : estimation du coût restant pour atteindre la cible

Rôle de f (n)
Le nœud ayant la plus petite valeur de f est toujours choisi pour être développé en premier.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 42 / 57

Données du labyrinthe et heuristique
Grille étudiée :
• Dimension : 4x4
• Départ : S(0, 0)
• Arrivée : E(3, 3)
• Coût d’un mouvement : 1

Heuristique utilisée : Distance de Manhattan

h(n) = |xn − xE | + |yn − yE |

Avec E(3, 3), on a par exemple :

h(S(0, 0)) = |0 − 3| + |0 − 3| = 3 + 3 = 6

Cette heuristique :
• Est admissible → ne surestime jamais le coût réel
• Assure l’optimalité du chemin trouvé (avec A*)

(y,x) 0 1 2 3
0 S (6) 5 4 3
1 5 # 3 2
2 4 # 2 1
3 3 2 1 E (0)

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 43 / 57

Itération 1 — Développement de S(0, 0)
Initialisation :
• g(S) = 0, h(S) = 6 ⇒ f (S) = 6
• Frontière = [ S(0, 0) | f = 6 ]
• Visitées = ∅

Développement de S
• S est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles (sans diagonales, sans murs) : (0, 1) et (1, 0).

Calcul pour les voisins :

g=1 (un mouvement depuis S)
h(0, 1) = |1 − 3| + |0 − 3| = 2 + 3 = 5, h(1, 0) = |0 − 3| + |1 − 3| = 3 + 2 = 5

f =g+h =1+5=6

Voisin g h f Parent
(0,1) 1 5 6 S
(1,0) 1 5 6 S

Après itération 1 :
Frontière = [ (0, 1) | f = 6, (1, 0) | f = 6 ], Visitées = {S}

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 44 / 57

Itération 2 — Développements de (0, 1) et (1, 0)
Développement de (0,1)
• (0, 1) est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles (sans murs, non déjà visités) : (0, 2).
• (0, 0) est ignoré car déjà visité.
Pour (0, 2) :
g(0, 2) = g(0, 1) + 1 = 1 + 1 = 2
h(0, 2) = |2 − 3| + |0 − 3| = 1 + 3 = 4
f (0, 2) = 2 + 4 = 6
Voisin g h f Parent Action
(0,2) 2 4 6 (0,1) Ajouté

Développement de (1,0)
• (1, 0) est retiré de la Frontière et ajouté aux Visitées.
• Voisin vers le bas : (2, 0) (car (1, 1) est un mur, (0, 0) visité).
Pour (2, 0) :
g(2, 0) = g(1, 0) + 1 = 1 + 1 = 2
h(2, 0) = |0 − 3| + |2 − 3| = 3 + 1 = 4
f (2, 0) = 2 + 4 = 6
Voisin g h f Parent Action
(2,0) 2 4 6 (1,0) Ajouté

Après itération 2 :

Frontière = [ (0, 2) | f = 6, (2, 0) | f = 6 ]

Visitées = {S, (0, 1), (1, 0)}
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 45 / 57
Itération 3 — Développements de (0, 2) et (2, 0)
Situation au début de l’itération 3 :

Frontière = [ (0, 2)|f = 6, (2, 0)|f = 6 ], Visitées = {S, (0, 1), (1, 0)}

Développement de (0,2)
• (0, 2) est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles (sans murs, non visités) : (0, 3) et (1, 2).

g(0, 2) = 2
h(0, 3) = |3 − 3| + |0 − 3| = 3, h(1, 2) = |2 − 3| + |1 − 3| = 3
g(0, 3) = 3, f (0, 3) = 3 + 3 = 6; g(1, 2) = 3, f (1, 2) = 3 + 3 = 6
Voisin g h f Parent Action
(0,3) 3 3 6 (0,2) Ajouté
(1,2) 3 3 6 (0,2) Ajouté

Développement de (2,0)
• (2, 0) est retiré de la Frontière et ajouté aux Visitées.
• Voisin accessible (hors mur et non visité) : (3, 0).

g(2, 0) = 2, h(3, 0) = |0 − 3| + |3 − 3| = 3 ⇒ g(3, 0) = 3, f (3, 0) = 3 + 3 = 6

Voisin g h f Parent Action
(3,0) 3 3 6 (2,0) Ajouté

Après itération 3 : Frontière = [ (0, 3)|f = 6, (1, 2)|f = 6, (3, 0)|f = 6 ]

Visitées = {S, (0, 1), (1, 0), (0, 2), (2, 0)}
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 46 / 57
Itération 4 — Développements de (0, 3) et (3, 0)
Situation au début de l’itération 4 :

Frontière = [ (0, 3)|f = 6, (1, 2)|f = 6, (3, 0)|f = 6 ]

Développement de (0,3)
• (0, 3) est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles non visités : (1, 3)
• (0, 2) est ignoré car déjà visité.

g(0, 3) = 3, h(1, 3) = |3 − 3| + |1 − 3| = 2 ⇒ g(1, 3) = 4, f (1, 3) = 4 + 2 = 6

Voisin g h f Parent Action

(1,3) 4 2 6 (0,3) Ajouté

Développement de (3,0)
• (3, 0) est retiré de la Frontière et ajouté aux Visitées.
• Voisin accessible non visité : (3, 1)
• (2, 0) est ignoré car déjà visité.

g(3, 0) = 3, h(3, 1) = |1 − 3| + |3 − 3| = 2 ⇒ g(3, 1) = 4, f (3, 1) = 4 + 2 = 6

Voisin g h f Parent Action

(3,1) 4 2 6 (3,0) Ajouté

Après itération 4 : Frontière = [ (1, 2)|f = 6, (1, 3)|f = 6, (3, 1)|f = 6 ]

Visitées= {S, (0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0)}
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 47 / 57
Itération 5 — Développements de (1, 2) et (3, 1)
Situation au début de l’itération 5 : Frontière = [ (1, 2)|f = 6, (1, 3)|f = 6, (3, 1)|f = 6 ]
Développement de (1,2)
• (1, 2) est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles :
• (0, 2) déjà visité,
• (1, 1) est un mur ⇒ interdit,
• (1, 3) déjà en Frontière,
• (2, 2) nouveau nœud.

g(1, 2) = 3, h(2, 2) = |2 − 3| + |2 − 3| = 2 ⇒ g(2, 2) = 4, f (2, 2) = 4 + 2 = 6

Voisin g h f Parent Action
(2,2) 4 2 6 (1,2) Ajouté

Développement de (3,1)
• (3, 1) est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles :
• (3, 0) déjà visité,
• (2, 1) est un mur,
• (3, 2) nouveau nœud.

g(3, 1) = 4, h(3, 2) = |2 − 3| + |3 − 3| = 1 ⇒ g(3, 2) = 5, f (3, 2) = 5 + 1 = 6

Voisin g h f Parent Action
(3,2) 5 1 6 (3,1) Ajouté

Après itération 5 : Frontière = [ (1, 3)|f = 6, (2, 2)|f = 6, (3, 2)|f = 6 ]

Visitées = {S, (0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0), (1, 2), (3, 1)}
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 48 / 57
Itération 6 — Atteinte de l’objectif E(3, 3)
Situation au début de l’itération 6 :
Frontière = [ (1, 3)|f = 6, (2, 2)|f = 6, (3, 2)|f = 6 ]

Développement du nœud (3,2)

• (3, 2) est retiré de la Frontière et ajouté aux Visitées.
• Voisins accessibles :
• (3, 1) déjà visité,
• (2, 2) déjà en Frontière,
• (3, 3) qui est l’objectif E.

g(3, 2) = 5, h(3, 3) = 0 ⇒ g(E) = 6, f (E) = 6 + 0 = 6

Voisin g h f Parent Action
E(3,3) 6 0 6 (3,2) But atteint

Reconstruction du chemin optimal

En remontant les parents : S(0, 0) → (1, 0) → (2, 0) → (3, 0) → (3, 1) → (3, 2) → E(3, 3)
Nombre total de déplacements : g(E) = 6

Conclusion
Le coût minimal (nombre de mouvements) est 6, égal à h(S).

L’heuristique de Manhattan est admissible et permet à A* de trouver un chemin optimal.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 49 / 57

Exemple 2 : Problème du Taquin (8-puzzle)
• État initial : disposition mélangée des tuiles
• État but : disposition ordonnée :

1 2 3
4 5 6
7 8 □
• Actions : déplacer la case vide (□)
• Test de but : puzzle résolu
• Coût : 1 mouvement

Problème pour étudiants

Quel est le minimum de déplacements pour passer de :

1 3 6
5 □ 2
4 7 8

à l’état final ?
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 50 / 57
Rappel : Algorithme A*
Coût g, heuristique h et fonction f

• g(n) : coût du chemin depuis l’état initial jusqu’à n.

• h(n) : estimation du coût restant jusqu’au but.
• f (n) = g(n) + h(n) : fonction d’évaluation minimale.

Heuristique utilisée
Heuristique admissible : distance de Manhattan
8
X
h(n) = |xt − xt∗ | + |yt − yt∗ |
t=1

où (xt , yt ) = position actuelle, (xt∗ , yt∗ ) = position dans l’état but.

L’heuristique ne surestime jamais ⇒ A* trouve un chemin optimal.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 51 / 57

Évaluation de l’état initial
Calcul détaillé de h(S0 )

1 3 6
S0 = 5 □ 2
4 7 8
Calcul des distances de Manhattan (tuile par tuile) :

h(S0 ) = 0 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 8

g(S0 ) = 0 f (S0 ) = g + h = 8

Interprétation
L’état initial est déjà “à 8 mouvements” du but selon l’heuristique. A* va
chercher à réduire h tout en augmentant progressivement g.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 52 / 57

Déroulement d’A* : premières étapes
A* choisit toujours le nœud avec le plus petit f

Étape 1 : déplacer □ vers la droite

1 3 6
S1 = 5 2 □
4 7 8

g = 1, h = 7, f =8
Étape 2 : □ monte (échange avec 6)

1 3 □
S2 = 5 2 6
4 7 8

g = 2, h = 6, f =8

Observation
À chaque étape : h baisse d’une unité et g augmente d’une unité. Ainsi, f
reste constant et minimal.
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 53 / 57
Déroulement d’A* : étapes intermédiaires
A* continue sur le chemin optimal

Étape 3 : □ va à gauche
1 □ 3
S3 = 5 2 6
4 7 8
g = 3, h = 5, f = 8
Étape 4 : □ descend
1 2 3
S4 = 5 □ 6
4 7 8
g = 4, h = 4, f = 8

Point clé
La première ligne est maintenant correcte : (1, 2, 3) A* se rapproche
progressivement du but tout en maintenant f minimal.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 54 / 57

Finalisation du chemin optimal
Atteindre l’état but en 8 déplacements

Étape 5 : □ va à gauche
1 2 3
S5 = □ 5 6
4 7 8
Étape 6 : □ descend
1 2 3
S6 = 4 5 6
□ 7 8
Étape 7 : □ à droite
1 2 3
S7 = 4 5 6
7 □ 8
Étape 8 : □ à droite (état final)
1 2 3
S8 = 4 5 6
7 8 □

g = 8, h = 0, f =8
MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 55 / 57
Récapitulatif des valeurs (g, h, f)
Vérification de l’optimalité

État g h f
S0 0 8 8
S1 1 7 8
S2 2 6 8
S3 3 5 8
S4 4 4 8
S5 5 3 8
S6 6 2 8
S7 7 1 8
S8 8 0 8

Conclusion
L’algorithme A* atteint l’état but en 8 déplacements. Ce chemin est
garanti optimal car l’heuristique de Manhattan est admissible.

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 56 / 57

Questions ?

Merci pour votre attention !

MAJDOUB Soufyane (UPF) Systèmes intelligents 16 décembre 2025 57 / 57