Intelligence Artificielle AI - Prolog : TD 5 Prolog
Télécharger PDFArbre généalogique
Voici un programme Prolog décrivant un arbre généalogique :
homme(albert).
homme(marc).
homme(charles).
femme(sara).
pere(albert, marc).
pere(albert, charles).
pere(albert, sara).
Prédicats généraux à définir
À partir des prédicats ci-dessus, définissez les règles suivantes :
• enfant(X, Y) : X est un enfant de Y.
• fils(X, Y) : X est un fils de Y.
• fille(X, Y) : X est une fille de Y.
• frere-ou-soeur(X, Y) : X est frère ou sœur de Y (un individu ne peut pas être son propre frère ou sœur).
Manipulation de listes
1. Prédicat element(X, L)
Écrivez ce prédicat de deux manières : avec et sans le cut (!). Voici les deux versions possibles :
Version sans cut :
element(X, [X|_]).
element(X, [_|Reste]) :- element(X, Reste).
Version avec cut :
element(X, [X|_]).
element(X, [_|Reste]) :- element(X, Reste), !.
Explication et arbre de résolution
Le cut (!) permet d’éviter des calculs inutiles en bloquant les recherches alternatives dès qu’une solution est trouvée. Sans cut, Prolog explore toutes les possibilités, tandis qu’avec cut, il s’arrête après la première solution.
2. Prédicat inverse(L, L1)
Définissez un prédicat qui renverse une liste L pour obtenir L1 :
inverse([], []).
inverse([Tete|Queue], L1) :- inverse(Queue, L2), append(L2, [Tete], L1).
3. Prédicat compresse(L, L1)
Écrivez un prédicat qui supprime les doublons consécutifs dans une liste L tout en conservant l’ordre des éléments :
compresse([], []).
compresse([X], [X]).
compresse([X, X|Reste], L1) :- compresse([X|Reste], L1).
compresse([X, Y|Reste], [X|L1]) :- X \= Y, compresse([Y|Reste], L1).
Exemple d’utilisation
Consultez la liste suivante :
?- compresse([a,a,a,a,b,c,c,a,a,d,e,e,e,e], L1).
Résultat attendu : L1 = [a,b,c,a,d,e].
Coloriage d’une carte
Prédicat coloriage(C1, C2, C3, C4)
Définissez un prédicat pour colorier une carte avec les contraintes suivantes :
• Trois couleurs disponibles : vert, jaune, rouge.
• Deux zones contiguës doivent avoir des couleurs différentes.
Première version (génération puis vérification)
coloriage(C1, C2, C3, C4) :-
couleur(C1), couleur(C2), couleur(C3), couleur(C4),
C1 \= C2, C1 \= C3, C2 \= C4, C3 \= C4.
couleur(vert).
couleur(jaune).
couleur(rouge).
Deuxième version (vérification immédiate)
coloriage(vert, C2, C3, C4) :- C2 \= vert, C3 \= vert, C2 \= C3, C4 \= C2, C4 \= C3.
coloriage(jaune, C2, C3, C4) :- C2 \= jaune, C3 \= jaune, C2 \= C3, C4 \= C2, C4 \= C3.
coloriage(rouge, C2, C3, C4) :- C2 \= rouge, C3 \= rouge, C2 \= C3, C4 \= C2, C4 \= C3.
coloriage(C1, vert, C3, C4) :- C1 \= vert, C3 \= vert, C4 \= vert, C3 \= C4.
coloriage(C1, jaune, C3, C4) :- C1 \= jaune, C3 \= jaune, C4 \= jaune, C3 \= C4.
coloriage(C1, rouge, C3, C4) :- C1 \= rouge, C3 \= rouge, C4 \= rouge, C3 \= C4.
coloriage(C1, C2, vert, C4) :- C1 \= vert, C2 \= vert, C4 \= vert.
coloriage(C1, C2, jaune, C4) :- C1 \= jaune, C2 \= jaune, C4 \= jaune.
coloriage(C1, C2, rouge, C4) :- C1 \= rouge, C2 \= rouge, C4 \= rouge.
coloriage(C1, C2, C3, vert) :- C1 \= vert, C2 \= vert, C3 \= vert.
coloriage(C1, C2, C3, jaune) :- C1 \= jaune, C2 \= jaune, C3 \= jaune.
coloriage(C1, C2, C3, rouge) :- C1 \= rouge, C2 \= rouge, C3 \= rouge.
Conséquence de la modification
En déplaçant les tests de différence de couleurs dès que les variables sont instanciées, Prolog réduit le nombre de combinaisons à explorer, ce qui améliore l’efficacité du programme.
FAQ
1. Comment fonctionne le prédicat enfant(X, Y) ?
Ce prédicat est défini pour vérifier si X est un enfant de Y en combinant les règles fils et fille avec le prédicat pere.
2. Pourquoi utiliser le cut dans element(X, L) ?
Le cut optimise les performances en évitant les recherches inutiles après la première solution trouvée.
3. Quels sont les avantages de la vérification immédiate dans le coloriage ?
La vérification immédiate réduit le nombre d’options à tester, ce qui accélère la recherche des solutions valides.