关于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中交换和传递等价实现的建议

回答

相关问题