图中的循环检测

Question

我们有一个图形，包含以下信息：

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

我们被要求定义一个规则cycle(X)，以确定从节点X开始是否存在循环。

我真的不知道如何做到这一点，我尝试遍历节点并检查下一个节点是否再次成为起始节点，但似乎无法使其工作。

- Steve

Answer 1

阿奇的想法是一个很好的起点，但是如果在寻找路径时发现另一个循环，它将创建一个无限循环。

我也已经多年没有使用过Prolog了，但你需要类似于path(X,Y,Visited)这样的东西，其中你要跟踪访问过的节点，以防止无尽的循环。

- Karoly Horvath

Answer 2

我使用深度优先搜索算法，同时记录已访问的节点列表。如果在遍历过程中遇到任何已访问过的节点，则返回true。我已经对小规模数据进行了测试，看起来运行正确。

cycle(X):- cycleh(X,[X]).
cycleh(X,Visited) :- edge(X,Y), (member(Y,Visited) -> !,true; cycleh(Y,[Y|Visited])).

- Gökhan Uras

Answer 3

这应该可以解决问题：

cycle( X ) :-
  cycle( X , [] ).

cycle( Curr , Visited ) :-
  member( Curr, Visited ) ,
  !. 
cycle( Curr , Visited ) :-
  edge( Curr , Next ) ,
  cycle( Next , [Curr|Visited] ) .

尽管它看起来与@Gökhan Uras的解决方案类似--伟大的思想是相似的！或者说是巧合B^)

基本逻辑是如果当前节点已经被访问过(在cycle/2辅助谓词中的第一个子句)，则存在一个循环。此时，我们使用cut(!)截断并宣布成功。使用cut(!)的原因是，如果没有它，回溯将导致重新访问已经访问过的节点，从而形成无限的循环集。

如果当前节点尚未被访问，则我们获取以当前节点为锚点的一条边并进行访问。回溯到cycle/2的第二个子句会访问下一条边，因此一旦特定路径耗尽，cycle/2会回溯并尝试另一条路径。

- Nicholas Carey

Answer 4

我已经有一段时间没有使用Prolog了，但是这是我解决这个问题的方法。

你可以创建规则path(X,Y)，检查从节点X到Y是否存在路径。路径可以是单个边缘或通往路径的边缘。有了这个，很容易找到从节点X开始的循环-- 它将简单地是path（X，X）。这是我的实现（从我的记忆中取出来的，不一定正确，但是给出了思路）：

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

cycle(X) :- path(X,X).

- Archie

---

取出 edge(a,b). edge(b,c). edge(c,b).，查询 ?- cycle(X)。深度优先的 Prolog 会陷入无限循环，并找不到这个循环。 - user502187

Answer 5

如果您的Prolog系统具有前向链接器，则可以使用它来确定循环。但要注意，它可能会消耗相当多的内存，因为它将生成并保留path/2事实。

以下是您需要在不自动消除重复项的前向链接器中制定规则的方式。 \+用于明确消除重复项：

:- forward edge/2.
:- forward path/2.

path(X,Y) :- edge(X,Y), \+ path(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y), \+ path(X,Y).
cycle(X) :- path(X,X).

为了让示例结果更有趣，我已经删除了edge(d,d)。以下是一个样例运行：

?- postulate(edge(a,b)), postulate(edge(a,c)), postulate(edge(b,a)),    
postulate(edge(c,d)), postulate(edge(d,e)), postulate(edge(e,f)), 
postulate(edge(f,g)), postulate(edge(g,e)), cycle(X).
X = a ;
X = b ;
X = e ;
X = f ;
X = g

postulate/1谓词在此处发布事件并保持前向链接器的传播器运行。如何编写您的前向规则取决于您正在使用的Prolog系统各自的库。

P.S.：仍有一些研究正在进行中：
http://x10.sourceforge.net/documentation/papers/X10Workshop2011/elton_slides.pdf

- user502187

Answer 6

我已经有一段时间没有使用Prolog了，但也许这种方法会起作用：一个路径是一系列边缘，每个边缘都从前一个边缘结束的节点开始（例如a -> b，b -> c，c -> d）。微不足道的路径是单个边缘，更复杂的路径可以通过采取现有路径并向其添加边缘来形成。循环是从同一节点开始并结束的路径。您能否使用这些定义构建您的Prolog规则？

- Aasmund Eldhuset