家庭關係序言 - 距離

Question

可以說，我已經得到了以下斷言：

father(aaron, chloe). 
father(aaron, dan). 
father(aaron, emily). 
father(frank, george). 
mother(beth, chloe). 
mother(beth, dan). 
mother(beth, emily). 
mother(emily, george). 
sibling(X,Y) :-... 
parents(X,Y) :-... 

我想找到族譜中的兩個成員之間的最短路線（距離）。 例如父母之間的距離是2，兄弟（兄弟姐妹）之間的距離是1。 我試過以下（但它沒有工作）：

parent(X,Y) :- 
    father(X,Y); 
    mother(X,Y). 

sibling(X,Y):- 
    parent(Z,X), !, parent(Z,Y), 
    not(X=Y). 

not_in_list(_,[]). 
not_in_list(X,[Y|L]):- 
    not(X=Y), 
    not_in_list(X,L). 

edge(X,Y):- 
    (parent(X,Y); 
    parent(Y,X); 
    sibling(X,Y)). 

list_length(0,[]). 
list_length(N,[_|Ys]):- 
    list_length(N1,Ys), 
    N is N1+1. 

travel_graph(X,X,_). 
travel_graph(From,To,[From|Path]):- 
    edge(From,Next), 
    not_in_list(Next,Path), 
    travel_graph(Next,To,Path). 

degree(X,Y,N):- 
    travel_graph(X,Y,L), 
    list_length(N,L). 

Answer 1

一般來說，當你想最短路徑你想有一個廣度優先搜索。這裏有一些討論：Breadth-First in Prolog

Prolog將試圖找到解決方案的深度，所以它會看到多遠，一個特定的推理線可以採取它。當你想要最短路徑時，你寧願Prolog嘗試所有的第一個選項，然後從每個選項中迭代出一個，直到找到解決方案。這樣，你找到的第一個解決方案將是最短的。如果你可能有無限的解決方案（比如走迷宮，在那裏你可以備份和回溯你的步驟），這是唯一的方法。

不幸的是，沒有魔法開關可以翻轉以獲取廣度優先搜索，因此您必須實施它。 O'Keefe在The Props中非常清楚地解釋了這一點，它首先解釋瞭如何將一個普通的Prolog搜索轉換爲一個明確的深度優先搜索，其中包含一個尚未嘗試的「開放集合」，然後如何改變表示開放集的列表的順序來取代廣度優先行爲。