Contrôle de la résolution
en langage Prolog
Faculté de sciences et de génie
Département d’informatique et de génie logiciel
IFT-2003 Intelligence artificielle I
Laurence Capus
3 prédicats particuliers
• Coupure : !/0
– Pour obtenir une seule solution
– Pour réduire l’arbre de résolution
– Le retour-arrière est stoppé à la coupure
• Négation : not/1
– Pour nier un But
– Réussit si son argument échoue
• Échec : fail/0
– Pour faire échouer un But
– Échoue toujours
2
Coupure : !/0
– Stopper la récursion
• Exemple 1
a(1). ?- c(X).
a(2). X = 2 ; X = 3 ; no
a(3).
b(2). ?- d(X).
b(3). X = 2 ; X = 3 ; no
b(4).
c(A) :- a(A), b(A). ?- e(X).
d(A) :- !, a(A), b(A). no
e(A) :- a(A), !, b(A).
f(A) :- a(A), b(A), !. ?- f(X).
X = 2 ; no
3
Coupure : !/0
– Stopper la récursion
• Exemple 2 (utilisation incorrecte de la
coupure)
/*max/3: max(A,B,C) est | ?- max(1,2,M).
vrai si le maximum entre A M = 2
et B est C */
max(M,N,M):- M >= N, !. | ?- max(2,1,M).
max(M,N,N). M=2
| ?- max(2,1,1).
yes
4
Coupure : !/0
– Obtenir une seule réponse
• Exemple 1 (parenté)
parent(pierre, ?- parent(X,
sébastien). sébastien).
parent(nathalie, X = pierre ;
sébastien). X = nathalie ;
parent(marie, nathalie). no
parent(robert, nathalie).
?- parent(X,
sébastien), !.
X = pierre ;
no
5
Coupure : !/0
– Réduire la recherche
• Exemple : séparer/3 : séparer(L1,L2,L3) réussit si tous
les nombres positifs de la liste L1 sont dans L2 et tous
les nombres négatifs sont dans la liste L3.*/
séparer([ ], [ ], [ ]).
séparer([X|R], [X|RP], RN) :- X>0, séparer(R, RP, RN).
séparer([X|R], RP, [X|RN]) :- X<0, séparer(R, RP, RN).
séparer([X|R], RP, RN) :- X=:=0, séparer(R, RP, RN).
%avec la coupure : rendre chaque clause exclusive
séparer([ ], [ ], [ ]).
séparer([X|R], [X|RP], RN) :- X>0, !, séparer(R, RP, RN).
séparer([X|R], RP, [X|RN]) :- X<0, !, séparer(R, RP, RN).
séparer([X|R], RP, RN) :- X=:=0, !, séparer(R, RP, RN).
6
Arbre de résolution sans la coupure
séparer([ ], [ ], [ ]). %1
séparer([X|R], [X|RP], RN) :- X>0, séparer(R, RP, RN). %2
séparer([X|R], RP, [X|RN]) :- X<0, séparer(R, RP, RN). %3
séparer([X|R], RP, RN) :- X=:=0, séparer(R, RP, RN). %4
?- séparer([1, -2], LP, LN). %3,4
%1
Échec %2 X=1,R=[-2],
[1,-2]≠[] LP=[1|RP], LN=RN
1>0, séparer([-2], RP, RN).
séparer([-2], RP, RN).
%1 %4
Échec
%2 X=-2,R=[], %3 X=-2,R=[], RP=RP1, RN=[-2|RN1]
[-2]≠[] RP=[1|RP1], RN=RN1
-2>0, séparer([], RP1, RN1). -2<0, séparer([], RP1, RN1).
Échec séparer([], RP1, RN1).
-2<0 %2,3,4
%1 RP1 = [], RN1=[]
7
Succè
Arbre de résolution avec la coupure
séparer([ ], [ ], [ ]). %1
séparer([X|R], [X|RP], RN) :- X>0, !, séparer(R, RP, RN). %2
séparer([X|R], RP, [X|RN]) :- X<0, !, séparer(R, RP, RN). %3
séparer([X|R], RP, RN) :- X=:=0, !, séparer(R, RP, RN). %4
?- séparer([1, -2], LP, LN). %3,4
%1
Échec %2 X=1,R=[-2],
[1,-2]≠[] LP=[1|RP], LN=RN
1>0, !, séparer([-2], RP, RN).
séparer([-2], RP, RN).
%1 %4
Échec
%2 X=-2,R=[], %3 X=-2,R=[], RP=RP1, RN=[-2|RN1]
[-2]≠[] RP=[1|RP1], RN=RN1
-2>0, !, séparer([], RP1, RN1). -2<0, !, séparer([], RP1, RN1).
Échec séparer([], RP1, RN1).
-2<0 %2,3,4
%1 RP1 = [], RN1=[]
8
Succès
Négation et échec
– Exemple :
• Comment traduire ces connaissances en
Prolog : « Marie aime les animaux, mais pas
les serpents » ?
– Alternative 1 : utiliser le not/1
/* Si X est un animal et que X n’est pas un serpent,
alors marie aime X*/
aime(marie, X) :- animal(X), not(serpent(X)).
– Alternative 2 : utiliser le fail/0
aime(marie, X) :- serpent(X), !, fail.
aime(marie, X) :- animal(X).
9
Négation et échec
– Implémentation de la négation : négation
par l’échec
– Un prédicat non/1 : non(But) est vrai si
But est faux
%si But est vrai alors non( But ) est faux
non( But ) :- But, !, fail.
%si But est faux alors non( But ) est vrai
non( But ).
10
Conclusion
• On peut contrôler la résolution en
utilisant les prédicats prédéfinis : !/0,
not/1, fail/0.
11