Modélisation d un problème et Algorithmes de recherche
12 pages
Français

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

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
12 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Niveau: Supérieur, Master, Bac+4
Modélisation d'un problème et Algorithmes de recherche Master M1 Miage - Université d'Orléans Christel LIFO (Laboratoire d'Informatique Fondamentale d'Orléans) Département Informatique - Faculté Sciences Université d'Orléans Ch. Vrain (Université d'Orléans) Algo de recherche 1 / 24 Plan Modélisation d'un problème Stratégies de résolution de problèmes I Stratégie irrévocable I Recherche par retour arrière I Recherche dans les graphes I Recherche heuristique Ch. Vrain (Université d'Orléans) Algo de recherche 2 / 24 Introduction aux algorithmes de recherche Les algorithmes de recherche constituent l'une des approches les plus puissantes pour la résolution de problèmes en IA Les algorithmes de recherche sont un mécanisme général de résolution de problème qui I se déroule dans un espace appelé espace d'é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 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 Condition d'arrêt spécifiant le but I état particulier I une liste d'états I condition vraie ou fausse sur les états 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 Ch.

  • stratégies de recherche stratégie irrévocable

  • mécanisme général de résolution de problème

  • configuration initiale du puzzle condition d'arrêt

  • algo de recherche

  • idée idée

  • laboratoire d'informatique fondamentale


Informations

Publié par
Nombre de lectures 46
Langue Français

Extrait

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

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents