Intelligence Artificielle – TD 2
A LGORITHMES DE RECHERCHE EN IA
Exercice 1 - Donnez une définition pour chacun des termes suivants :
1. Etat 2. Espace d’états
3. Arbre de recherche 4. Nœud
5. But 6. Action
7. Fonction successeurs 8. Coefficient de branchement
Exercice 2 - 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 3 - Considérez la carte suivante. L’objectif est de trouver un chemin allant de A à I.
A H
5 C 3
5 2 F 4
6 G
3
3 3
D 4 I
2 5
5
E
B
Donner l’ordre de parcours des nœuds pour les algorithmes :
1. largeur d’abord
2. coût uniforme
3. profondeur d’abord
1
Exercice 4 - Considérez un espace de recherche dans lequel l’état initial est 1 et la fonction successeur pour un
nœud n retourne deux états contenant les entiers 2n et 2n + 1.
1. Dessiner la partie de l’espace de recherche contenant les nœuds de 1 à 15
2. Supposer que le but soit 11. Donner l’ordre de parcours des nœuds pour les algorithmes :
(a) largeur d’abord
(b) profondeur d’abord
(c) profondeur d’abord limitée à 2
(d) profondeur itérative
Exercice 5 - On est dans la situation initiale donnée sur la figure suivante : sur une table sont posés trois cubes,
les cubes A et B à même la table et le cube C sur le cube A. On suppose que la position des cubes sur la table les
uns par rapport aux autres et indifférencié (que B soit à droite ou à gauche de A ne fait aucune différence). On
veut atteindre l’état final. On a juste le droit de soulever un cube qui n’est pas recouvert par un autre cube et de
le reposer ailleurs.
Etat initial Etat final
C
C B
B A A
1. Dessiner l’espace de recherche de ce problème
2. Donner l’ordre de parcours des nœuds pour les algorithmes :
(a) largeur d’abord
(b) profondeur d’abord
(c) profondeur d’abord limitée à 3
(d) profondeur itérative
