图中的循环检测
我们得到了一个包含以下事实的图表：
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 开始的循环。
我真的不知道如何做到这一点，我尝试尝试遍历节点并检查下一个节点是否再次成为起始节点，但我似乎无法让它工作
We are given a graph with the following facts:
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)
And we are asked to define a rule, cycle(X), that determines if there is a cycle starting from the node X.
I am really lost on how to do this, I tried attempting to traverse the nodes and checking if the next one would be the starting one again but I cannot seem to get it to work
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
Archie 的想法是一个很好的起点，但如果在搜索路径时发现另一个循环，它将创建一个无限循环。
我也已经很多年没有使用 prolog 了，但是您将需要像
path(X,Y,Visited)这样的东西，您可以在其中跟踪访问的节点，防止无限循环。Archie's idea is a good starting point, but it will create an infinite loop if it finds another cycle while searching for the path.
I also haven't used prolog for years, but you will need something like
path(X,Y,Visited), where you keep track of the visited nodes, preventing the endless loops.我将深度优先搜索与访问节点列表一起使用，如果我们在遍历过程中遇到任何访问节点，它会返回 true。我用小输入进行了测试，看起来工作正常。
I used Depth First Search with visited node list if we encounter any visited node during traversal it returns true. I tested with small inputs it looks like working correctly.
我已经有一段时间没有使用 Prolog 了，但这是我解决这个问题的方法。
您可以创建规则
path(X,Y)来检查是否存在从节点X到Y的路径。路径是单条边或通向路径的边。有了这个，就很容易找到从节点X开始的循环 - 它将只是path(X,X)。这是我的实现（取自我的头脑，不一定正确，但给出了想法）：I haven't been using Prolog for some time, but here is my approach to this problem.
You could make rule
path(X,Y)that checks if there exists path from nodeXtoY. A path is a single edge or an edge leading to a path. Having this, it's easy to find cycle starting from nodeX-- it will be simplypath(X,X). Here is my implementation (taken from the top of my head and not necessarily correct, but gives the idea):这应该可以解决问题：
虽然它看起来与@Gökhan Uras 类似 - 英雄所见略同！或者 B^)
基本逻辑是，如果当前节点已经被访问过，则有一个循环（
cycle/2辅助谓词中的第一个子句。此时，我们剪切（！）并声明成功 剪切（！）的原因是，如果没有它，回溯将导致重新访问已经访问过的节点，从而导致无限循环如果当前节点尚未被访问，我们会抓取锚定在当前节点的边 。节点并回溯到该节点。
cycle/2的第二个子句访问下一条边，因此一旦特定路径耗尽，cycle/2就会回溯并尝试另一条路径。This should do the trick:
Although it appears to be a similar solution to @Gökhan Uras -- great minds think alike! Or something B^)
The basic logic is that you have a cycle if the current node has already been visited (the first clause in the
cycle/2helper predicate. At that point, we cut(!) and declare success The reason for the cut (!) is that without it, backtracking would result in revisiting a node already visited and thus an infinite set of cycles.If the current node has not been visited, we grab an edge anchored at the current node and visit that. Backtracking into the 2nd clause of
cycle/2visits the next edge, so once a particular path is exhausted,cycle/2backtracks and tries another path.如果您的 Prolog 系统有前向链接器，您可以使用它来确定周期。但要小心，它可能会消耗相当多的内存，因为它会生成并保留
path/2事实。以下是您需要如何在不会自动消除重复项的正向链接器中制定规则。
\+的作用是显式消除重复项：为了使示例在与结果相关的方面更加有趣，我删除了
edge(d,d)。下面是一个示例运行：这里的
postulate/1谓词发布一个事件并保持前向链接器的传播器运行。如何编写转发规则取决于您使用的 Prolog 系统各自的库。PS：仍有一些研究正在进行中：
http://x10.sourceforge.net/documentation/papers/X10Workshop2011/elton_slides.pdf
If your Prolog system has a forward chainer, you could use it to determine cycles. But watch out, it might eat quite some memory, since it will generate and keep the
path/2facts.Here is how you would need to formulate the rules in a forward chainer that does not eliminate automatically duplicates. The
\+is there to explicitly eliminate the duplicates:To make the example a little bit more interesting what concerns the result, I have dropped the
edge(d,d). Here is a sample run:The
postulate/1predicate here posts an event and keeps the propagator of the forward chainer running. How to write your forward rules depends on the Prolog systems respective library you are using.P.S.: There is still some research going on:
http://x10.sourceforge.net/documentation/papers/X10Workshop2011/elton_slides.pdf
自从我使用 Prolog 以来已经有一段时间了，但也许这种方法会起作用：路径是一系列边，其中每条边都从前一条边结束的节点开始（例如 a -> b， b→c，c→d)。普通路径是一条边，更复杂的路径可以通过采用现有路径并向其添加一条边来形成。循环是在同一节点上开始和结束的路径。您可以使用这些定义来构建您的 Prolog 规则吗？
It's been a while since I used Prolog, but perhaps this approach will work: A path is a sequence of edges where each edge starts on the node the previous edge ended on (e.g. a -> b, b -> c, c -> d). The trivial path is a single edge, and more complex paths can be formed by taking an existing path and adding an edge to it. A cycle is a path that starts and ends on the same node. Can you use these definitions to build your Prolog rules?