Prolog Language
Derywacje drzew
Szukaj…
Drzewo dowodu
Drzewo próbne (także drzewo wyszukiwania lub drzewo pochodne) to drzewo, które pokazuje wykonanie programu Prolog. To drzewo pomaga zwizualizować chronologiczny proces cofania się obecny w Prologu. Korzeń drzewa reprezentuje wstępne zapytanie, a gałęzie są tworzone, gdy pojawiają się punkty wyboru. Każdy węzeł w drzewie reprezentuje zatem cel. Gałęzie stają się liśćmi tylko wtedy, gdy potwierdzono albo prawda / fałsz dla wymaganych (zestawów) celów, a wyszukiwanie w Prologu odbywa się od lewej do prawej, od głębokości do pierwszej .
Rozważ następujący przykład:
% 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).
Kiedy teraz zapytamy:
?- grandfather_grandchild(paul,peter).
następujące drzewo dowodów wizualizuje proces wyszukiwania w pierwszej kolejności:
?- 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
(*) nie działa dla mother_child(ellen,angie)
gdzie „angie” nie pasuje do „peter”