如何访问有向图中的每个点 [英] how to visit each point in directed graph

问题描述

在Prolog中，如何实现图算法以便找到所有路径以便在有向图中实现旅行商问题？例如：

 图
预期输入预期输出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 
  

如您所知，在有向图中，可能存在一个循环。但是，不需要两次通过同一点。

 图表预期输出
 X ----> Y 
 Y ----> X X Y Z 
 Y ----> Z 
  

为什么我要取消这种情况是因为;

 输出：
 
 XYXY ... Z 
 ^^^ 
上帝知道这个长度（程序终止时）
终止是np问题
  

解决方案

解释代码的作用......

 ％有向图
 edge（x，y）。 
 edge（y，t）。 
 edge（t，z）。 
 edge（y，z）。 
 edge（x，z）。 
 
％获得从开始到结束的路径
路径（开始，结束，路径）： -  
路径（开始，结束，[开始]，路径）。 
 
％达到目标时，反向访问列表
 path（End，End，RPath，Path）： -  
 reverse（RPath，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。 
  

In Prolog, how can I implement graph algorithm in order to find all path in order to implement travel salesman problem in directed graph ?

example :

                                                                         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

As you know, in directed graph, there could be a cycle. However, no need to pass same point two times.

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

Why I am elimineting this case is because ;

      output :

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

解决方案

I placed some comment that explain what the code does...

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

test:

?- path(x,z,P).
P = [x, y, t, z] ;
P = [x, y, z] ;
P = [x, z] ;
false.

这篇关于如何访问有向图中的每个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！