Algorithmes d’exploration (search)

Exercices suggérés

Luc Lamontagne

Hiver 2008

1. Complétez les exercices suivants du livre de Russell et Norvig :

· 3.7

· 3.8 a) et b).

2. Complétez les exercices suivants du livre de Russell et Norvig :

· 4.1

· 4.2

· 4.3

· 4.9

· 4.11

3. Quel algorithme d’exploration vous semble le plus adéquat pour les jeux suivants  (il est possible qu’aucun ne convienne):

• Tetris
• Pacman
• Backgammon
• Cracker Barrel

4. Donnez la séquence de nœuds visités dans l’arbre ci-dessous pour chacun des algos suivants :

· Largeur d’abord

· Coût uniforme

· Profondeur d’abord

· Itérative en profondeur

· Meilleur d’abord avare

· A*