swi-ProLog 查找所有可能到达特定结束节点的起始节点

Question

我是逻辑编程的新手。我正在尝试编写一个程序，它可以找到可以到达特定节点的所有节点。

这是我的代码：

link(0, 1).  
link(3, 4). 
link(1, 2).  
link(2, 0). 
link(2, 1).  
link(3, 2).  
link(4, 3).

所以用图表显示在上面，它应该如下所示：

我想做这样的事情：

?- go(X,0).
X=1;
X=2;
X=3;
X=4;
....

也就是说从1,2,3,4都可以到0.

[1->2->0],[2->0],[3->2->0],[4->3->2->0]...

所以我试试

go(X,Y) :- link(X,Y).
go(X,Y) :- link(X,Z),go(Z,Y).

?- go(X,0).
X=2;
X=0;
X=0;
X=0;
X=0;
....

但我不希望 0 作为输出之一，当我已经在 0 时显示我可以转到 0 是没有意义的。而且，它一直在重复。我尝试通过以下方式解决此问题：

go(X,Y) :- link(X,Y).
go(X,Y) :- (X\==Y),link(X,Z),go(Z,Y).

?- go(X,0).
X = 2 ;
false.

我不确定为什么它会在 X=2 处停止。我尝试绘制 ProLog 搜索树，但我仍然不知道为什么我的代码不会继续寻找其他事实 (link(3,4))。似乎它在某个时候停止并且没有继续下面的绿色部分：

我尝试使用 go(1,0) 对其进行测试。去（4,0）。 go(1,0) 和 go(2,0) 成功但是 go(3,0) 和 go(4,0) return 错误：堆栈限制。我发现递归一直在节点3和节点4之间进行。但是我真的不知道如何解决它。

我现在很困惑，请告诉我我的错误是什么，或者如何以正确的方式实现这个功能？谢谢。

Answer 1

问题是你的图表是 cyclic，而不是 acyclic 图。这意味着从某个节点 X 开始，您 [最终] 将 return 到 X.

这意味着（对于初学者）除非您以某种方式处理循环，否则您将陷入无休止的递归循环（直到您运行出栈 space）。

当您遍历图时，您需要维护一些额外的状态（您已经访问过的节点列表）。要在 Prolog 中执行此操作，使用 辅助谓词 是一种常见的习惯用法，它具有相同的名称，但带有额外的参数来携带额外的状态。

所以，尝试这样的事情：

% the public predicate. We seed the visited list here
% with our starting node.
%
% Not to worry if it is an unbound
% variable. It will become bound/unbound as necessary.
traverse(A,B) :- traverse(A,B,[A]).

traverse(A,B,V) :-    % We can get from A to B, if...
  link(A,B),          % - A and B are directly connected, and
  \+ member(B,V)      % - we haven't already visited B
  .                   % - easy!
traverse(A,B,V) :-    % Otherwise, we can get from A to B, if...
  link(A,X),          % - we can get to some intermediate node X,
  \+ member(X,V)      % - that we have not yet visited, and
  traverse(X,B,[X|V]) % - we can get from X to B (adding X to the visited list
  .

swi-ProLog 查找所有可能到达特定结束节点的起始节点

swi-ProLog Finding all possible starting nodes which can arrive specific ending node

prolog

transitive-closure