Intelligence Artificielle AI - Prolog : TD5 avec Correction – Prolog AI
Télécharger PDFBase de l’Intelligence Artificielle 2019-2020
PARTIE 1 – CUT
Question 1 : Écrire un prédicat element, de deux manières, avec et sans le cut (!), permettant de savoir si X est un élément de la liste L.
Version sans le cut
element(X, [X | _]).
element(X, [ _ | Q ]) :- element(X, Q).
?- element(c, [a, b, c, d]).
true ; false.
?- element(a, [a, b, c, d, a]).
true ; true ; false.
?- element(e, [a, b, c, d]).
false.
?- element(X, [a, b, c, d]).
X = a ; X = b ; X = c ; X = d ; false.
Version avec le cut
element2(X, [X | _]) :- !.
element2(X, [ _ | Q ]) :- element2(X, Q).
?- element2(c, [a, b, c, d]).
true.
?- element2(e, [a, b, c, d]).
false.
?- element2(X, [a, b, c, d]).
X = a.
Explications et différences
Sans le cut, le prédicat explore toutes les possibilités de la liste L pour vérifier si X en fait partie. Cela génère un arbre de résolution complet où chaque chemin est testé, même après avoir trouvé une solution.
Avec le cut, dès que X est trouvé en tête de liste, le prédicat s’arrête immédiatement grâce à !. Cela optimise la recherche en évitant d’explorer les autres éléments de la liste une fois la solution trouvée.
PARTIE 2 – RÉSOLUTION DE PROBLÈME
Question 2 : Écrivez un prédicat coloriage générant toutes les valeurs possibles de C1, C2, C3 et C4, puis vérifiant les contraintes de couleurs différentes pour zones contiguës.
couleur(vert).
couleur(jaune).
couleur(rouge).
coloriage(C1, C2, C3, C4) :-
couleur(C1), couleur(C2), couleur(C3), couleur(C4),
C1\==C2, C1\==C3, C1\==C4, C2\==C3, C3\==C4.
Question 3 : Optimisez le prédicat en vérifiant les contraintes dès que les variables sont instanciées.
coloriage(C1, C2, C3, C4) :-
couleur(C1), couleur(C2), C1\==C2,
couleur(C3), C1\==C3, C2\==C3,
couleur(C4), C1\==C4, C3\==C4.
PARTIE 3 – CASSE-TÊTE
Question 4 : Programme Prolog pour résoudre le cryptarithme HUIT + HUIT = SEIZE.
/* Première version : affectation puis test */
valeur(X) :- member(X, [0,1,2,3,4,5,6,7,8,9]).
hhs2([H,U,I,T,S,E,Z]) :-
valeur(H), H\==0,
valeur(S), S\==0, S\==H,
valeur(T), not(member(T, [H,S])),
valeur(E), not(member(E, [T,H,S])),
R1 is ((2*T - E)/10),
valeur(I), not(member(I, [E,T,H,S])),
valeur(Z), not(member(Z, [I,E,T,H,S])), R2 is ((2*I + R1 - Z)/10),
valeur(U), not(member(U, [Z,I,E,T,H,S])), R3 is ((2*U + R2 - I)/10),
2*H + R3 =:= E + 10*S.
PARTIE 4 – L’AGENCE DE VOYAGE
Question 6 : Clauses décrivant le catalogue des séjours.
catalogue(rome, 40, hotel, 240).
catalogue(rome, 40, camping, 170).
catalogue(rome, 40, habitant, 80).
catalogue(londres, 20, hotel, 200).
catalogue(londres, 20, camping, 180).
catalogue(londres, 20, habitant, 76).
catalogue(tunis, 25, hotel, 300).
catalogue(tunis, 25, camping, 160).
catalogue(tunis, 25, habitant, 84).
Question 7 : Prédicat voyage calculant le coût d’un séjour.
voyage(Ville, Duree, TypeHebergement, Cout) :-
catalogue(Ville, PrixTransport, TypeHebergement, CoutH),
Cout is Duree*CoutH + PrixTransport.
Question 8 : Prédicat voyage_eco vérifiant que le coût est inférieur à un maximum.
voyage_eco(Ville, Duree, TypeHebergement, Cout, CoutMax) :-
catalogue(Ville, PrixTransport, TypeHebergement, CoutH),
Cout is Duree*CoutH + PrixTransport, Cout < CoutMax.
FAQ
1. Pourquoi utiliser le cut dans un prédicat comme element ?
Le cut optimise la recherche en stoppant l’exploration dès qu’une solution est trouvée, réduisant ainsi le nombre de branches dans l’arbre de résolution.
2. Comment fonctionne l’heuristique dans la deuxième version du cryptarithme ?
L’heuristique consiste à tester les contraintes dès que les variables sont instanciées, notamment en commençant par les unités (T et E) avant de passer aux dizaines (U et I), ce qui limite les possibilités dès le début.
3. Que signifie not(member(X, Liste)) dans le prédicat hhs2 ?
Cela signifie que la valeur X ne doit pas être présente dans la liste Liste, assurant ainsi que chaque lettre représente un chiffre unique.