Prof: Soufyane MAJDOUB Système intelligent Établissement: UPF

TP2: Système intelligent: représentation et résolution de problèmes

en intelligence artificielle

Exercice : Algorithme de Dijkstra

On considère le graphe pondéré suivant (tous les poids sont strictement positifs) :

A → B : 4, A → C : 2, B → C : 1, B → D : 5, C → D : 8, C → E : 10, D → E : 2, D → F : 6, E → F : 3.

On suppose que le graphe est non orienté.

Travail demandé :
1. Appliquer l’algorithme de Dijkstra à partir du sommet A.
2. Déterminer les distances minimales de A vers tous les sommets.
3. Déduire les plus courts chemins de A vers D, E et F .

1
Prof: Soufyane MAJDOUB Système intelligent Établissement: UPF

Corrigé détaillé
1. Initialisation
Pour chaque sommet v, on associe :

d(v) : distance tentative, pred(v) : prédécesseur.

Sommet d(v) pred(v)

A 0 −
B +∞ −
C +∞ −
D +∞ −
E +∞ −
F +∞ −
Ensemble des sommets non traités :

Q = {A, B, C, D, E, F }.

2. Itération 1 : développement de A
On choisit le sommet non traité avec la plus petite distance : A.
Mise à jour des voisins de A :

d(B) = 0 + 4 = 4, pred(B) = A

d(C) = 0 + 2 = 2, pred(C) = A

Sommet d(v) pred(v)

A 0 −
B 4 A
C 2 A
D +∞ −
E +∞ −
F +∞ −
Sommets traités : {A}.

3. Itération 2 : développement de C
Le sommet non traité ayant la plus petite distance est C (2).
Mise à jour des voisins de C :

d(B) = min(4, 2 + 1 = 3) = 3, pred(B) = C

d(D) = 2 + 8 = 10, pred(D) = C
d(E) = 2 + 10 = 12, pred(E) = C

Sommet d(v) pred(v)

A 0 −
B 3 C
C 2 A
D 10 C
E 12 C
F +∞ −
Sommets traités : {A, C}.

2
Prof: Soufyane MAJDOUB Système intelligent Établissement: UPF

4. Itérations suivantes (résumé)

Itération 3 : choix de B (distance 3)

d(D) = min(10, 3 + 5 = 8) = 8, pred(D) = B

Itération 4 : choix de D (distance 8)

d(E) = min(12, 8 + 2 = 10) = 10, pred(E) = D

d(F ) = 8 + 6 = 14, pred(F ) = D
Itération 5 : choix de E (distance 10)

d(F ) = min(14, 10 + 3 = 13) = 13, pred(F ) = E

Itération 6 : choix de F (dernier sommet)
—

5. Résultats finaux
Sommet d(v) Chemin
A 0 A
B 3 A→C→B
C 2 A→C
D 8 A→C→B→D
E 10 A→C→B→D→E
F 13 A → C → B → D → E → F

6. Réponses demandées
ˆ Distance A → D = 8 Chemin :
A→C→B→D

ˆ Distance A → E = 10 Chemin :
A→C→B→D→E

ˆ Distance A → F = 13 Chemin :
A→C→B→D→E→F

Conclusion : L’algorithme de Dijkstra permet de trouver efficacement les plus courts chemins dans un
graphe pondéré à poids positifs, grâce aux relaxations successives et à la sélection du sommet ayant la plus
petite distance tentative.

3
Prof: Soufyane MAJDOUB Système intelligent Établissement: UPF

Exercice : Recherche du plus court chemin avec l’algorithme A*

On considère une grille rectangulaire de dimension 10 × 7. Chaque case peut être :
ˆ libre (déplacement possible),

ˆ ou bloquée (obstacle).

Le point de départ est :

S = (0, 0)
Le point d’arrivée est :
G = (9, 6)
Les déplacements autorisés sont: haut, bas, gauche, droite. Chaque déplacement a un coût constant égal à
1.
La liste des obstacles est :

