Modélisation d'un problème et Algorithmes de recherche

Ensemble d’actions, souvent modélisées par des règles
MG! MD
Résoudre le problème
= Trouver une suite d’actions permettant de passer de l’état initial à un
état final
Plan
Modélisation d’un problème et Algorithmes de
recherche
Modélisation d’un problèmeMaster M1 Miage - Université d’Orléans
Stratégies de résolution de problèmes
I Stratégie irrévocable
Christel Vrain
I Recherche par retour arrière
Christel.Vrain@univ-orleans.fr I dans les graphes
I heuristiqueLIFO (Laboratoire d’Informatique Fondamentale d’Orléans)
Département Infor - Faculté Sciences
Université d’Orléans
Ch. Vrain (Université d’Orléans) Algo de recherche 1 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 2 / 24
Introduction aux algorithmes de recherche Modélisation d’un problème par graphes d’états
Espace du problème : ensemble des états possibles
Les algorithmes de recherche constituent l’une des approches les Etat initial : description du problème initial
plus puissantes pour la résolution de problèmes en IA
Condition d’arrêt spécifiant le but
Les algorithmes de recherche sont un mécanisme général de
I état particulierrésolution de problème qui
I une liste d’états
I se déroule dans un espace appelé espace d’états I condition vraie ou fausse sur les états
I explore systématiquement toutes les alternatives
I trouve la séquence d’étapes menant à la solution
Etat initial
Action
Test de solution
Ch. Vrain (Université d’Orléans) Algo de recherche 3 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 4 / 24Résoudre le problème
= Trouver une suite d’actions permettant de passer de l’état initial à un
état final
I modéliser les déplacements des chiffres
I Imodéliser les déplacements du blanc modéliser les déplacements du blanc
Modélisation d’un problème par graphes d’états Modélisation d’un problème par graphes d’états
Espace du problème : ensemble des états possibles
Etat initial : description du problème initial Espace du problème : ensemble des états possibles
Condition d’arrêt spécifiant le but Etat initial : description du problème initial
Ensemble d’actions, souvent modélisées par des règles Condition d’arrêt spécifiant le but
MG! MD Ensemble d’actions, souvent modélisées par des règles
où MG! MD
MG : conditions d’applications de la règle
MD : spécification du nouvel état engendré Résoudre le problème
= Trouver une suite d’actions permettant de passer de l’état initial à un
état final
Ch. Vrain (Université d’Orléans) Algo de recherche 4 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 4 / 24
Exemple : Problème du taquin ou puzzle-8 [Nilsson Exemple : Problème du taquin ou puzzle-8 [Nilsson
71] 71]
Exemple Exemple
2 8 3 1 2 3 2 8 3 1 2 3
1 6 4 8 4 1 6 4 8 4! !
7 5 7 6 5 7 5 7 6 5
Etat inital Etat final Etat inital Etat final
un état du problème : une configuration du puzzle un état du problème : une configuration du puzzle
espace du problème : ensemble de toutes les configurations espace du problème : ensemble de toutes les configurations
possibles (9! = 362 880) possibles (9! = 362 880)
état initial : configuration initiale du puzzle état initial : configuration initiale du puzzle
condition d’arrêt : donnée par l’état final condition d’arrêt : donnée par l’état final
actions : actions :
I modéliser les déplacements des chiffres
Ch. Vrain (Université d’Orléans) Algo de recherche 5 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 5 / 24I modéliser les déplacements du blanc
Exemple : Problème du taquin ou puzzle-8 [Nilsson Exemple : Problème du taquin ou puzzle-8 [Nilsson
71] 71]
Exemple Exemple
2 8 3 1 2 3 2 8 3 1 2 3
1 6 4 8 4 1 6 4 8 4! !
7 5 7 6 5 7 5 7 6 5
Etat inital Etat initalEtat final Etat final
un état du problème : une configuration du puzzle un état du problème : une configuration du puzzle
espace du problème : ensemble de toutes les configurations espace du problème : ensemble de toutes les configurations
possibles (9! = 362 880) possibles (9! = 362 880)
état initial : configuration initiale du puzzle état initial : configuration initiale du puzzle
condition d’arrêt : donnée par l’état final condition d’arrêt : donnée par l’état final
actions : actions :
I Imodéliser les déplacements des chiffres modéliser les déplacements des chiffres
I32 actions possibles les du blanc
Ch. Vrain (Université d’Orléans) Algo de recherche 5 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 5 / 24
au plus 4 actions applicables par état
Exemple : Problème du taquin ou puzzle-8 [Nilsson Stratégies de recherche et de raisonnement
71]
Exemple Stratégies de recherche
stratégie irrévocable
2 8 3 1 2 3 stratégie par tentatives
1 6 4 8 4
I! retour arrière
7 5 7 6 5 I stratégies par recherche dans les graphes
Etat inital Etat final F en largeur
F en profondeur
F recherche heuristique
un état du problème : une configuration du puzzle
espace du problème : ensemble de toutes les configurations Stratégies de raisonnement
possibles (9! = 362 880)
recherche guidée par les données - chaînage avantétat initial : configuration initiale du puzzle guidée par le but - chaînage arrièrecondition d’arrêt : donnée par l’état final
actions :
I modéliser les déplacements des chiffres
I les du blancCh. Vrain (Université d’Orléans) Algo de recherche 5 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 6 / 24
4 actions possibles
au moins deux actions applicablesStratégie irrévocable / retour arrière Stratégie irrévocable / retour arrière
Stratégie irrévocable / retour arrière Stratégie irrévocable
Structure de contrôle
composé des trois étapes suivantes :
Le choix d’une action n’est jamais remis en cause.
recherche des actions applicables sur l’état courant E
choix d’une action Ale
application de A sur E
Ch. Vrain (Université d’Orléans) Algo de recherche 7 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 8 / 24
Stratégie irrévocable / retour arrière Stratégie irrévocable / retour arrière
Stratégie irrévocable Stratégie irrévocable
Le choix d’une action n’est jamais remis en cause.Le choix d’une action n’est jamais remis en cause.
méthode du gradient) Exploration d’un unique chemin
utilisation d’une fonction d’évaluation f atteignant son maximum) intéressante si l’on dispose de "bonnes" connaissances guidant
(resp. son minimum) pour tout état satisfaisant la condition d’arrêtdans le choix de la règle à appliquer
connaissance globale / connaissance locale choix d’une action, si la valeur pour f du nouvel état est supérieure
solution / comment arriver à la solution. (resp. inférieure) ou égale à la valeur de l’état courant
Ch. Vrain (Université d’Orléans) Algo de recherche 8 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 8 / 24Stratégie irrévocable / retour arrière Stratégie irrévocable / retour arrière
Exemple : problème du taquin ou puzzle-8 Inconvénient
f(Etat)=< nbre_chif_mal_places´ /e´tat#final >
Si l’espace de recherche est concave, on risque d’atteindre des2 8 3 1 2 3
maxima locaux.1 6 4 8 4!
7 5 7 6 5
ExempleEtat initial Etat final
1 2 31 2 5
4 3 3 2
2 8 3 2 8 3 2 3 2 3 7 4 7 4*1 6 4 1 4 1 8 4 1 8 4 !
7 5 7 6 5 7 6 5 7 6 5 8 6 58 6 3
1 0 Etat initial Etat final
1 2 3 1 2 3
8 4 8 4
7 6 5 7 6 5 Toute règle applicable va augmenter la valeur de f.
si plusieurs actions maximisent f , on en choisit une au hasard.
Ch. Vrain (Université d’Orléans) Algo de recherche 9 / 24 Ch. Vrain (Université d’Orléans) Algo de recherche 10 / 24
Stratégie irrévocable / retour arrière Stratégie irrévocable / retour arrière
Retour arrière Exemple : problème du taquin ou puzzle-8
détection des cyclesIdée
profondeur maximale : 6Idée : Si une action sélectionnée ne permet pas d’aboutir à la solution,
les étapes de calcul qui ont suivi ce choix sont oubliés et une autre choix de la première règle applicable trouvée
action est choisie. I 1 : déplacement du blanc vers la gauche
I 2 : du blanc vers le haut
Istockage uniquement du chemin de l’état initial à l’état courant 3 : du blanc vers la droite
I 4 : déplacement