15

我对 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……这甚至是不对的！这段代码可能有什么问题？

4

4 回答 4

15

图中的循环。您需要跟踪您正在访问的节点，并检查它们。试试这个，使用带有累加器的辅助谓词来跟踪访问的节点：

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).
于 2014-01-17T22:07:29.500 回答
7

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

实际上，已经有很好的替代方案可用，在某些情况下，有用的谓词已准备就绪：例如，在 library( ugraph ) 中，有可达/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)

将所有边放入 Es 中，并按照库的要求使用符号，

vertices_edges_to_ugraph([],Es,G)

在 G 中构建相应的图

reachable(X,G,Path)

列出从 X 到达的所有顶点的路径（duh）

member(Y,Path)

查看路径中是否存在 Y。

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

于 2014-01-16T15:38:52.610 回答
7

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

幸运的是，是中的一个常见习语！

要表达 的非自反传递闭包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.
于 2016-05-13T16:50:38.570 回答
2

它正在检查一个循环！我使用之前的命令执行了示例trace.，并且看到程序在循环后返回问题以找到从 a 到 f 的路径。path(a,f) 需要 path(e,f) 为真，简而言之，我们需要为真：

（d，f），（c，f），（b，f），然后是（a，f）。

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

于 2014-01-16T12:44:18.517 回答