在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之间存在边并且顶点Z和顶点Y之间存在路径时，才存在顶点X和顶点Y之间的路径（一种递归）。

对于给出的图来说，这样理解是否正确？当我询问Prolog关于顶点A和顶点F之间的路径时，它给出了true……这甚至都不正确！在这段代码中可能有什么问题呢？

- yak

---

; 表示“或者”，, 表示“并且”。因此，您的 path 子句不正确。 - lurker

@mbratch：当我将 ; 改为 , 时，Prolog 卡住了...没有给出答案。对于我的图形，答案应该是 false/no。 - yak

; 是错误的，必须改为 ,。另一个问题是代码不能处理在闭环路径上的情况，所以它可能会在解决问题之前一直在闭环路径上转圈，直到栈溢出。您需要收集“已经走过的路径”的列表，以确保不重复走相同的路径。 - lurker

@mbratch：好的，谢谢，现在我明白了。但是我的图应该如何设置适当的规则呢？ - yak

一种方法是让你的规则收集你已经走过的边缘列表，如果你已经走过那里，就不要选择它们。如果你在谷歌上搜索“prolog graph”，你会发现在线上有几个例子都详细说明了这个确切的问题，例如http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html。 - lurker

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

- Nicholas Carey

---

更简单的方法来完成它。也许memberchk/2比member/2更可取。 - CapelliC

这个谓词有一些令人惊讶的实际应用。通过一些简单的修改，它可以用作英语到Prolog的翻译器。 - Anderson Green

Answer 2

如果您想知道路径是否存在（但不一定需要实际的路径），请计算二元关系 edge/2 的传递闭包。

幸运的是，传递闭包 是 Prolog 中常用的习语！

要表示edge/2的非反身传递闭包，请使用元谓词 closure/3，它在早期问题“反身传递闭包的定义”中已经定义：

?- closure(edge, X, Y).
   X = a, Y = e
;  X = a, Y = d
;  X = a, Y = c
;  ...

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

如果edge/2的所有条款都是ground事实，则closure(edge, _, _)通用地终止！看：

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

- repeat

---

edge(X,s(X)). 在全局范围内终止，但 closure(edge,0,X) 描述了一个无限集合，只能用无限多个答案来描述。因此不会终止！ - false

太棒了！也有点可怕。会编辑以澄清！谢谢！ - repeat

Answer 3

你使用的格式（edge/2）对于学习Prolog很有意义，你应该遵循mbratch关于教程的建议。

实际上，已经有很好的替代方案可用，在某些情况下还带有有用的谓词：例如，在library(ugraph)中，有reachable/3。现在，使用你的数据，这个path/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)

将所有的边用库所要求的符号表示为E。

vertices_edges_to_ugraph([],Es,G)

在G中构建相应的图形

reachable(X,G,Path)

制作一个列表，列出所有可以从X到达的顶点路径（显然）

member(Y,Path)

查看路径中是否存在Y。

由于我使用了 Yfree 进行查询，因此我可以从绑定到 a 的 X 中获取所有可达的顶点。

- CapelliC

Answer 4

这是一个循环检查！我先用trace.命令执行了示例，发现程序在循环一圈后返回到寻找从a到f路径的问题。要使path(a,f)成立，需要path(e,f)成立，简写为以下内容：

(d,f)，(c,f)，(b,f)，然后再次是(a,f)。

为了解决循环，你需要一种机制来防止循环。我的第一个想法是保留节点名称列表，并在检查路径时检查该列表是否不包含当前X。

- nxthor