Intelligence Artificielle AI - Prolog : TP3 4 PROLOG (PROgrammation LOGique)
Télécharger PDFTP Prolog : Résolution de Problèmes
1. Étude du Code Prolog pour le Problème du Chou, de la Chèvre et du Loup
Modélisation du problème :
- État initial :
etatcourant(0, 0, 0, 0)(tous sur la rive 0) - État objectif :
etatcourant(1, 1, 1, 1)(tous sur la rive 1) - Opérateurs et contraintes :
- Ne pas laisser le chou et la chèvre seuls sur une rive (sans moi ni loup).
- Ne pas laisser la chèvre et le loup seuls sur une rive (sans moi ni chou).
- Transporter un seul élément à la fois (moi + un autre) ou moi seul.
Code Prolog Commenté et Corrigé
/* Représentation : 1 = rive droite, 0 = rive gauche.
Ordre des protagonistes : moi, chou, chèvre, loup. */
/* États impossibles : chou et chèvre seuls sur une rive, ou chèvre et loup seuls sur une rive */
etat_impossible(etat(Moi, Chou, Chevre, Loup)) :-
(Chou = 1, Chevre = 1, Moi \= Chou, Loup \= Chou) ; /* chou et chèvre seuls sur rive 1 */
(Chou = 0, Chevre = 0, Moi \= Chou, Loup \= Chou). /* chou et chèvre seuls sur rive 0 */
/* Transporter le chou */
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(0, 0, Chevre, Loup)) :-
Chou = 1, Moi = 1, \+ etat_impossible(etat(0, 0, Chevre, Loup)).
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(1, 1, Chevre, Loup)) :-
Chou = 0, Moi = 0, \+ etat_impossible(etat(1, 1, Chevre, Loup)).
/* Transporter la chèvre */
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(0, Chou, 0, Loup)) :-
Chevre = 1, Moi = 1, \+ etat_impossible(etat(0, Chou, 0, Loup)).
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(1, Chou, 1, Loup)) :-
Chevre = 0, Moi = 0, \+ etat_impossible(etat(1, Chou, 1, Loup)).
/* Transporter le loup */
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(0, Chou, Chevre, 0)) :-
Loup = 1, Moi = 1, \+ etat_impossible(etat(0, Chou, Chevre, 0)).
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(1, Chou, Chevre, 1)) :-
Loup = 0, Moi = 0, \+ etat_impossible(etat(1, Chou, 1, Loup)).
/* Transporter moi seul */
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(0, Chou, Chevre, Loup)) :-
Moi = 1, \+ etat_impossible(etat(0, Chou, Chevre, Loup)).
etat_suivant(etat(Moi, Chou, Chevre, Loup), etat(1, Chou, Chevre, Loup)) :-
Moi = 0, \+ etat_impossible(etat(1, Chou, Chevre, Loup)).
/* Recherche avec accumulateur */
possible(Initial, Initial, Chemin, Chemin).
possible(Initial, Objectif, Chemin, Resultat) :-
etat_suivant(Initial, EtatSuivant),
\+ member(EtatSuivant, Chemin),
possible(EtatSuivant, Objectif, [EtatSuivant | Chemin], Resultat).
/* Trouver un chemin */
trouver_chemin(Initial, Objectif, Chemin) :-
possible(Initial, Objectif, [Initial], Chemin).
/* Recherche en largeur (BFS) */
recherche_largeur(Initial, Objectif, Chemin) :-
cherche(Objectif, [[Initial]], Chemin).
cherche(Objectif, [[Objectif|Chemin]|_], [Objectif|Chemin]) :- !.
cherche(Objectif, [[Etat|Chemin]|AutresChemins], Solution) :-
findall([NouvelEtat, Etat|Chemin], etat_suivant(Etat, NouvelEtat), NouveauxChemins),
append(AutresChemins, NouveauxChemins, Chemins),
cherche(Objectif, Chemins, Solution).
/* Afficher le chemin */
but :- trouver_chemin(etat(0,0,0,0), etat(1,1,1,1), Liste), reverse(Liste, Resultat), write(Resultat).
Exemple d'Exécution
Consultez le prédicat but pour afficher une solution.
2. Problème des Cruches
2.1 Modélisation
- État initial :
etat(0, 0)(cruche de 8 litres vide, cruche de 5 litres vide) - État objectif :
etat(4, _)ouetat(_, 4)(4 litres dans une cruche) - Opérateurs :
- Remplir une cruche (8 ou 5 litres).
- Vider une cruche (8 ou 5 litres).
- Transvaser d'une cruche à l'autre jusqu'à ce qu'elle soit vide ou que la première soit pleine.
2.2 Code Prolog Commenté
/* Représentation : etat(Cruche8, Cruche5) */
/* États impossibles : aucun (tous les états sont valides) */
/* Remplir la cruche de 8 litres */
etat_suivant(etat(0, Q), etat(8, Q)) :- Q < 8.
/* Remplir la cruche de 5 litres */
etat_suivant(etat(Q, 0), etat(Q, 5)) :- Q < 5.
/* Vider la cruche de 8 litres */
etat_suivant(etat(Q, Y), etat(0, Y)) :- Q > 0.
/* Vider la cruche de 5 litres */
etat_suivant(etat(X, Q), etat(X, 0)) :- Q > 0.
/* Transvaser de la cruche de 8 à celle de 5 */
etat_suivant(etat(X, Y), etat(X1, Y1)) :-
X > 0, Y < 5,
X1 is X - (5 - Y), Y1 is 5,
X1 >= 0.
/* Transvaser de la cruche de 5 à celle de 8 */
etat_suivant(etat(X, Y), etat(X1, Y1)) :-
Y > 0, X < 8,
Y1 is Y - (8 - X), X1 is 8,
Y1 >= 0.
/* Recherche avec accumulateur */
possible(Initial, Initial, Chemin, Chemin).
possible(Initial, Objectif, Chemin, Resultat) :-
etat_suivant(Initial, EtatSuivant),
\+ member(EtatSuivant, Chemin),
possible(EtatSuivant, Objectif, [EtatSuivant | Chemin], Resultat).
/* Trouver un chemin */
trouver_chemin(Initial, Objectif, Chemin) :-
possible(Initial, Objectif, [Initial], Chemin).
/* Afficher le chemin */
but :- trouver_chemin(etat(0, 0), etat(4, _), Liste), reverse(Liste, Resultat), write(Resultat).
Exemple d'Exécution
Consultez le prédicat but pour afficher une solution.
FAQ
Comment définir les états initiaux et objectifs ?
Les états initiaux et objectifs sont représentés sous forme de faits Prolog. Par exemple, pour le problème des cruches, etat(0, 0) est l'état initial et etat(4, _) est l'état objectif où 4 litres sont dans une cruche.
Quelle est la différence entre recherche en profondeur et recherche en largeur ?
La recherche en profondeur explore un chemin jusqu'à son terme avant de revenir en arrière, tandis que la recherche en largeur explore tous les états possibles au même niveau avant de passer au niveau suivant.
Comment éviter les états déjà visités ?
Utilisez la prédication member(EtatSuivant, Chemin) pour vérifier si un état a déjà été exploré et l'exclure avec \+.