TD 3 Algorithmes et Recherches Heuristiques : Algorithme A*

Introduction au troisième TD d'Intelligence Artificielle

Ce document pédagogique de niveau universitaire est consacré aux algorithmes de recherche heuristique en intelligence artificielle. Il propose une série d'exercices pratiques permettant d'appliquer concrètement des méthodes de recherche de chemin comme l'algorithme A* et l'évaluation d'heuristiques.

Structure et contenu des exercices

Le document s'articule autour de trois exercices principaux qui abordent la résolution de problèmes par recherche heuristique sous différents angles méthodologiques.

Exercice 1 : Application de l'algorithme A* en Roumanie

Le premier exercice reprend le problème classique du voyage en Roumanie. À partir d'une table de distances en ligne droite vers Bucarest et d'une carte détaillée comportant les coûts entre les villes, il est demandé d'appliquer l'algorithme A* en partant de Lugoj pour atteindre Bucarest. Pour chaque nœud exploré, il faut déterminer les valeurs des fonctions f, g et h, tout en gérant les doublons d'états selon la plus petite valeur de f.

Exercice 2 : Analyse d'heuristiques et recherche sur un graphe

Le deuxième exercice présente un graphe orienté comportant des sommets de A à I avec des coûts d'arcs spécifiés, ainsi que trois propositions d'heuristiques différentes nommées h1, h2 et h3. Les étudiants doivent analyser l'admissibilité de ces heuristiques, étudier leurs relations de dominance, tester la validité d'une heuristique combinée maximale, puis exécuter manuellement des algorithmes de recherche gloutonne et l'algorithme A* en utilisant différentes fonctions d'évaluation.

Exercice 3 : Restitution des coûts d'arcs à partir d'une trace d'exécution

Le troisième exercice propose un espace de recherche réduit où D est l'état initial et F l'état final. Une trace partielle de l'exécution de l'algorithme A* est fournie sous forme de listes successives de nœuds ouverts avec leurs valeurs de f. L'objectif est de retrouver par déduction les coûts de chaque arc du graphe et de vérifier si l'heuristique utilisée est admissible.

Compétences et notions abordées

Ce TD permet de manipuler les concepts fondamentaux de la recherche opérationnelle et de l'intelligence artificielle symbolique. Parmi les notions clés, on retrouve la définition formelle d'une heuristique admissible, la notion de dominance entre heuristiques, l'élaboration de fonctions d'évaluation combinées, ainsi que le suivi rigoureux des structures de données ouvertes dans les algorithmes de parcours de graphes.

Conseils pour l'utilisation de ce document

Il est recommandé de s'munir d'une feuille de brouillon et d'une calculatrice pour tracer les arbres de recherche étape par étape. Pour l'exercice 1, la construction méthodique d'un tableau de suivi des nœuds ouverts et fermés facilite grandement la résolution. Pour l'exercice 3, l'analyse rétroactive de la trace nécessite une compréhension fine de la formule fondamentale f = g + h.

Questions fréquentes

Quel est l'objectif principal de ce TD d'intelligence artificielle ?

Ce TD vise à maîtriser le fonctionnement de l'algorithme A* et l'utilisation des fonctions heuristiques à travers des applications pratiques sur des graphes et des cartes géographiques.

Quels types de problèmes sont traités dans le document ?

Le document aborde la planification de trajets routiers en Roumanie, l'analyse comparative de différentes heuristiques sur un graphe abstrait, et la rétro-ingénierie de coûts d'arcs à partir d'une trace d'exécution d'algorithme.

Faut-il connaître les valeurs des distances en ligne droite par cœur ?

Non, le document fournit explicitement un tableau récapitulatif des distances en ligne droite vers Bucarest ainsi que les cartes nécessaires pour chaque exercice.

Testez vos connaissances

Télécharger TD 3 Algorithmes et Recherches Heuristiques : Algorithme A* pdf