Td 1 représentation et résolution de problème (1)

Intelligence Artificielle AI - Prolog : TD 1 Représentation et résolution de problème (1)

Télécharger PDF

Représentation et résolution de problèmes en informatique

1. Introduction

Le TD est organisé sur trois sessions avec des interventions d'étudiants au tableau.

Ce document présente uniquement le sujet du TD.

2. Résolution de problème par exploration d'espace d'états

2.1 Représentation du problème du Taquin (30 min)

Proposer une représentation d'un état du Taquin.

Définir des opérateurs permettant de passer d'un état à un autre.

Identifier une heuristique pour éviter d'explorer l'ensemble des états possibles.

2.2 Recherche heuristique : mise en œuvre de l'algorithme A*

L'algorithme A* utilise une heuristique minorante h(u) telle que h(u) ≤ h*(u), où h*(u) est le coût optimal d'un chemin vers l'état but (sinon h*(u) = +∞).

Algorithme A*

Initialisation :
OUVERTS ← {u₀} ; FERMES ← ∅ ; g(u₀) ← 0 ; u ← u₀
Itérer tant que [OUVERTS ≠ ∅ et u non terminal] :
1. Supprimer u de OUVERTS et l'ajouter à FERMES.
2. Itérer sur les nœuds successeurs v de u :
  Si [v ∉ (OUVERTS ∪ FERMES) ou g(v) > g(u) + coût(u, v)], alors :
  - g(v) ← g(u) + coût(u, v)
  - f(v) ← g(v) + h(v)
  - père(v) ← u
  - Ranger v dans OUVERTS, trié par ordre croissant de f(v), puis décroissant de g(v).
3. Si OUVERTS ≠ ∅, alors u ← tête(OUVERTS).
Si OUVERTS = ∅, alors le problème n'admet pas de solution.

Exemple de configuration initiale et but :

état Initial : 2 8 3 1 6 4 7 5
état But :     1 2 3 8 4 7 6 5

Appliquer cet algorithme au problème du Taquin en utilisant différentes heuristiques et tracer les structures et variables.

2.3 Résolution par décomposition de problèmes (30 min)

La décomposition d'un problème en sous-problèmes plus simples est applicable aux problèmes récursifs ou non.

Un algorithme de recherche aveugle pour un graphe ET/OU (hypergraphe particulier) sans circuit est le suivant :

Algorithme BSH (Backward Search Heuristique)

RESOLUS contient :
1. Les états terminaux.
2. Les états u où tous les successeurs v d'un connecteur S_i(u) sont dans RESOLUS.
INSOLUBLES contient :
1. Les états non terminaux sans successeur.
2. Les états u où pour tout connecteur S_i(u), il existe un successeur v dans INSOLUBLES.

Problème à résoudre : d

Sous-problèmes terminaux : b, c, e, l

Décomposer le problème selon les règles données et dessiner le graphe/arbre de décomposition.

Appliquer l'algorithme en traçant les structures et variables importantes.

FAQ

1. Qu'est-ce qu'une heuristique minorante dans A* ?

Une heuristique minorante est une fonction qui sous-estime le coût réel pour atteindre l'état but. Elle garantit que l'algorithme A* trouve un chemin optimal.

2. Comment éviter les circuits dans un graphe ET/OU ?

L'algorithme BSH utilise un majorant sur le rang des états pour borner l'espace exploré et éviter les circuits.

3. À quoi servent les ensembles OUVERTS et FERMES dans A* ?

OUVERTS contient les états à explorer, triés par priorité. FERMES stocke les états déjà traités pour ne pas les réévaluer.

Td 1 représentation et résolution de problème (1) - intellig

Représentation et résolution de problèmes en informatique

1. Introduction

2. Résolution de problème par exploration d'espace d'états

2.1 Représentation du problème du Taquin (30 min)

2.2 Recherche heuristique : mise en œuvre de l'algorithme A*

2.3 Résolution par décomposition de problèmes (30 min)

FAQ

1. Qu'est-ce qu'une heuristique minorante dans A* ?

2. Comment éviter les circuits dans un graphe ET/OU ?

3. À quoi servent les ensembles OUVERTS et FERMES dans A* ?

نموذج الاتصال

Td 1 représentation et résolution de problème (1) - intellig

Représentation et résolution de problèmes en informatique

1. Introduction

2. Résolution de problème par exploration d'espace d'états

2.1 Représentation du problème du Taquin (30 min)

2.2 Recherche heuristique : mise en œuvre de l'algorithme A*

2.3 Résolution par décomposition de problèmes (30 min)

FAQ

1. Qu'est-ce qu'une heuristique minorante dans A* ?

2. Comment éviter les circuits dans un graphe ET/OU ?

3. À quoi servent les ensembles OUVERTS et FERMES dans A* ?

Cela peut vous intéresser :

نموذج الاتصال