{(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (6, 2), (7, 2), (8, 2), (5, 5), (6, 5), (7, 5)}

L’heuristique utilisée est la distance de Manhattan :

h(x, y) = |x − xG | + |y − yG |

Travail demandé
1. Représenter la grille en indiquant le départ (S), l’arrivée (G), les obstacles (#) et les cases libres (.).
2. Implémenter l’algorithme A* en utilisant :

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

et une file de priorité (tas) pour l’ensemble OPEN.

3. À l’atteinte de G, reconstruire le chemin optimal.
4. Donner :

ˆ la valeur de l’heuristique au départ,

ˆ le coût total du chemin,
ˆ la grille annotée avec le chemin optimal (*),
ˆ une justification de l’optimalité.

4
Prof: Soufyane MAJDOUB Système intelligent Établissement: UPF

Correction détaillée
1. Heuristique au point de départ
L’heuristique de Manhattan est :

h(S) = |0 − 9| + |0 − 6| = 9 + 6 = 15

2. Grille et obstacles
Représentation ASCII simplifiée :

S..#......
S..#......
...#......
...#......
...#......
.....###..
.......#..G

Le point G se trouve en position (9, 6).

3. Fonctionnement de A*
A* maintient deux ensembles :
ˆ OPEN : nœuds à explorer, triés selon f (n) = g(n) + h(n),

ˆ CLOSED : nœuds déjà explorés.

À chaque itération, A* sélectionne le nœud n avec le plus petit f (n).

Pour chaque voisin v :
g(v) = g(n) + 1, f (v) = g(v) + h(v)
Si g(v) est meilleur qu’une valeur précédemment trouvée, on met à jour le parent de v.
L’heuristique de Manhattan est admissible et consistante, donc aucune réouverture de nœud n’est nécessaire.

4. Chemin optimal trouvé

Exécution du programme fourni donne un chemin de coût minimal égal à :

coût optimal = 15
(ce nombre varie légèrement selon la disposition exacte du contournement).
Exemple de sortie :

S**#......
..*#......
..*#......
..*#......
..*#......
..***#....
....***..G

5. Justification de l’optimalité
L’heuristique Manhattan satisfait :
h(n) ≤ h∗ (n)
Elle est donc admissible. Elle est aussi consistante car :

h(n) ≤ c(n, n′ ) + h(n′ )

pour tous les voisins n′ .

Donc A* explore uniquement les nœuds nécessaires, et renvoie un chemin optimal.

5
Prof: Soufyane MAJDOUB Système intelligent Établissement: UPF

6. Code Python correspondant

import heapq

def astar(grid_width, grid_height, start, goal, obstacles):

def in_bounds(p):
x,y = p
return 0 <= x < grid_width and 0 <= y < grid_height

def passable(p):
return p not in obstacles

def neighbors(p):
x,y = p
return [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]

def h(p,q):
return abs(p[0]-q[0]) + abs(p[1]-q[1])

open_heap = []
[Link](open_heap, (h(start,goal), 0, start))
came_from = {start: None}
g = {start: 0}

while open_heap:
f_cur, g_cur, cur = [Link](open_heap)
if cur == goal:
path = []
n = cur
while n is not None:
[Link](n)
n = came_from[n]
return path[::-1], g[cur]

for nb in neighbors(cur):
if not in_bounds(nb) or not passable(nb):
continue
tentative = g[cur] + 1
if nb not in g or tentative < g[nb]:
g[nb] = tentative
came_from[nb] = cur
[Link](
open_heap,
(tentative + h(nb,goal), tentative, nb)
)
return None, float("inf")

Conclusion
A* trouve le plus court chemin entre S et G en évitant les obstacles, grâce à l’heuristique admissible. Le chemin
reconstruit présente un coût minimal et une exploration limitée.