如何訪問有向圖中的每個點

Question

在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 

如你所知，在向圖，有可能是一個循環。但是，不需要兩次通過同一點。

   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 

Answer 1

我放了一些評論解釋代碼做什麼...

% 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. 

Answer 2

保留已經訪問過的節點列表。在每一步中，檢查邊緣的端點是否存在於列表中。