0

無向グラフで終わるまでの道のりを見つけるにはどうすればよいですか?

Graph :

    Node : S, Y, F, T                visualization :    S ----- Y ---- T
    Edge : S --- Y                                       \     /
           Y --- F                                        \   /
           S --- F                                         \ /
           Y --- T                                          F


Assume that

       Start   S 
       Finish  F

       after run   go 

       result will be :

              S F
              S Y F

1 つのノードに複数回アクセスしたくありません。私が訪問すると、この問題は NP 問題の 1 つになります。

編集：

入力は任意の形式にすることができます

example:

       edge (S,Y).     OR          edge (Y,S).
       edge (Y,F).                 edge (F,Y).
       edge (S,F).                 edge (F,S).
       edge (Y,T).                 edge (T,Y).

しかし、出力は同じでなければなりません

4

1 に答える 1

1

訪問したノードのトレースを保持し、次のステップで可能な宛先を追加するときにそれらを除外します。

いくつかのエッジを変更して 1 つ追加し、S から F に移動するためにエッジが「間違った」順序でリストされている場合でも機能することを確認しました。

edge('S','Y').    visualization:    S -- Y -- T
edge('F','Y').                     / \  /
edge('S','F').                    /   \/
edge('Y','T').                   A --- F
edge('A','S').
edge('F','A').

プロローグでは、これは大まかに次のようになります。

pathBetween(A,A,_):- !, fail.
pathBetween(S,F,Visited) :- (edge(S,F) ; edge(F,S)),
    append(Visited,[S,F],L),
    write(L).
pathBetween(S,F,Visited) :-
    (   edge(S,A) ; edge(A,S)  ),
    not(member(A,Visited)),
    pathBetween(A,F,[S|Visited]).

を使用;して、すべての解を手動で見つけるか、findallを使用できます。

?- findall(Visited, pathBetween('S', 'F', []), _).
[S,F][S,Y,F][S,A,F]
true.
于 2012-06-02T10:49:15.877 に答える