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 から約 2K の対称 Equal/2 ファクトがかなり高速に計算されるため、ルールの原因である必要があります。推移的Equal / 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の間のすべての可能なパスを列挙することに注意してください。事実によって暗示されるグラフが大きく、多くの切断されたコンポーネントが含まれている場合、および/またはすべての組み合わせを探している場合、これは非常に高価になる可能性があります。ABequal/2

于 2013-01-11T02:22:06.697 に答える