TD 2 Algorithmes de recherche en IA : Exercices corrigés

Introduction au TD 2 d'intelligence artificielle

Ce document de travaux dirigés est consacré à l'étude des algorithmes de recherche en intelligence artificielle. Il propose une série d'exercices progressifs permettant d'aborder les notions fondamentales de modélisation de problèmes sous forme d'espace d'états et d'exploration par différents algorithmes de parcours.

Définitions fondamentales des algorithmes de recherche

La première partie du document demande de formaliser les concepts théoriques de base inhérents à la recherche opérationnelle et à l'intelligence artificielle. Les étudiants sont invités à définir précisément la notion d'état, l'espace d'états, l'arbre de recherche, les nœuds, ainsi que l'état but et les actions possibles. Sont également abordées la fonction de successeurs qui permet de générer les états voisins et la notion de coefficient de branchement qui caractérise la structure de l'arbre.

Modélisation de problèmes pratiques

Le deuxième exercice s'intéresse à la formalisation mathématique et logique de trois situations concrètes. Le premier problème concerne le coloriage de cartes avec quatre couleurs distinctes sous contrainte d'adjacence. Le deuxième problème met en scène le classique problème du singe et des bananes avec des caisses à déplacer dans une pièce. Le troisième problème propose une énigme de manipulation de récipients d'eau de capacités différentes pour obtenir un volume précis d'un litre.

Parcours de graphes et d'arbres de recherche

Les exercices suivants plongent directement dans l'application pratique des stratégies d'exploration de graphes. À partir d'une carte comportant des nœuds interconnectés de A à I avec des coûts de déplacement, le document demande de déterminer l'ordre de visite des nœuds selon plusieurs méthodes classiques : la recherche en largeur d'abord, la recherche à coût uniforme et la recherche en profondeur d'abord.

D'autres exercices explorent des espaces de recherche définis par des fonctions arithmétiques simples, comme le double et le double plus un, ou encore des manipulations de cubes sur une table. Ces cas d'étude permettent de comparer l'efficacité et l'ordre de parcours des algorithmes de recherche en profondeur limitée et de recherche en profondeur itérative.

Méthodes d'étude et de révision

Ce support de travaux dirigés constitue un outil d'entraînement direct pour s'approprier les mécanismes d'exploration algorithmique. Il est conseillé de dessiner systématiquement l'espace d'états avant d'appliquer les algorithmes de parcours pour éviter les erreurs de cheminement. La résolution méthodique des problèmes de modélisation aide également à mieux appréhender la transition entre un problème du monde réel et sa représentation formelle en intelligence artificielle.

Questions fréquentes

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

Ce document vise à entraîner les étudiants à modéliser des problèmes sous forme d'espaces d'états et à appliquer manuellement différents algorithmes de recherche non informée comme la largeur d'abord, la profondeur d'abord et le coût uniforme.

Quels types de problèmes sont modélisés dans les exercices ?

Le TD propose des problèmes variés incluant un coloriage de carte, l'énigme classique du singe et des bananes, des transvasements de récipients d'eau, ainsi que des graphes de navigation entre des sommets étriqués et des manipulations de cubes.

Quels algorithmes de parcours sont étudiés dans le document ?

Le document aborde la recherche en largeur d'abord, la recherche en profondeur d'abord, la recherche à coût uniforme, la recherche en profondeur limitée et la recherche en profondeur itérative.

Testez vos connaissances

Télécharger TD 2 Algorithmes de recherche en IA : Exercices corrigés pdf