7

我们得到一个包含以下事实的图表：

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。

我真的迷失了如何做到这一点，我尝试遍历节点并检查下一个节点是否会再次成为起始节点，但我似乎无法让它工作

4

6 回答 6

5

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

我也多年没有使用 prolog，但您将需要类似的东西path(X,Y,Visited)，您可以在其中跟踪访问的节点，防止无限循环。

于 2011-07-17T01:47:17.827 回答
2

如果我们在遍历过程中遇到任何访问节点，我将深度优先搜索与访问节点列表一起使用，它返回 true。我用小输入进行了测试，它看起来工作正常。

cycle(X):- cycleh(X,[X]).
cycleh(X,Visited) :- edge(X,Y), (member(Y,Visited) -> !,true; cycleh(Y,[Y|Visited])).
于 2011-07-17T09:50:15.483 回答
2

这应该可以解决问题：

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回溯并尝试另一条路径。

于 2011-07-21T18:39:54.660 回答
1

我已经有一段时间没有使用 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).
于 2011-07-17T00:35:37.337 回答
1

如果你的 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 系统各自的库。

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

于 2012-05-17T23:24:35.697 回答
0

自从我使用 Prolog 已经有一段时间了，但也许这种方法会起作用：路径是一系列边，其中每条边都从前一条边结束的节点开始（例如 a -> b，b -> c，c -> d)。平凡路径是单条边，更复杂的路径可以通过采用现有路径并为其添加边来形成。循环是在同一节点上开始和结束的路径。你可以使用这些定义来构建你的 Prolog 规则吗？

于 2011-07-17T00:33:57.100 回答