Prolog Language
Arbres de dérivation
Recherche…
Arbre de preuve
L'arbre de preuve (également arbre de recherche ou arborescence de dérivation) est une arborescence qui montre l'exécution d'un programme Prolog. Cet arbre permet de visualiser le processus de retour en arrière chronologique présent dans Prolog. La racine de l'arbre représente la requête initiale et les branches sont créées lorsque des points de choix apparaissent. Chaque nœud de l'arbre représente donc un objectif. Les branches ne deviennent des leafs que lorsque true / false a été prouvé pour le (les) jeu (s) d'objectifs requis (s) et que la recherche dans Prolog est effectuée de gauche à droite .
Prenons l'exemple suivant:
% Facts
father_child(paul,chris). % Paul is the father of Chris and Ellen
father_child(paul,ellen).
mother_child(ellen,angie). % Ellen is the mother of Angie and Peter
mother_child(ellen,peter).
% Rules
grandfather_grandchild(X,Y) :-
father_child(X,Z),
father_child(Z,Y).
grandfather_grandchild(X,Y) :-
father_child(X,Z),
mother_child(Z,Y).
Lorsque nous interrogeons maintenant:
?- grandfather_grandchild(paul,peter).
l'arbre de vérification suivant visualise le processus de recherche en profondeur:
?- grandfather_grandchild(paul,peter).
/ \
/ \
?- father_child(paul,Z1),father_child(Z1,peter). ?- father_child(paul,Z2),mother_child(Z2,peter).
/ \ / \
{Z1=chris} {Z1=ellen} {Z2=chris} {Z2=ellen}
/ \ / \
?- father_child(chris,peter). ?- father_child(ellen,peter). ?- mother_child(chris,peter). ?- mother_child(ellen,peter).
| | | / \
fail fail fail fail(*) success
(*) échoue pour mother_child(ellen,angie) où 'angie' ne correspond pas à 'peter'