序言 - 遞歸下來的家庭樹

Question

我想寫一個Prolog程序，將按順序打印出英國皇室的男性接班人。到目前爲止，我嘗試：

son(elizabeth, charles). 
son(charles, william). 
son(charles, henry). 
son(elizabeth, andrew). 
son(elizabeth, edward). 
son(edward, severn). 
successor(X, Y) :- son(X, Y). 
successor(X, Y) :- son(X, C), successor(C, Y). 

後繼功能並沒有完全做到我想要的東西：電流輸出是這樣的：

successor(elizabeth, Y). 
Y = charles ; 
Y = andrew ; 
Y = edward ; 
Y = william ; 
Y = henry ; 
Y = severn ; 
false. 

第一條規則讓所有的三個孩子立即打印出來，然後第二條規則打印出所有的後代。但是，第一個孩子的後代應該來第二直接子之前，像這樣：

successor(elizabeth, Y). 
Y = charles ; 
Y = william ; % william and henry should come before andrew 
Y = henry ; 
Y = andrew ; 
Y = edward ; 
Y = severn ; 
false. 

這是我的第一個Prolog程序，和我在如何表達權關係的損失。任何人都可以給我一個想法或指點資源，這將有助於我？

Answer 1

由於慧慧如上所述，Prolog的查詢是通過選擇一個規則，遞歸使用depth-first search評估，然後解決選擇下一條規則並重復該過程。然而，你開始的特定規則實際上導致了家譜的breadth-first search，正如你所指出的那樣，它並沒有給出與實際連續線匹配的輸出。相反，你想要對皇家樹進行深度優先遍歷。這個版本給您正在尋找的結果是：

successor(X, Y) :- son(X, Z), (Y = Z; successor(Z, Y)). 

利用這個規則，Prolog的解析查詢successor(X, Y)大致如下：

• 對於每個Z誰是X兒子：
  • 綁定Y至Z，給出Z作爲解決方案。
  • ;運算符作爲邏輯OR運算，因此現在Y未被綁定，並且successor/2被遞歸地調用以獲得Z的兒子的後繼者。

是的，請不要試圖讓Prolog的藝術的一個副本。這不是最簡單的編程手冊，但是我發現它對我理解邏輯編程的嘗試非常有幫助。最近在1994年版的eBay上出現了一些廉價的精裝版本。

Answer 2

你的規則集對我來說看起來不錯，它給你正確的結果，它只是打印它們，因爲它推斷出它們，這使得訂單看起來不正確。通過紙上的結果，你可能會得到類似的結果。

Answer 3

你說：

第一條規則讓所有的三個孩子立即打印出來，然後第二個規則打印出所有的後代。

對於任何給定謂詞（如successor/2），PROLOG一般會評估所有的第一條可能的解決方案，那麼接下來，等等，直到最後一節，在這個順序。因此，PROLOG的行爲將完全按照您上面的建議 - 首先找到直系孩子的解決方案，因爲successor/2的第一個子句就是這樣，而第二個子句找到了子孫。如果你是在一個不同的命令後，嘗試重新排序的條款（即）;

successor(X, Y) :- son(X, C), successor(C, Y). 
successor(X, Y) :- son(X, Y). 

這將導致PROLOG評價到：

?- successor(elizabeth, Y). 
Y = william ; 
Y = henry ; 
Y = severn ; 
Y = charles ; 
Y = andrew ; 
Y = edward. 

即所有descentants之前直接孩子。

但是，您建議的排序順序不能通過簡單重新排序這些子目標來實現。相反，考慮各種樹遍歷方法;即按順序，預定和後序。您可以編寫一個（簡單）程序，該程序能夠以各種不同的方式遍歷樹結構，而不是PROLOG的默認評估順序。例如，考慮successor/2以下新定義：

successor(Parent, [Son|SonDescendents]) :- 
    son(Parent, Son), 
    successor(Son, SonDescendents). 

該條款旨在深度優先填充孩子的列表的兒子之下，將回溯到發現所有的解決方案。

successor(NonParent, []) :- 
    \+ son(NonParent, _). 

這在下一項採取基本情況，由此給定的個體不具有任何兒子護理，因此沒有後代輸入結果列表（空）。

評估這給：

?- successor(elizabeth, S). 
S = [charles, william] ; 
S = [charles, henry] ; 
S = [andrew] ; 
S = [edward, severn] ; 
false. 

PS。我強烈推薦以下書籍學習PROLOG：

The Art of Prolog, by Leon Sterling and Ehud Shapiro

The Craft of Prolog, by Richard O'Keefe

Programming in Prolog, by Clocksin and Mellish