如何访问有向图中的每个点

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

保留已经访问过的节点列表。在每一步中，检查边缘的端点是否存在于列表中。