TD Ia

Université de Monastir
Département Informatique
Enseignant responsable : Mariem Gzara
ISIMM-LI2-2022
Intelligence artificielle
Exercice 1
Le problème des ponts de königsberg consiste à trouver dans la configuration
suivante, un chemin qui part d’un point, traverse tous les ponts une et une seule fois et
revient au même point. Nous avons 6 ponts qui lient les deux iles aux deux rives de la
rivière et le pont 1 lie les deux îles.
Pour formuler précisément le problème sous la forme de parcours d'un espace de

recherche, répondre aux questions suivantes :
1. Comment est défini un état ?
2. Quel est l'état initial en sachant que le visiteur se trouve sur ile 1?
3. Quelles actions permettent de passer d'un état à un autre ?
4. Quel est l'état but ?
Exercice 2
On considère le problème de manipulation des blocs. On dispose de trois cubes A, B

et C à manipuler et un bras manipulateur à programmer. Le but recherché est de
passer de l’état initial (a) à l’état final (b). Le bras transporte un cube à la fois. Il place
un cube soit sur la table, soit au dessus d’un bloc. Seul le cube au sommet du bloc
peut être déplacé.
L’état initial est {(C,A),(B)}. L’état but est {(A,B,C)}.

1. Quelles actions permettent de passer d'un état à un autre ?
2. Quel est le nombre d’états possibles ?
3. Représenter l’espace d’états.
4. Donner une solution à ce problème en appliquant le DFS.
1
Exercice 3 :
Ce jeu se joue à deux. La situation de départ est un nombre donné d’allumettes (ce
nombre sera appelé la dimension du jeu), associé à l’indication du joueur qui doit
commencer le jeu. Chacun des joueurs retire alors à tour de rôle 1,2 ou 3 allumettes
parmi les allumettes encore disponibles. Le joueur qui gag
gagne
ne est celui qui réussit à
retirer la (ou les) dernière(s) allumette(s).
1) Donner le graphe d’espace d’état d’un jeu de dimension 5.
2) Une fonction cout-chemin

chemin est
est-elle
elle nécessaire pour la formalisation de notre
problème ?
Exercice 4 :
Considérez un espace d’états dans lequel l’état initial est 1 et la fonction successeur
pour un nœud n retourne deux états conten
contenant les entiers 2n et 2n + 1.
1. Dessinez la partie de l’espace d’états pour les états de 1 à 15.

2. Supposez que l’état but soit 11. Donnez l’ordre de parcours des nœuds pour les
algorithmes :
a. Largeur
argeur d’abord
b. Profondeur
rofondeur d’abord
c. Profondeur
rofondeur d’abord limitée à 2
Exercice 5 :
Soit le graphe suivant, la valeur porté
portée sur
ur chaque arc correspond au coût de passage
d’une extrémité de l’arc à l’autre. On souhaite calculer
ler le plus court chemin de A à J.
On a de plus la fonction heuristique h qui estime le coûtt pour atteindre J depuis

de
chaque sommet. h est donné
donnée par le tableau ci-dessous.
2
A B C D E F G H I J
30 26 20 21 25 10 12 8 5 0
Le déroulement d’un algorithme doit être représenté sous la forme suivante :

