Exercices d’application sur les parcours de graphes
Exercice #1
Soit le graphe suivant, représentant un espace de recherche. Chaque lettre représente un état et chaque
flèche une opération possible pour passer d’un état à un autre. Indiquez la suite des états à parcourir
pour passer de l’état A à l’état X par la technique de recherche en profondeur d’abord. Les numéros
associés aux flèches sortant d’un état représentent l’ordre dans lequel les opérations doivent être
appliquées pour cet état. Aucun état ne devra être revisité.
Exercice #2
Soit l’arbre suivant dans lequel le nœud « P » désigne l’état initial. La notation « P : 10 » signifie que la
valeur de la fonction heuristique au nœud P est égale à 10.
Énumérer la liste ordonnée des nœuds traversés pour la technique du meilleur d’abord. Indiquer aussi
s’il s’agit d’un succès ou d’un échec de la recherche. Aucun nœud ne devra être revisité. Si plusieurs
nœuds sont candidats, on choisit le nœud le plus à gauche. L’état initial est P et le but est atteint lorsque
la valeur heuristique est nulle.
1
Exercice #3
On veut utiliser l’algorithme A pour trouver le chemin le plus court entre l’entrée et la sortie dans le
labyrinthe suivant :
Les déplacements se font uniquement dans les quatre directions↑,↓,→,←et toujours d’une case à la
fois. Chaque déplacement a un coût de 1.
Considérons comme fonction heuristique, la somme des distances horizontales et verticales jusqu’à la
sortie. La valeur heuristique de la case d’entrée sera de 5 (3 horizontalement + 2 verticalement).
Simuler le déroulement de l’algorithme A* .
Exercice #4
Cinq billes sont alignées. Deux sont vertes (V), deux sont rouges (R), une est blanche(B). Au départ,
elles sont disposées dans l'ordre VVBRR. À l'arrivée, elles doivent être dans l'ordre RRBVV. Quatre
types de mouvements sont autorisés :
1. vert_à_droite : une bille V immédiatement à gauche de la bille B peut changer de place avec B.
2. rouge_à_gauche : une bille R immédiatement à droite de la bille B peut changer de place avec B.
3. vert_chevauche_rouge : une bille V immédiatement suivie d'une bille R, elle-même suivie de la bille
B peut changer de place avec la bille B.
4. rouge_chevauche_vert : une bille R immédiatement précédée d'une bille V, elle-même précédée de la
bille B peut changer de place avec la bille B.
a) Dessiner l'arbre de recherche complet pour ce problème selon l’approche par espace d’états. Les
états ne doivent jamais être revisités. Indiquer l’opérateur utilisé pour chaque étape.
b) Appliquer la technique du meilleur d’abord. Numéroter séquentiellement les états visités.
L’heuristique sera le nombre de billes mal placées. Si 2 nœuds ont la même valeur heuristique, on
choisira le plus à gauche.
Exercice #5
Soit un jeu de deux adversaires où chaque joueur a toujours le choix entre deux mouvements. Appelons
ces deux adversaires MAX et MIN. Soit une fonction heuristique f(E) où E est l’état du jeu. La valeur
2
retournée par f(E) tend vers l’infini (+∞) lorsque MAX tend à gagner, et tend vers moins l’infini (-∞)
lorsque MIN tend à gagner. Nous supposons que MAX commence. Nous supposons également que
MAX est un programme d’IA implémentant la procédure MINIMAX à un niveau de profondeur de 5.
Indiquez la valeur heuristique dans chaque état (cercle) évalué. Les valeurs heuristiques des états les
plus profonds sont données dans le tableau. Quel coup MAX devra-t-il jouer (à gauche ou à droite) ?
Exercice #6
Le programme de Louis a construit l’arbre suivant :
Lorsqu’on fait une recherche dans cet arbre, on obtient un succès si on réussit à atteindre une feuille de
l’arbre ; on arrête alors la recherche. Une recherche qui ne permet pas d’atteindre une feuille échoue
(échec) et la recherche s’arrête. La fonction heuristique est décroissante, plus la valeur d’un nœud est
petite, plus il est estimé proche d’un état final.
3
1) Énumérer dans l’ordre les états visités (A, B, etc.) avec la technique du meilleur d’abord. Indiquer
pour chaque état la valeur heuristique. Indiquer aussi s’il s’agit d’un succès ou d’un échec.
2) Est-ce que l’intelligence artificielle garantit qu’on trouvera la meilleure solution ?
3) Considérer le même arbre et effectuer une recherche en utilisant la procédure Minimax. Cette fois,
les valeurs heuristiques des feuilles de l’arbre sont les gains obtenus par Max s’il jouait ces différents
coups. Le gagnant de ce jeu est celui qui a obtenu le plus de points. C’est à Max de commencer. Quelle
est la valeur heuristique associée à chaque état ? Quel coup devra jouer Max pour s’assurer le meilleur
gain ?