1

我想用可交换和传递的属性来模拟 Prolog 中的等价性，这就是我所做的：equal/2 将作为事实提供。

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分钟），我从equal/2计算得非常快，大约有2KsymmetricEqual/2事实，所以它一定是规则的原因对于transitiveEqual/2，任何人都可以提出任何改进建议吗？

非常感谢。

4

1 回答 1

0

感谢这里的方法：

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-11T02:22:06.697 回答