Étape numéro :
États ouverts (découverts et non traités) par ordre de priorité décroissante.
État choisi
États successeurs de l’état choisi et les calculs effectués
1. Appliquez l’algorithme Best-First Search sur ce graphe. Montrer à chaque étape,
les états en attente, l’état sélectionné et les calculs associés comme le coût.
2. Appliquez l’algorithme A* avec la fonction h sur ce graphe. Montrer à chaque
étape, les états en attente, l’état sélectionné et les calculs associés comme le coût.
Exercice 6 :
Donnez l’état initial, le but, la fonction successeur et la fonction de coût pour chacun
des problèmes suivants :
1. Vous devez colorier une carte de façon à ce que les pays adjacents ne soient pas
de la même couleur, et en sachant que vous avez à votre disposition 4 couleurs
distinctes.
2. Un singe mesurant 1 mètre se trouve dans une pièce de 3 mètres de hauteur.
Une banane est suspendue au plafond de cette pièce, et le singe aimerait bien
avoir cette banane. La pièce contient également 2 caisses qu’il peut déplacer et
sur lesquelles il peut monter, chaque caisse mesurant 1 mètre
3. On a trois récipients pouvant contenir respectivement 3, 8 et 12 litres, et un
robinet d’eau. On peut remplir les récipients, ou verser entièrement leur contenu
dans un autre récipient ou sur le sol. Nous voulons obtenir exactement 1 litre
d’eau
Exercice 7 :
Considérez l’espace de recherche suivant (D est l’état initial, F est l’état final) :
3
Pour chaque nœud est indiquée la valeur de l’heuristique h. On veut récupérer le
coût de chaque arc entre deux nœuds. Pour cela nous disposons d’une trace de
l’algorithme A∗.
Pour chaque pas de l’algorithme est indiquée la liste des nœuds encore à traiter avec
la valeur f = g+h. Si un nœud peut apparaître deux fois avec deux valeurs de f
différentes, on conserve seulement celui avec la meilleure (la plus petite) valeur de f.
[(D, f = 1)]
[(B, f = 7), (A, f = 8)]
[(A, f = 8), (C, f = 10)]
[(C, f = 10)]
[(E, f = 12), (F, f = 15)]
[(F, f = 14)]
Exercice 8:
Dans l’espace de recherche ci-dessous, le nombre placé à côté de chaque lien dénote
le coût associé au lien entre les nœuds et h est le coût estimé du nœud jusqu’au but
final G.
4
Donner l’ordre dans lequel les nœuds sont visités lorsqu’on utilise A*. Donner alors
f(n) pour chacun des nœuds n.
Exercice 9 :
Un singe situé à la position vectorielle « a » dans le plan du sol veut attraper des
bananes situés en hauteur et à la position vectorielle « c » (a≠c). Pour y arriver, il
utilise une boite située initialement à la position vectorielle « b » (b≠a, b≠c).
On essaie de résoudre ce problème par une approche espace d’états. Pour cela, on
utilise les quatre opérateurs suivants :
(W,0,Y,Z) aller(U) (U,0,Y,Z) U≠W
(W,0,W,Z) pousser en (V) (V,0,V,Z) U≠W
(W,0,W,Z) grimper (W,1,W,Z)
(c,1,c,0) attraper (c,1,c,1)
W, Y, Z, U et V sont des variables alors que a,b et c sont des constantes.

Le premier terme du quadruplet représente la position du singe, le troisième celle de
la boite.
Le deuxième et le quatrième terme prennent la valeur 0 ou 1 suivant que le singe est
sur le sol ou sur la boite et les bananes libres ou prises par le singe.
1. Donner l’espace complet des états par application des différents opérateurs.
2. Une fonction cout-chemin est-elle nécessaire pour la formalisation de notre
problème ? si oui, laquelle ?
3. Résoudre le problème ainsi formulé en appliquant une recherche en largeur
d'abord.

TD Ia

Transféré par

Droits d'auteur :

Formats disponibles

TD Ia

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

TD Ia

Transféré par

Droits d'auteur :

Formats disponibles

Université de Monastir

Pour formuler précisément le problème sous la forme de parcours d'un espace de

On considère le problème de manipulation des blocs. On dispose de trois cubes A, B

L’état initial est {(C,A),(B)}. L’état but est {(A,B,C)}.

1) Donner le graphe d’espace d’état d’un jeu de dimension 5.

2) Une fonction cout-chemin

1. Dessinez la partie de l’espace d’états pour les états de 1 à 15.

On a de plus la fonction heuristique h qui estime le coûtt pour atteindre J depuis

Le déroulement d’un algorithme doit être représenté sous la forme suivante :

[(B, f = 7), (A, f = 8)]

[(A, f = 8), (C, f = 10)]

[(E, f = 12), (F, f = 15)]

W, Y, Z, U et V sont des variables alors que a,b et c sont des constantes.

Vous aimerez peut-être aussi