Travaux Dirigés d'Intelligence Artificielle n°3 : Algorithmes de recherche
Introduction au document
Ce document de travaux dirigés est destiné aux étudiants en Master 1. Il aborde la thématique fondamentale des algorithmes de recherche en intelligence artificielle à travers quatre exercices pratiques couvrant des concepts variés tels que l'espace d'états, les arbres de recherche, les heuristiques et l'évaluation de stratégies algorithmiques.
Présentation du contenu et des exercices
Le sujet s'ouvre sur un premier exercice consacré à l'analyse d'un espace de recherche sous forme d'arbre. Le facteur de branchement est noté b, et l'exercice demande d'étudier le nombre de nœuds générés ainsi que la taille maximale de la liste des nœuds à traiter selon différentes méthodes : la recherche en profondeur d'abord, la recherche en profondeur itérative et la recherche en largeur d'abord.
Le second exercice propose une application concrète sur une carte géographique modélisée sous forme de graphe où l'objectif est de trouver le chemin le plus court entre le nœud A et le nœud I. Les coûts de connexion entre les différents points sont spécifiés, de même qu'une table d'heuristiques pour chaque nœud. Les étudiants sont invités à analyser l'admissibilité de cette heuristique et à appliquer plusieurs méthodes de recherche, à savoir la recherche à coût uniforme, la recherche gloutonne et la recherche A*.
L'exercice suivant place l'étudiant dans un contexte algorithmique appliqué à la robotique d'intérieur. Un robot mobile doit livrer trois paquets identiques depuis sa position initiale vers trois emplacements différents (A, B et C). L'énoncé structure progressivement la modélisation formelle du problème en demandant de définir l'espace des états, l'état initial, l'état final, les actions, la fonction de coût et d'imaginer des heuristiques admissibles. Des variantes sont introduites au fil des questions, notamment pour prendre en compte des priorités de livraison ou des situations où le robot doit d'abord récupérer les objets avant de les acheminer.
Enfin, le dernier exercice est issu d'une épreuve d'examen de juin 2004. Il demande de concevoir des arbres de recherche comportant au plus 15 nœuds et au maximum 2 fils par nœud pour illustrer comparativement l'efficacité relative de la recherche A*, de la recherche en largeur d'abord, de la recherche en profondeur d'abord, de la recherche gloutonne et de la recherche à coût uniforme en fonction de l'admissibilité des heuristiques.
Notions et compétences travaillées
Ce support pédagogique permet de travailler des notions clés de l'intelligence artificielle symbolique et de la résolution de problèmes par la recherche. Parmi les concepts abordés figurent la complexité spatiale et temporelle des algorithmes, la notion d'optimalité, l'admissibilité des fonctions heuristiques, ainsi que la modélisation d'environnements réels sous forme d'états et d'actions.
Méthodes d'utilisation pour les révisions
Ce type de document se prête particulièrement à un travail personnel approfondi en amont des examens ou des séances de travaux dirigés. Il est conseillé de tracer schématiquement les arbres et graphes proposés sur papier, d'écrire explicitement les structures de données (comme la liste des nœuds ouverts et fermés) pour chaque étape des algorithmes de parcours, puis de confronter ses résultats aux définitions théoriques du cours d'intelligence artificielle.
Informations sur le document
Ce document s'intitule Travaux Dirigés Intelligence Artificielle n°3 pour le niveau Master 1 et comprend également un extrait d'examen daté de juin 2004. Il est rédigé en français et s'adresse aux étudiants suivant un cursus universitaire en informatique ou en intelligence artificielle.
Questions fréquentes
Quel est le sujet principal de ce document ?
Le document est centré sur les algorithmes de recherche en intelligence artificielle, abordant à la fois des aspects théoriques sur des arbres génériques et des applications pratiques sur des graphes et des problèmes de robotique.
À quel niveau d'études ce sujet est-il destiné ?
Le document est destiné aux étudiants en Master 1 d'intelligence artificielle, comme l'indique l'en-tête de la première page.
Quels types de méthodes de recherche sont étudiés dans les exercices ?
Les exercices mobilisent la recherche en profondeur d'abord, la recherche en profondeur itérative, la recherche en largeur d'abord, la recherche à coût uniforme, la recherche gloutonne et l'algorithme A*.
D'où provient le dernier exercice de la feuille ?
Le quatrième exercice est explicitement mentionné comme étant un extrait d'un examen de juin 2004.
Télécharger Travaux Dirigés d'Intelligence Artificielle n°3 : Algorithmes de recherche pdf
