Intelligence Artificielle AI - Prolog : Projet intelligence artificielle
Télécharger PDFExercice 1 : Agence matrimoniale
Soit une agence matrimoniale disposant d'un fichier de candidats au mariage. Ce fichier est structuré sous forme de faits :
- homme(N, T, C, A) : N est le nom d'un homme, T sa taille (grande, moyenne ou petite), C la couleur de ses cheveux (blonds, bruns, roux, châtains), et A son âge (jeune, mur ou vieux).
- femme(N, T, C, A) : N est le nom d'une femme, T sa taille, C la couleur de ses cheveux, et A son âge.
- gout(N, M, L, S) : N aime le genre de musique M (classique, pop, jazz), le genre de littérature L (aventure, science-fiction, policier), et pratique le sport S (tennis, natation, jogging).
- recherche(N, T, C, A) : N recherche un partenaire de taille T, avec des cheveux de couleur C, et d'âge A.
1. Définir un ensemble de faits pour 10 hommes et 10 femmes
Voici un exemple de base de faits :
homme(alexandre, grande, blonds, jeune).
homme(bernard, moyenne, bruns, mur).
homme(charles, petite, châtains, vieux).
homme(david, moyenne, roux, jeune).
homme(eric, grande, châtains, mur).
homme(francois, petite, blonds, vieux).
homme(georges, moyenne, châtains, jeune).
homme(henri, grande, bruns, mur).
homme(isabelle, moyenne, roux, vieux).
homme(julien, petite, châtains, mur).
femme(marie, moyenne, châtains, jeune).
femme(laure, grande, blonds, mur).
femme(nathalie, petite, bruns, vieux).
femme(olivier, moyenne, roux, jeune).
femme(patricia, petite, châtains, vieux).
femme(quitterie, moyenne, châtains, mur).
femme(robertine, grande, blonds, jeune).
femme(sophie, moyenne, châtains, vieux).
femme(therese, petite, châtains, jeune).
femme(ursule, moyenne, châtains, mur).
2. Définir le prédicat convient-physiquement(X, Y)
Ce prédicat vérifie si les caractéristiques physiques de X correspondent aux critères de recherche de Y.
convient_physiquement(X, Y) :-
homme(X, TX, CX, AX),
femme(Y, _, _, _),
recherche(Y, TY, CY, AY),
TX = TY,
CX = CY,
AX = AY.
convient_physiquement(X, Y) :-
femme(X, TX, CX, AX),
homme(Y, _, _, _),
recherche(Y, TY, CY, AY),
TX = TY,
CX = CY,
AX = AY.
3. Définir le prédicat meme_gout(X, Y)
Ce prédicat vérifie si X et Y ont les mêmes goûts en musique, littérature et sport.
meme_gout(X, Y) :-
gout(X, MX, LX, SX),
gout(Y, MY, LY, SY),
MX = MY,
LX = LY,
SX = SY.
4. Programme pour déterminer les couples assortis
couple_assorti(X, Y) :-
convient_physiquement(X, Y),
meme_gout(X, Y).
Exercice 2 : Cryptarithmétique
Résoudre l'addition suivante en Prolog : LOGIC + LOGIC = PROLOG, où chaque lettre représente un chiffre unique (0 à 9) et la première lettre de chaque mot ne peut pas être 0.
Solution en Prolog
cryptarithme([L, O, G, I, C], [P, R, O, L, G]) :-
L + O = P avec_carry(0, CO),
O + G = R avec_carry(CO, CO1),
G + I = O avec_carry(CO1, CO2),
I + C = L avec_carry(CO2, CO3),
C + CO = G avec_carry(CO3, CO4),
CO4 = 0,
distinctes([L, O, G, I, C]),
L \= 0, P \= 0.
avec_carry(Somme, Carry) :-
Somme =< 9,
Carry is 0.
avec_carry(Somme, Carry) :-
Somme > 9,
Carry is 1,
Somme1 is Somme - 10,
Somme = Somme1 + 10.
distinctes([]).
distinctes([X]) :-
X \= _.
distinctes([X|Xs]) :-
distinctes(Xs),
\+ member(X, Xs).
Bonus : Vérification avec ZERO + ZERO = RIEN
cryptarithme([Z, E, R, O], [R, I, E, N]) :-
Z + E = R avec_carry(0, CZ),
E + R = I avec_carry(CZ, CE),
R + O = E avec_carry(CE, CR),
O + CR = N avec_carry(CR, C),
C = 0,
distinctes([Z, E, R, O]),
Z \= 0, R \= 0.
Exercice 3 : Coloriage de carte
Définir un prédicat pour colorier une carte avec trois couleurs (vert, jaune, rouge) et garantir que deux zones contiguës ont des couleurs différentes.
1. Coloriage avec vérification en deux étapes
coloriage(C1, C2, C3, C4) :-
findall(C, (member(C, [vert, jaune, rouge])), Couleurs),
permutation(Couleurs, [C1, C2, C3, C4]),
C1 \= C2,
C2 \= C3,
C3 \= C4,
C1 \= C3,
C2 \= C4.
2. Coloriage avec vérification immédiate des contraintes
coloriage(C1, C2, C3, C4) :-
C1 \= C2,
C2 \= C3,
C3 \= C4,
C1 \= C3,
C2 \= C4,
membre(C1, [vert, jaune, rouge]),
membre(C2, [vert, jaune, rouge]),
membre(C3, [vert, jaune, rouge]),
membre(C4, [vert, jaune, rouge]).
membre(X, L) :- member(X, L).
Conséquence
En déplaçant les tests de différence dès que les couleurs sont instanciées, le programme devient plus efficace car il élimine rapidement les solutions non valides.
Exercice 4 : Nombres en triangle
Placer les nombres de 1 à 6 en triangle sans répétition, de sorte que la somme des trois nombres sur chaque côté soit égale.
1. Prédicat choisir(X, L)
choisir(X, L) :- member(X, L).
2. Prédicat permutation(L, LP)
permutation(L, P) :- permutation(L, P, []).
permutation([], P, P).
permutation([T|L], P, Acc) :-
permutation(L, P1, Acc),
append(Acc1, [T|Acc2], P1),
append(Acc1, Acc2, Acc),
permutation(Acc2, P, [T|Acc1]).
3. Prédicat generer(L)
generer(L) :- permutation([1, 2, 3, 4, 5, 6], L).
4. Prédicat tester(L)
tester([N1, N2, N3, N4, N5, N6]) :-
N1 + N2 + N5 = N3 + N6 + N4.
5. Prédicat solution(X)
solution(X) :- generer(X), tester(X).
6. Nombre de solutions
nombre_solutions(N) :- findall(X, solution(X), Sol), length(Sol, N).
Exercice 5 : Parcours de graphe
1. Base de faits pour le graphe
arc(bachant, eclaibes).
arc(eclaibes, denain).
arc(denain, gommegnies).
arc(denain, croix).
arc(gommegnies, aulnoye).
arc(denain, aulnoye).
arc(aulnoye, croix).
2. Règles pour les questions
chemin(A, B, Liste) :- chemin(A, B, [A], Liste).
chemin(A, A, _, []).
chemin(A, B, Visite, [A|Liste]) :-
arc(A, C),
\+ member(C, Visite),
chemin(C, B, [C|Visite], Liste).
Exemple de questions
peut_aller(A, B) :- chemin(A, B, _).
comment_aller(A, B, Liste) :- chemin(A, B, Liste).
chemins_vers(Aulnoye, Liste) :- chemin(_, Aulnoye, Liste).
chemin_par_denain(Eclaibes, Gommegnies, Liste) :-
chemin(Eclaibes, Denain, Liste1),
chemin(Denain, Gommegnies, Liste2),
append(Liste1, Liste2, Liste).
chemin_min_etapes(A, B, Liste) :-
chemin(A, B, Liste),
length(Liste, N),
N >= 3.
3. Base de faits avec coût
arc(bachant, eclaibes, 5).
arc(eclaibes, denain, 3).
arc(denain, gommegnies, 7).
arc(denain, croix, 4).
arc(gommegnies, aulnoye, 6).
arc(denain, aulnoye, 2).
arc(aulnoye, croix, 8).
4. Prédicat chemin(A, B, Liste, Cout)
chemin(A, B, Liste, Cout) :- chemin(A, B, [A], Liste, Cout).
chemin(A, A, _, [], 0).
chemin(A, B, Visite, [A|Liste], Cout) :-
arc(A, C, Coût),
\+ member(C, Visite),
chemin(C, B, [C|Visite], Liste, Cout1),
Cout is Coût + Cout1.
5. Questions avec coût
chemins_par_denain(Bachant, Gommegnies, Liste, Cout) :-
chemin(Bachant, Denain, Liste1, Cout1),
chemin(Denain, Gommegnies, Liste2, Cout2),
append(Liste1, Liste2, Liste),
Cout is Cout1 + Cout2.
chemins_coût_supérieur(A, B, Liste, Cout) :-
chemin(A, B, Liste, Cout),
Cout >= 11.
6. Prédicat voisin(A, B)
voisin(A, B) :- arc(A, B, _).
7. Prédicat chemin(A, B, Trace, Liste)
chemin(A, B, Trace, Liste) :- chemin(A, B, Trace, [A], Liste).
chemin(A, B, Trace, Visite, Liste) :-
arc(C, D, _),
member(C, Visite),
\+ member(D, Trace),
append(Visite, [D], Visite1),
chemin(D, B, Trace, Visite1, Liste).
8. Afficher les chemins entre aulnoye et croix
chemins_aulnoye_croix :- findall(Liste, chemin(aulnoye, croix, Liste), Chemins), write(Chemins).
9. Prise en compte du coût
chemin_coût(A, B, Liste, Cout) :- chemin(A, B, Liste, Cout).
10. Afficher les chemins entre aulnoye et gommegnies de coût inférieur à 20
chemins_coût_inférieur :- findall((Liste, Cout), chemin_coût(aulnoye, gommegnies, Liste, Cout), Chemins), write(Chemins).
FAQ
1. Comment définir une base de faits en Prolog ?
Une base de faits se définit en listant les prédicats avec leurs arguments. Par exemple : homme(nom, taille, couleur_cheveux, âge). Chaque argument doit être instancié avec une valeur valide.
2. Qu'est-ce que le prédicat permutation en Prolog ?
Le prédicat permutation vérifie si une liste est une réorganisation d'une autre liste. Il est souvent utilisé pour générer toutes les permutations possibles d'une liste.
3. À quoi sert le prédicat bagof dans l'exercice 4 ?
Le prédicat bagof permet de collecter toutes les solutions d'une requête et de les regrouper dans une liste. Il est utile pour obtenir toutes les permutations valides d'un problème.