Exercices et corrigés d'algorithme A* et recherche heuristique
Introduction à la recherche heuristique et à l'algorithme A*
Ce document pédagogique propose une série d'exercices pratiques accompagnés de leurs corrigés détaillés, consacrés à la recherche heuristique et plus particulièrement à l'algorithme A*. Conçu pour le cours d'intelligence artificielle de l'hiver 2017, ce support aborde la manipulation formelle des fonctions d'évaluation, des listes d'exploration et des propriétés fondamentales des heuristiques.
Présentation du document et contexte académique
Le fichier se présente sous la forme d'un ensemble de planches d'exercices comprenant des énoncés précis et des corrections pas à pas. Il est issu d'un enseignement universitaire en informatique (sigle INF4230 - Intelligence Artificielle). La progression s'articule autour d'un cas d'étude filé permettant d'illustrer de manière concrète le fonctionnement des algorithmes de recherche sur graphe.
Contenu des exercices et concepts abordés
L'exercice principal du document met en scène un graphe d'états défini par une fonction successeur, une fonction heuristique et une fonction de validation du but. Les étudiants sont amenés à suivre le déroulement de l'algorithme A* en remplissant les listes d'exploration ouvertes (open) et fermées (closed), tout en calculant les valeurs des fonctions f et g à chaque itération.
Le document explore également la notion d'admissibilité d'une fonction heuristique. À travers une analyse comparative des coûts réels et des estimations fournies, le support démontre comment identifier une surestimation et les conséquences de cette dernière sur la garantie d'optimalité de l'algorithme. Enfin, une modification de la fonction de but est proposée pour observer le comportement d'exploration exhaustive lorsque la solution recherchée change de statut.
Méthode de travail recommandée
Ce support constitue un outil d'entraînement idéal pour s'approprier la mécanique de l'algorithme A*. Il est conseillé de redessiner le graphe à partir du tableau des successeurs avant de tenter de résoudre les itérations de manière autonome. La confrontation entre les résultats personnels et les corrections rédigées permet de cibler précisément les erreurs de calcul sur les coûts cumulés et estimés.
Questions fréquentes
Quel est le sujet principal traité dans ce document ?
Le document traite de la recherche heuristique et de l'exécution pas à pas de l'algorithme A* sur un graphe d'états.
À quel niveau d'études ce cours est-il destiné ?
Ce support est destiné à des étudiants universitaires en informatique suivant un enseignement d'intelligence artificielle de niveau supérieur.
Quelles informations retrouve-t-on dans le corrigé de l'exercice ?
Le corrigé détaille l'évolution des listes open et closed à chaque itération, les valeurs des fonctions f et g, le chemin solution final ainsi qu'une justification sur l'admissibilité de l'heuristique.
Testez vos connaissances
Question 1
Dans l'algorithme A*, que représente la valeur g(s) pour un état donné ?
- Le coût estimé pour aller de l'état actuel au but
- Le coût réel du chemin parcouru depuis l'état initial jusqu'à l'état actuel
- La somme du coût réel et du coût heuristique
- Le nombre total d'états explorés dans la liste closed
Réponse correcte : Le coût réel du chemin parcouru depuis l'état initial jusqu'à l'état actuel
Explication : La fonction g(s) correspond au coût cumulé pour atteindre l'état s depuis la racine, tandis que h(s) représente l'estimation vers le but et f(s) leur somme.
Question 2
Quelle condition caractérise une fonction heuristique admissible ?
Elle doit toujours surestimer le coût restant pour atteindre le but.
- Elle doit toujours surestimer le coût restant pour atteindre le but.
- Elle doit toujours être égale à zéro pour tous les états.
- Elle ne doit jamais surestimer le coût restant minimal pour atteindre un état but.
- Elle doit être strictement supérieure au coût réel des arêtes.
Réponse correcte : Elle ne doit jamais surestimer le coût restant minimal pour atteindre un état but.
Explication : Une heuristique est admissible si, pour tout état, h(s) est inférieur ou égal au coût réel optimal h*(s) menant au but.
Télécharger Exercices et corrigés d'algorithme A* et recherche heuristique pdf
