在Prolog中定义图形:边缘和路径,查找两个顶点之间是否存在路径

Question

我是Prolog的新手.我graph.pl在下图中定义:

这是我的Prolog代码:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

我理解如下:只有在顶点X和顶点之间Y存在边缘且顶点X和顶点之间Z存在一条路径ZY(某种递归)时,顶点和顶点之间才有路径.

这对于呈现的图表是否正确？当我问Prolog关于顶点A和顶点之间的路径时,F它给了我true......这甚至都不对!这段代码可能有什么问题？

Answer 1

图中的循环.您需要跟踪您正在访问的节点,并检查它们.试试这个,使用辅助谓词和累加器来跟踪访问过的节点:

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven't yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).

Answer 2

如果您有兴趣了解是否存在路径，而不是在实际路径（S）一定-compute的传递闭包的二元关系edge/2。

幸运的是，传递闭包是prolog 中的常见习语！

要表达 的非自反传递闭包edge/2，请使用 元谓词—— closure/3在前面的问题“自反传递闭包的定义”中定义：

?- 闭合（边缘，X，Y）。
   X = a, Y = e
; X = a, Y = d
; X = a, Y = c
; ...

请注意，它closure/3具有非常好的终止特性。

如果 的所有条款edge/2都是基本事实，则closure(edge, _, _)普遍终止！看：

?- closure(edge, _, _), false.
false.

Answer 3

您使用的格式(edge/2)对于学习Prolog很有意义,您应该遵循mbratch关于本教程的建议.

实际上,有一些很好的替代品已经可用,在某些情况下可以使用有用的谓词:例如,在库(ugraph)中,有可达/3.现在,使用您的数据,此路径/ 2谓词

path(X,Y) :-
    findall(A-B, edge(A,B), Es),
    vertices_edges_to_ugraph([],Es,G),
    reachable(X,G,Path),
    member(Y,Path).

不

?- path(a,X).
X = a ;
X = b ;
X = c ;
X = d ;
X = e.

让我们看看它意味着什么:

findall(A-B, edge(A,B), Es)

放入Es所有边缘,带有库所要求的符号,

vertices_edges_to_ugraph([],Es,G)

在G中构建相应的图形

reachable(X,G,Path)

制作一个列表从X到达所有顶点的路径(duh)

member(Y,Path)

看看Path中是否存在Y.

由于我用Y 自由查询,我从X得到所有可到达的顶点,我必须这样做a.