2

Prologでは、有向グラフで巡回セールスマン問題を実装するためにすべてのパスを見つけるためにグラフアルゴリズムを実装するにはどうすればよいですか？

例 ：

                                                                         graph
                    expected input     expected output                 X -----> Y
    start X             X  Y               X Z                         Y -----> T
    end   Z             Y  T               X Y Z                       T -----> Z
                        T  Z               X Y T Z                     Y -----> Z
                        Y  Z                                           X -----> Z
                        X  Z

ご存知のように、有向グラフでは、サイクルが存在する可能性があります。ただし、同じポイントを2回通過する必要はありません。

             graph             expected output             
           X ----> Y            
           Y ----> X               X Y Z
           Y ----> Z

私がこのケースを排除している理由は、;

      output :

      X Y X Y ...   Z
              ^^^
              god knows this length ( when program terminates )
              termination is np problem
4

2 に答える 2

2

すでにアクセスしたノードのリストを保持します。各ステップで、エッジの端点がリストに存在するかどうかを確認します。

于 2012-05-29T11:06:54.010 に答える
2

コードの機能を説明するコメントを付けました...

% your directed graph
edge(x, y).
edge(y, t).
edge(t, z).
edge(y, z).
edge(x, z).

% get a path from start to end
path(Start, End, Path) :-
    path(Start, End, [Start], Path).

% when target reached, reverse the visited list
path(End, End, RPath, Path) :-
    reverse(RPath, Path).

% take non deterministically an edge, check if already visited before use
path(Start, End, Visited, Path) :-
    edge(Start, Next),
    \+ memberchk(Next, Visited),
    path(Next, End, [Next|Visited], Path).

テスト：

?- path(x,z,P).
P = [x, y, t, z] ;
P = [x, y, z] ;
P = [x, z] ;
false.
于 2012-05-29T13:52:39.887 に答える