2

論理コースの宿題を出しましたが、多かれ少なかれ、それを解決する方法がわかりません...次のようなクエリを使用して

  ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]),
  r(e,[b,d,f]),r(f,[e,g]),r(g,[f])],Path).

Prolog は、指定されたグラフで可能なすべてのパスを返す必要があります。r(X,List) という用語はグラフを定義します。これは、ノード X から List 内のノードに到達できることを意味します。この場合、出力は次のようになります。

Path = [a,b,c] ;
Path = [a,b,e,d] ;
Path = [a,b,e,f,g] ;
Path = [a,d,e,b,c] ;
Path = [a,d,e,f,g] ;
false.

私はここ SE と Web で同様の問題に対する多数の解決策のコツをつかんでいますが、この割り当てでグラフの定義を操作する方法を理解するにはあまりにも愚かです。

find(Start,...) は r(Start,List) のリストのすべてのメンバーを使用して再帰的に呼び出す必要があると考えていますが、Prolog のまったくの初心者として (標準的な家系図を作成しただけです...) 私はそれを行う方法がわかりません。

どんな助けでも本当に感謝しています。始めるものがあまりないことは承知していますが、すでに半夜をかけて何かを理解しようとしており、今に至るまで手がかりがありません。

/編集：

まず、再帰を中止するには、何らかの基本ケースが必要になると思います。どっちでもいいと思う

find([],_,_).

最後の再帰呼び出しには最初から何もないと思うので、または

find(_,[],_).

プログラムが処理を終了したときに、隣接するノードを定義する用語のリストが空であると仮定します。

では、実際の呼び出しです。おそらく次のようなもの

find(Start,[r(Start,[Adjacent|Restadj])|Rest],Path):-
           find(???).

ここでの私の問題は次のとおりです。

- 次の Start として r(...) 項のリストのメンバーをプログラムに使用させるにはどうすればよいですか?

-ノードがすでに「訪問」されているかどうかを確認するにはどうすればよいですか/rの特定のリストからノードを削除するにはどうすればよいですか

-見つかったノードをパス リストに入れるにはどうすればよいですか? 単純に追加しますか？または、[Path|Start] のようなもので再帰呼び出しを実行しますか?

ご覧のとおり、それほど多くはありません。Prolog は非常に興味深く、したがって学ぶのが楽しいので、いくつかの示唆に富んだ質問はいいでしょう...

きちんとした PDT-Eclipse トレース ツールをしばらく使用した後、プログラムが何をしているのかを理解したと思います。この時点でわからないのは、最後のノードが常に失われる理由です。バックトラックが失敗した後、たとえば r(c,[b]) が次に見つかった用語であり、 memberchk(b,[b]) が否定のために失敗し (それが + が行うことです)、r(c を含む他の用語がないためです。 ,X) が見つかると、r(b,[...]) に隣接するノードが残っているノード b から移動する他の可能性を探すことからやり直します。しかし、なぜプログラムはノード c を Path リストに入れるのを忘れるのでしょうか? 場合に備えて、何らかのif-then-elseを行う可能性はありますか

 member(r(Node, Adjacent), Graph),
member(AdjNode, Adjacent),
\+ memberchk(AdjNode, Seen),

パスに最後のノードを追加するには失敗しますか?

4

2 に答える 2

2

幅優先検索である Daniel Lyons による非常に明確なコードに基づいて構築します。

all_paths(Node, Graph, Paths) :- 
   bfs(Graph, [[Node]-[]], R, []),      % or dfs(...)
   maplist( fst, Paths, R).

fst(A, A-_).        % utility
pair(B, A, A-B).    %  helpers
add(LS,H,[H|LS]).   %   

bfs(_G, [], Z, Z).                % queue is empty
bfs(Graph, [H|Q], [H|R], Z) :- 
    H = Path-Seen, Path = [Node|_],
    findall( Next, member(r(Node, Next), Graph), NS),
    flatten_diff( NS, Seen, WS),  % working set of nodes
    maplist( add(Path), WS, PS),  % new paths
    maplist( pair([Node|Seen]), PS, QH),  % new addition to the queue
    %% append( QH, Q, Q2),        % DFS
    append(    Q, QH, Q2),        % BFS
    bfs(Graph, Q2, R, Z).

（未検証）。flatten_diff(A,B,C)list の list を平坦化し、 list にAも表示される要素を削除して、結果としてBlist を生成する必要があります。C

PeterPanter が気づいたように、Daniel Lyons のコードは、結果のパスの最後のノードを除外しないように、少し調整する必要があります。

find(Node, Graph, [Node|Path]) :- find(Node, Graph, Path, []).

find(_, _, [], _).
find(Node, Graph, [AdjNode|Path], Seen) :-
    member(r(Node, Adjacent), Graph),
    member(AdjNode, Adjacent),
    \+ memberchk(AdjNode, Seen),
    find(AdjNode, Graph, Path, [Node|Seen]).

現在生成されている空のパスはなく、期待どおりに機能します。

11 ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),    r(d,[a,g]), 
              r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], Path).
Path = [a] ;
Path = [a, b] ;
Path = [a, b, c] ;
Path = [a, b, e] ;
Path = [a, b, e, d] ;
Path = [a, b, e, d, g] ;
Path = [a, b, e, d, g, f] ;
Path = [a, b, e, f] ;
Path = [a, b, e, f, g] ;
Path = [a, d] ;
Path = [a, d, g] ;
Path = [a, d, g, f] ;
Path = [a, d, g, f, e] ;
Path = [a, d, g, f, e, b] ;
Path = [a, d, g, f, e, b, c] ;
false.
于 2013-05-08T17:59:03.333 に答える