5

Prolog で 2 つのノード間の最短経路を見つけたい。2 つのノード間のすべてのパスを見つける方法を考え出しましたが、残念ながら次のコードはループに陥ります。

arc(a,b).
arc(b,a).
arc(b,c).
arc(c,b).
arc(c,d).
arc(d,c).

path(X,Y,[arc(X,Y)]) :-
   arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :-
   arc(X,Z),
   path(Z,Y,P).

コードの実行は次のとおりです。

?- path(a,c,R).
R = [arc(a, b), arc(b, c)] ;
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, c)] ;
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, a), arc(a, b), arc(b, c)] 
....

だから、私の質問は:無限にループせずにすべてのパスを取得する方法は?

一日の終わりに、リストの長さを取得し、最小値を見つけます。

可能であれば、ISO Prolog であるソリューションを提供してください。

注：これは更新されたコードです。まだ問題があります。どうやら、アトムではなくファクトに対してチェックする場合、メンバー述語は機能しません。

xxx([]).

path(X,Y,[arc(X,Y)]) :-
   arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :- 
        arc(X,Z)
        ,xxx(L)
        ,member(arc(X,Z),L)->
            !;
            (member(arc(Z,X),L)->
                !;
                (append(L,[arc(X,Z)],R),retract(xxx(_)),assert(xxx(R)),path(Z,Y,P))).

私のメンバーの述語は次のとおりです。

member(X,[X|T]).
member(X,[H|T])  :-  member(X,T).

ありがとうございました。

4

2 に答える 2

0

解が1つだけ必要な場合は、カット演算子「！」を調べることができます。

無限ループに陥らないようにするには、すでにアクセスしたノードを格納するアキュムレータリストを使用する必要があります。

于 2012-05-30T07:55:18.107 に答える