2

アークのリストが表示されます。

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

Xノードからノードへのパスがあるかどうかを教えてくれる一連の句を書きましたY。ループが発生する可能性があり、私はそれを説明しました。

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

path(X,Y,P) :-
    arc(X,Y).
path(X,Y,P) :-
    \+ member(X,P),
    arc(X,Z),
    append([X],P,L),
    path(Z,Y,L).

成功すると、トラバースされたノードのリストを返すようにこれを変更する必要があります。これをどのように行うかはわかりません。

私のベースケースは次のようなものになると思いますpath2(X,Y,[X,Y]) :- arc(X,Y).が、それは私のプログラムでは機能しません。前の部分のソリューションに何か問題がありますか、それとも小さな変更がありませんか？どんな助けでもいただければ幸いです。ありがとう！

4

3 に答える 3

2

閉じる...しかし、考慮してください：

path(Start, End, Path) :-
    path(Start, End, [], Path).

開始ノードと終了ノードで呼び出すpath/3と、存在する場合はそれらの間のパスが構築され、バックトラックして代替ルートが提供されます。ノードが 2 回アクセスされることはありません。これ[]はノードアキュムレータリストであるため、パスが作成されたときに循環していないことを確認できます。

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    Mid == End, !,
    append(Acc, [Now, End], Path).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

これらの述語は、実際の作業を行います。1 つ目は基本ケースで、別の呼び出しを介してエンド ノードに到達しarc/2ます。この場合、パスが構築されています。2 つ目は (有向) グラフをトラバースしますが、まだアクセスされていないノードにのみ移動します。

次を使用して、すべてのパスを一度に見つけることができますfindall/3。

findall(Path, path(Start,End,Path), Paths).

Startノード アトムとノード アトムのバインドされた値End。

于 2010-10-10T22:23:24.073 に答える
1

より高いレベルに移動し、1を基本的なイディオムとして使用してください!

%        二項述語 arc/2 がここで使用されます
% |
%v
?-パス(アーク、パス、From、To)。
   送信元 = 送信先、パス = [送信先]
; From = a、To = b、パス = [a,b]
; 出発地 = a、到着地 = c、経路 = [a,b,c]
; 出発地 = a、到着地 = d、パス = [a、b、c、d]
; From = a、To = e、Path = [a,b,c,d,e]
; From = a、To = f、パス = [a,b,c,d,e,f]
; 出発地 = b、到着地 = c、経路 = [b,c]
; 出発地 = b、到着地 = d、経路 = [b,c,d]
; 出発地 = b、到着地 = e、経路 = [b,c,d,e]
; From = b、To = f、パス = [b,c,d,e,f]
; 出発地 = c、到着地 = d、パス = [c,d]
; From = c、To = b、パス = [c,d,b]
; 出発地 = c、到着地 = e、経路 = [c,d,e]
; From = c、To = f、パス = [c,d,e,f]
; 出発地 = d、到着地 = b、パス = [d,b]
; 出発地 = d、到着地 = c、経路 = [d,b,c]
; 出発地 = d、到着地 = e、経路 = [d,e]
; 出発地 = d、到着地 = f、パス = [d、e、f]
; 送信元 = e、送信先 = f、パス = [e,f]
; 間違い。

脚注 1:用途の path/4によって実装されます。

于 2015-12-21T14:12:25.297 に答える
0

シャーキーの答えは私にはうまくいかないようですが、次のモッドはうまくいき、私にはより簡単に感じます. :

path(Now, End, Acc, [Now,End]) :-
    arc(Now, End),
    \+ member(Now, Acc),
    \+ member(End, Acc).

path(Now, End, Acc, Path) :-
    arc(Now, Mid),
    \+ member(Mid, Acc),
    path(Mid, End, [Now|Acc], Path).

何か足りない場合は教えてください。

于 2015-11-17T19:04:24.540 に答える