Titre: IA
Auteurs: Maria MALEK
Ecole: EISTI
Résumé: L’objectif de ce chapitre est d’introduire les principes de la résolution d’un problème donné en utilisant un espace de recherche. Cet espace de recherche permet de recenser les états d’un système donné et de trouver parmi ces états une ou plusieurs solutions. Le passage d’un état à un autre se fait par l’application d’une action donnée. Nous verrons rapidement que le problème de recherche de l’état solution dans l’espace nous ramènera à développer un arbre de recherche et à définir une stratégie de recherche sur cet arbre. Le but de la recherche dans un tel arbre serait la diminution du temps de recherche en trouvant une stratégie qui converge rapidement vers la solution.
Nous allons dans un premier temps présenter les algorithmes de recherche classique : en profondeur et largeur qu’on appellera la recherche aveugle. Ce seront les algorithmes les plus coûteux évidemment en temps ou en espace car ils ont tendance à développer l’arbre complet pour aboutir à une solution où à l’ensemble de solutions. Ensuite, nous étudions l’algorithme A* qui intègre une heuristique courant le développement de l’arbre de recherche ; cette heuristique permettra d’élaguer un ensemble de branches de l’arbre et de converger rapidement vers une solution si cette solution existe. Dans la suite, nous définissons les notions utilisées à savoir : les états et les actions . Ensuite, nous montrons les techniques de résolution en effectuant une recherche dans un espace d’états. L’application la plus directe à ces méthodes sera les problèmes de planification pour lesquels on ne connaît pas d’algorithme général ; mais on sait qu’étant donnés, un état initial, un état final et un ensemble d’actions élémentaires valides nous permettant de passer d’un état à un autre, on doit trouver une séquence d’action à exécuter pour résoudre le problème.
Extrait du sommaire:
1.1 Introduction 3
1.2 Notions utilisées 4
1.2.1 Comment résoudre un problème de planification ? 4
1.3 Recherche aveugle 5
1.4 Les différents problèmes de planification 7
1.5 Introduction d’un coût 8
1.6 Recherche guidée 8
1.6.1 Propriétés d’une heuristique 8
1.6.2 Présentation de l’algorithme A* 9
1.7 Implémentation en Prolog 11
1.7.1 Le parcours en Profondeur d’abord 11
1.7.2 Le parcours en Largeur d’abord 11
1.7.3 La modélisation du problème du taquin 12
Télécharger le fichier PDF: IA