Retour arrière avec plusieurs points de choix

Quand il y a plus d’un point de choix au moment du retour arrière, il faut s’assurer d’identifier celui qui sera considéré en premier. On reculera au point de choix correspondant au dernier but unifié pour lequel il restait d’autres possibilités d’unification. Pour mieux comprendre, considérons le programme suivant :
tres_intelligent(X):- intelligent(X),sympathique(X).
tres_intelligent(X):-professeur_ia(X).
intelligent(X):- debrouillard(X), humain(X).
intelligent(X):- dauphin(X).
humain(X):- homme(X).
humain(X):- femme(X).
professeur_ia(michel).
debrouillard(chico).
dauphin(flipper).
femme(george).
homme(chico).
sympathique(flipper).
Supposons maintenant la requête suivante :
?- tres_intelligent(X).
Pour résoudre ce but, l’interpréteur Prolog devra réaliser plusieurs retours arrière. La figure 4 montre l’état de l’exécution la première fois qu’un échec se produit (les points de choix sont montrés en italiques). On note l’existence de trois points de choix. L’ordre d’apparition de ces points de choix est le suivant :
1. tres_intelligent(X)
2. intelligent(X)
3. humain(X)
Par conséquent, le point de choix auquel on reculera, au premier échec, est celui associé au but humain(X). La résolution repart à partir de ce point, pour se buter une nouvelle fois à un échec (voir figure 5).

FIG. 4 – Arbre de résolution
Cette fois, l’interprète Prolog reculera au point de choix associé au but intelligent(X). Continuant à partir de ce point, il faudra maintenant résoudre le but dauphin(X). La variable X sera instanciée par le constant flipper. La résolution pourra alors continuer et terminer avec succès dans l’état illustré à la figure 6.


FIG. 5 – Arbre de résolution

FIG. 6 – Arbre de résolution
Remarquez qu’il reste encore un point de choix qui n’a pas été considéré. Ainsi, si on demande une nouvelle solution, l’interpréteur Prolog reculera à ce point de choix. Dans ce cas, une nouvelle résolution à partir de ce point tentera de résoudre le but professeur_ia(X), ce qui se terminera avec succès, avec X = michel.
3.4 Exercices
3.1 Traduire en Prolog les faits suivants :
– João aime Maria.
– Paulo aime Antônio.
– Antônio aime Claudia.
– Fernando aime Claudia.
– Claudia aime tous ceux qui l’aiment.
– Personne n’aime Paulo.
– Deux personnes de sexes différents qui s’aiment mutuellement sont aussi des amants.
3.2 Supposons un édifice contenant un ensemble de salles. On utilise une relation connexe(X,Y) pour indiquer que l’on peut passer directement de la salle X à la salle Y, et vice versa. Supposant que la constante exterieur désigne l’extérieur de l’édifice, définissez le prédicat sortir(X), dont la résolution réussit s’il existe un chemin pour se rendre à l’extérieur à partir de la salle X.
Exemple :
connexe(salle1,salle2).
connexe(salle2,salle5).
connexe(salle3,exterieur).
connexe(salle4,salle7).
connexe(salle5,salle6).
connexe(salle5,salle8).
connexe(salle6,salle9).
connexe(salle9,exterieur).
?- sortir(salle1).
Yes
?- sortir(salle4).
No