Prolog Language
Alberi di derivazione
Ricerca…
Albero di prova
L'albero delle prove (anche albero di ricerca o albero di derivazione) è un albero che mostra l'esecuzione di un programma Prolog. Questo albero aiuta a visualizzare il processo cronologico di backtracking presente in Prolog. La radice dell'albero rappresenta la query iniziale e i rami vengono creati quando si verificano punti di scelta. Ogni nodo dell'albero rappresenta quindi un obiettivo. I rami diventano foglie solo quando è stato dimostrato che sia vero / falso per l'obiettivo (set di) richiesto (s) e la ricerca in Prolog viene eseguita in modo da profondità a sinistra da destra a prima .
Considera il seguente esempio:
% 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).
Quando interrogiamo ora:
?- grandfather_grandchild(paul,peter).
la seguente struttura di prova visualizza il processo di ricerca in profondità:
?- 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
(*) fallisce per mother_child(ellen,angie) dove 'angie' non riesce ad abbinare 'peter'