Université Batna2, Master 1 IAM, Méthodes pour l’intelligence artificielle

Exercices sur les Méthodes de résolution de problèmes

Exercice 1

Soit le graphe suivant avec A nœud de départ et I le nœud d’arrivée ( les nœuds sont développés
selon l’ordre alphabétique) :

A 5 H

5 C 3

6 2 F 4

D 3 3 G

2 E 5 4 3 I

B 5

Pour les algorithmes suivants :

- Recherche en profondeur d’abord,

- Recherche en largeur d’abord,
- Recherche à coût uniforme.

Donner :
- L’ordre des nœuds explorés,
- Le chemin trouvé ainsi que son coût,
- La structure de donnée utilisée pour chaque algorithme,
- La complexité en espace pour chaque algorithme.
- L’optimalité de chaque algorithme

Exercice 2

Considérons les graphes suivants. Le coût de chaque connexion est indiqué sur les arrêtes.
1. Le but est de trouver le chemin le plus court de S vers G

Nœud S A B C D E F G
h 11.0 10.4 6.7 4.0 8.9 6.9 3.0 0

A 1 B 4 C
2
S 2 5 G
5 3
D 2 E 4 F

2020/2021
 a. Appliquez la recherche gloutonne.
b. Appliquez la recherche A*.

2. Discuter l’admissibilité de l’heuristique :

Etat h1 h2
A 4 3
B 2 2
C 6 5
D 2 1
S 3 2

Exercice 3

Soit le problème suivant :

« Colorier la carte ci-dessous de façon à ce que les pays adjacents ne soient pas de la même couleur,
et en sachant que vous avez à votre disposition 3 couleurs distinctes »
1. Donnez l’état initial, le but, la fonction successeur et la fonction de coût.
2. Développer le graphe d’état jusqu’à 2 niveaux.

P1
P3 P4

P2
P5

Exercice 4

Soit le jeu du taquin en version 8 ; A gauche une situation de départ quelconque, et à droite la
situation but désirée.

7 2 4 1 2 3
5 6 4 5 6
8 3 1 7 8

1. Proposez une modélisation des états du jeu

2. En utilisant cette modélisation, écrivez les états de départ et de fin illustrés sur la figure.
3. Quel sont les actions possible dans ce jeux ?
4. Quel est le facteur de branchement moyen dans l'arbre du jeu ? (pour cela identifiez le nombre
d'actions possibles dans les différentes positions possibles pour le carré vide.)
5. Nous proposons de résoudre le ce problème en utilisant une stratégie A*. Pour cela, nous
utiliserons la fonction heuristique suivante : h : le nombre de pièces mal placées.
 5.1. Développez l'arbre du problème à la profondeur 2, en indiquant sur chaque nœud les valeurs
de h et de g (g est le cout du chemin parcouru, ici c'est le nombre de mouvements effectués).
6. Proposez une autre fonction heuristique admissible, et refaites la question précédente.

Exercice 5

Nous considérons un monde avec 4 pions (A, B C, D) non superposables. Ils peuvent être arrangés
dans n'importe quel ordre, sauf que A qui ne peut pas être plus à droite que D. Par exemple, ABCD
et CBAD sont deux états possibles du monde, tandis que DCBA et CDAB ne sont pas possibles. Le
monde peut être manipulé par une action de la forme echange(x; y) qui échange les pions des
positions x et y. Par exemple echange(1,2) transforme BCAD dans CBAD. Seules les actions
echange(1,2), echange(2,3) et echange(2,4) sont autorisées. Ils donnent un successeur uniquement si
la situation atteinte est possible.
1. Dessinez le graphe d'états.
2. On suppose que l'état de départ est ADBC et l'état que l'on veut atteindre est CBAD. On suppose
que chaque action coûte 1. Donnez une "bonne" heuristique h admissible (une heuristique qui ne
surestime pas le coût) pour ce problème. Remarquez que chaque action déplace 2 pions.
3. Appliquez la recherche gloutonne avec votre heuristique. Ne considérez pas les nœuds déjà
développés. En cas d'égalité choisissez un nœud à développer au hasard.

Exercice 6

Soit l'arbre de jeu suivant :

1. Appliquez l'algorithme Min-Max sur cet arbre. Quelle est la valeur finale de l’algorithme.
2. Appliquez l'algorithme Alpha-Beta sur cet arbre. Préciser les branches coupées et les valeurs α-β
au niveau de chaque nœud.

Exercice 7

Le morpion est un jeu de réflexion qui se joue sur une grille carrée de 3x3 cases où deux joueurs
s'affrontent. Ils doivent remplir chacun à leur tour une case de la grille avec le symbole qui leur est
attribué : ‘O’ ou ‘X’. Le gagnant est celui qui arrive à aligner trois symboles identiques,
horizontalement, verticalement ou en diagonale. Soit la configuration suivante du jeu illustrée sur la
figure ci-dessous. C'est au joueur X de jouer.
1. Etablissez l'arbre des configurations du jeu depuis cette configuration jusqu'à la fin de la partie.
2. En utilisant le principe de l'algorithme MinMax, quel sera le prochain coup que jouera X depuis la
configuration ci-dessous.
Pour les valeurs des états finaux vous utiliserez les valeurs suivantes : 1 pour gagné, 0 pour nul et -1
pour perdu.

Exercice 8

a. Utiliser l’algorithme génétique pour trouver le maximum de la fonction suivante :

f(x) = x2 + 1 avec 0 < x < 31 ;

b. Résoudre le problème du voyageur de commerce en utilisant un algorithme génétique.

L'application exacte consiste à trouver la distance la plus courte pour visiter cinq villes, sans
visiter une ville plus d'une fois, et retourner à la ville de départ. Le tableau ci-dessous montre
les distances entre chaque ville en kilomètres.
Ville 1 Ville 2 Ville 3 Ville 4 Ville 5
Ville 1 0 2 6 12 5
Ville 2 2 0 4 8 1
Ville 3 6 4 0 3 3
Ville 4 12 8 3 0 10
Ville 5 5 1 3 10 0

Lors de l'initialisation, chaque individu est représenté par un vecteur de permutation

comportant une représentation entière d'un itinéraire entre les cinq villes sans aucune
répétition. Exple : 1 3 4 5 2 1

La fonction fitness du chromosome est définie par la somme globale de toutes les distances
dans le vecteur de permutation. Plus la distance totale est petite, plus la fonction fitness de
l'individu est élevée.