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

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