Cours d'Intelligence Artificielle Heuristique : Algorithmes et Recherche

Introduction au cours d'Intelligence Artificielle Heuristique

Ce document pédagogique de niveau Licence 3 en informatique aborde les méthodes et algorithmes de recherche heuristique en intelligence artificielle. Conçu par Bruno Bouzy au sein de l'UFR Mathématiques et Informatique de l'Université Paris Descartes, le support s'adresse aux étudiants en cours d'apprentissage des stratégies de résolution de problèmes complexes.

Présentation générale du support de cours

Le document se structure autour de plusieurs grands chapitres thématiques, débutant par une introduction aux notions de recherche heuristique pour progresser vers des techniques plus avancées telles que la recherche locale. L'approche pédagogique s'appuie sur des exemples concrets, notamment le célèbre problème du voyage en Roumanie et le jeu du taquin, permettant d'illustrer visuellement le fonctionnement des algorithmes présentés.

Les principales notions et algorithmes abordés

Le cours détaille plusieurs stratégies fondamentales de recherche dans les graphes et les espaces d'états :

• La recherche meilleur d'abord : Utilisation d'une fonction d'évaluation pour mesurer l'utilité d'un nœud et prioriser les développements.
• La recherche gloutonne : Stratégie se basant uniquement sur l'estimation du coût restant vers l'état final, sans remettre en cause ses choix passés.
• L'algorithme A* : Combinaison du coût réel depuis l'état initial et d'une heuristique admissible pour garantir l'optimalité de la solution.
• Les algorithmes de recherche locale : Modification itérative d'un état pour les problèmes d'optimisation où le chemin d'accès n'importe pas, illustrés notamment par le problème des n reines et l'ascension du gradient.

Notions d'heuristiques et d'optimalité

Une part importante du document est consacrée à la définition des heuristiques admissibles qui ne surestiment jamais le coût réel pour atteindre le but. Les étudiants y découvrent les notions de dominance entre heuristiques, ainsi que des méthodes pour concevoir des fonctions d'évaluation adaptées à partir de versions simplifiées de problèmes, comme le montre l'étude du taquin avec le nombre de pièces mal placées ou la distance de Manhattan.

Questions fréquentes

À quel niveau d'études ce cours est-il destiné ?

Ce support de cours est destiné aux étudiants en Licence 3 Informatique au sein de l'UFR Mathématiques et Informatique de l'Université Paris Descartes.

Qui est l'auteur de ce document pédagogique ?

Le document a été rédigé par Bruno Bouzy, enseignant-chercheur rattaché à l'Université Paris Descartes.

Quels sont les exemples pratiques utilisés pour illustrer les algorithmes ?

Le cours utilise principalement le problème de la recherche d'itinéraire en Roumanie, le jeu du taquin pour les heuristiques admissibles, ainsi que le problème des n reines pour la recherche locale.

Télécharger Cours d'Intelligence Artificielle Heuristique : Algorithmes et Recherche pdf