Intelligence Artificielle AI - Prolog : TP3 4 PROLOG Résolution de problèmes par recherche dans un
Télécharger PDFRésolution de problèmes par recherche dans un graphe d’états
On considère des problèmes de type recherche d’un chemin entre un état initial Ei et un état final Ef, en utilisant des opérateurs de transition. L’ensemble des états atteignables à partir de Ei par l’application de tous les opérateurs possibles forme le graphe d’états, développé sous forme d’arborescence.
Recherche en profondeur dans un graphe d’états
Pour résoudre un problème, on définit :
- initial(Ei) : l’état initial connu.
- final(Ef) : l’état final à atteindre.
- op(Ec, Opx, Es) : un prédicat où Ec est l’état courant, Opx un opérateur de transition, et Es l’état résultant après application de Opx.
La recherche en profondeur suit ces principes :
- On atteint un état Ec à partir de Ei en utilisant une liste d’états mémorisés dans Chemin.
- L’application de l’opérateur Opx sur Ec produit un nouvel état Es.
- Lop est la liste des opérateurs à appliquer depuis Es pour atteindre Ef.
La définition du prédicat rechPf (recherche en profondeur) est :
rechPf(Ec, Ef, Chemin, Lop) :-
op(Ec, Opx, Es),
\+ member(Es, Chemin), % Évite les cycles
rechPf(Es, Ef, [Es|Chemin], [Opx|Lop]).
Les paramètres sont :
- Liste des états depuis Ei.
- Liste des opérateurs jusqu’à Ef.
Définir le prédicat resoudre(S)
Ce prédicat génère la liste S des opérateurs nécessaires pour passer de l’état initial à l’état final. Il utilise rechPf avec les paramètres appropriés.
Le problème des flèches
Définition du problème
Six flèches sont initialement dans une configuration donnée (figure 1) et doivent être repositionnées selon une autre configuration (figure 2).
Modélisation du problème
Les deux états sont représentés par des chaînes de caractères :
- État initial : « hhhbbb » (flèches hautes suivies de flèches basses).
- État final : « bbbhhh » (flèches basses suivies de flèches hautes).
Les opérateurs de transition sont :
- R1 : Retourner deux flèches hautes adjacentes (« hh » → « bb »).
- R2 : Retourner une flèche haute et une basse adjacentes (« hb » → « bh »).
- R3 : Retourner une flèche basse et une haute adjacentes (« bh » → « hb »).
- R4 : Retourner deux flèches basses adjacentes (« bb » → « hh »).
Prédicat rempl(S1, S2, L1, L2)
Ce prédicat vérifie si le remplacement de la sous-liste S1 par S2 dans la liste L1 produit L2. Il permet d’appliquer les opérateurs de transition.
Définition des prédicats initial, final et op
Pour le problème des flèches, on définit :
initial("hhhbbb").
final("bbbhhh").
op(Etat, R1, NouveauEtat) :-
rempl("hh", "bb", Etat, NouveauEtat).
op(Etat, R2, NouveauEtat) :-
rempl("hb", "bh", Etat, NouveauEtat).
op(Etat, R3, NouveauEtat) :-
rempl("bh", "hb", Etat, NouveauEtat).
op(Etat, R4, NouveauEtat) :-
rempl("bb", "hh", Etat, NouveauEtat).
Le problème de la simplification d’un nombre
Définition du problème
On souhaite simplifier une liste de chiffres (exemple : 3413242341) jusqu’à obtenir une liste vide. Les règles de simplification sont :
- R1 : Supprimer deux chiffres adjacents identiques.
- R2 : Permuter deux chiffres adjacents si la valeur absolue de leur différence est supérieure à 1.
- R3 : Remplacer la séquence (n, n-1, n) par (n-1, n, n-1).
Résolution du problème
On définit les prédicats initial, final et op pour ce problème, puis on utilise resoudre(S) pour trouver une solution.
Amélioration de la recherche en profondeur
La recherche en profondeur peut être optimisée en explorant tous les opérateurs applicables à chaque état. Si un opérateur mène directement à l’état final, il est privilégié. Sinon, on applique le premier opérateur disponible.
Prédicat resoudre+
Ce prédicat amélioré utilise rechPf+, qui implémente cette stratégie optimisée.
Pour aller plus loin
Une optimisation supplémentaire consiste à calculer une distance entre deux états pour chaque problème. Le prédicat de recherche choisit alors l’opérateur qui mène à l’état le plus proche de l’état final.
FAQ
Qu’est-ce qu’un graphe d’états ?
Un graphe d’états est une représentation des états possibles d’un problème, où chaque nœud correspond à un état et les arêtes représentent les transitions entre états via des opérateurs.
Comment éviter les cycles dans une recherche en profondeur ?
On mémorise les états déjà visités dans une liste (exemple : Chemin) et on vérifie avant chaque application d’opérateur que l’état résultant n’y figure pas déjà.
Quelle est la différence entre rechPf et resoudre+ ?
rechPf applique le premier opérateur disponible, tandis que resoudre+ explore tous les opérateurs applicables et privilégie celui qui mène directement à l’état final.