關於Prolog中交換和傳遞等價實現的建議

我想模擬Prolog中等價的交換和傳遞屬性，下面是我所做的：equal/2將作爲事實提供。關於Prolog中交換和傳遞等價實現的建議

symmetricEqual(A,B):- equal(A,B). 
symmetricEqual(A,B):- equal(B,A). 

transitiveEqualPath(A,B,_) :- symmetricEqual(A,B). 

transitiveEqualPath(B,C,IntermediateNodes) :- 
    symmetricEqual(A,B), 
    \+ member(C,IntermediateNodes), 
    transitiveEqualPath(A,C,[B|IntermediateNodes]), B\==C. 

transitiveEqual(A,B) :- transitiveEqualPath(A,B,[]).

但我遇到了與上述解決方案的性能問題，試圖計算transitiveEqual/2（它採取了大致20分鐘），我有2K左右symmetricalEqual/2的事實從等於/ 2計算相當快，所以它一定是transitiveEqual/2的規則的原因，任何人都可以對此提出任何改進建議？

非常感謝。

來源

2013-01-11 user1935724

禮貌的辦法從here：

symmetricEquals(X,Y) :- equal(X,Y). 
symmetricEquals(X,Y) :- equal(Y,X). 

transitiveEqual(A, B) :- 
    % look for an equality path from A to B 
    path(A, B, _Path). 

path(A, B, Path) :- 
    % build a path from A to B 
    path(A, B, [A], Path). 

path(A, B, _Acc, [B]) :- 
    symmetricEquals(A, B). 

path(A, B, Visited, [C|Path]) :- 
    symmetricEquals(A, C), 
    C \== B, 
    \+ memberchk(C, Visited), 
    path(C, B, [C|Visited], Path).

注意path/3,4將回溯到枚舉任何地面或可變A到B之間的所有可能路徑。如果您的equal/2事實隱含的圖形很大，包含許多斷開的組件，並且/或者您在尋找所有組合，這可能會非常昂貴。

來源

2013-01-11 02:22:06 sharky

感謝您的建議，但是，在我查詢了關於？-transitiveEqual（A，B）後，在SWI-Prolog中使用您的代碼後，它沒有產生任何東西。我總是得到A = B作爲輸出。任何想法？ – user1935724

啊，我錯誤地認爲你正在使用_test_的謂詞來限定'A'和'B'的綁定值，而不是用它們來枚舉回溯中的綁定。我會更新我的答案來處理這兩種情況。 – sharky

關於Prolog中交換和傳遞等價實現的建議

回答

相關問題