在遞歸中使用Prolog列表

所以我試圖使用遞歸方法來找到兩個人之間的路徑。這裏是快速背景：我定義了一些事實in(X,Y)。這表明誰是相關的，即。 in(person1,project1),in(person2,project1)等等。現在，任何兩個人如果在同一個項目中相互關聯，或者他們之間存在人與人之間的鏈接路徑。例如p1工作在A p2上工作在A和B上，p3工作在B上，因此有一條從p1到p3到p2的路徑。這些路徑可以是任意長度。在遞歸中使用Prolog列表

我試圖遞歸解決這個（沒有看到任何其他方式），但有一個惱人的問題：

related(A,B) :- 
     in(A,X), 
     in(B,X), 
     not(A=B). 

chain(A,B) :- 
     related(A,B). 
chain(A,B) :- 
     related(A,Y),  
     chain(Y,B).

的問題是，路徑可能重演。它可以從p1到p2回到p1無盡的時代。一個人不應該在路上超過一次。

我試圖解決這個問題，我添加了一個列表。如果一個人已經在列表中，他們不能再次添加：

related(A,B,L) :- 
     in(A,X), 
     in(B,X),not(A=B). 

chain(A,B,L) :- 
     related(A,B,L). 
chain(A,B,L) :- 
     related(A,Y,L), 
     not(member(Y,L)), 
     append(L,[Y],Q), 
     chain(Y,B,Q).

它有點工作，但造成一噸的隨機誤差，重複一些人多次，有的只有一次，然後失敗。這種方法看起來不錯嗎？我完全使用列表錯誤嗎？

謝謝。

來源

2012-11-02 Mike

我想我從來沒有完全清楚就夠了，但我結束了這個解決我自己。我把下面的代碼。

真正重要的是一個有效的notchain謂詞，然後確保我正確地添加了附件。我還創建了一個不同的謂詞來替換不是（A = B）。代碼如下。大部分答案都是確保在列表中附加了什麼。如果沒有正確的[]附加內容會導致錯誤。

notchain（X，L）： - ！

成員（X，L），失敗。

notchain（X，L）。

然後：

鏈（A，B，L）： -

相關（A，B），附加（L，[A]，Q），追加（Q，[B]，Z）， write（final），writeln（Z）。

鏈（A，B，L）： - notchain（A，L），附加（L，[A]，Q），相關（A，Y），鏈（Y，B，Q ）。

這在相關的使用：

notsame（A，B）： -
（A = B），失敗。（A，B）。

來源

2012-11-03 20:39:03 Mike

第一次改進。你在尋找所有的關係鏈嗎？還是你想要檢查是否有一個關係鏈？在第一種情況下添加一個剪輯。

chain(A,B) :- 
     related(A,B), !. 
chain(A,B) :- 
     related(A,Y),  
     chain(Y,B).

在第二種情況下，Prolog的不正是它的要求做的，就是找到所有可能鏈。

請發佈一個查詢導致問題，以便我們可以一起推理並改進解決方案。

來源

2012-11-02 16:40:06 NotAUser

所有的鏈都是優選的。真正的問題是，一個連鎖店可以多次擁有同一個人，需要有一種方法來防止這種情況發生。稍後我會在家時發佈樣本輸出。我知道如何在Java，C，C＃等中輕鬆完成這個任務，但是prolog正在拋出一個循環。 – Mike

這是一種替代方法，可能效率較低，但相當普遍，基於定點計算。

connected(Found, Connected) :- 
    collect(Found, [], Ext), 
    ( Ext == Found 
    -> Connected = Found 
    ; connected(Ext, Connected) 
    ). 

collect([], Set, Set). 
collect([E|Es], Set, Fix) :- 
    extend(E, Set, Ext), 
    collect(Es, Ext, Fix). 

extend(E, Set, Ext) :- 
    directly(E, DirectConn), 
    ord_union(DirectConn, Set, Ext). 

directly(A, DirectConn) :- 
    setof(B, P^(in(A, P), in(B, P)), DirectConn).

我們必須調用連接（發現，連接）與排序列表，它一直循環到集不能擴展。例如，對於本次測試數據

in(anna, project1). 
in(bob, project1). 
in(bob, project2). 
in(chris, project2). 
in(dan, project3). 

?- connected([bob],L). 
L = [anna, bob, chris]. 

?- connected([dan],L). 
L = [dan].

我允許在目的直接/ 2獲取Identity，即

?- directly(X,Y). 
X = anna, 
Y = [anna, bob] ; 
... 
X = dan, 
Y = [dan].

來源

2012-11-02 23:38:07 CapelliC

在遞歸中使用Prolog列表

回答

相關問題