问题标签 [transitive-closure]

我正在检查图表是否已连接，并且由于某种原因在它应该为真时变得错误。

我正在为我的谓词做的是检查 allConnected([a,b,c]) 中的每个节点是否都已连接。我应该是真实的，但无法查明我的错误，我尝试使用跟踪，但它没有帮助。

我是这样写的。但它只成功地找到了祖父母，而不是更远的地方。我如何编写它以找到所有可能的祖先。也就是说，如果存在这样的事实，找到曾祖父母甚至更远？

给定

仅退货

我有以下规则可以找到图表中的所有路径。

但是，我还想为每个节点 n添加边缘 n->n如果不存在的话。

在没有任何节点关系的情况下如何做到这一点？

我正在学习 Prolog，当我尝试查找路线时出现蠕变错误。我认为我所做的是递归，因为这是在没有直路时找到路线的方法。

这是代码：

当我试图找到时，假设从伦敦到罗马的路线

我收到此错误：

我究竟做错了什么？我应该定义别的东西吗？

提前致谢！

我正在尝试解决这个Pebble Solitaire问题，这是我的代码的一部分：

是的，很丑。

但是，当我调用 时findall( Value, play(Game, Value), Values)，其中 Game 只是 45 和 111 的任意序列（例如 [45, 111, 45, 45, 45, 45, 111, 111, 111, 45, 45, 45]），Values 只是永远与 2 个项目的列表统一（编辑：不正确，它与更多项目统一，请参阅评论）。

据我了解，当我调用 findall/3 时，它会在基本情况谓词中找到一个解决方案（它只计算鹅卵石的数量并将其与 X 统一），然后从其他 20 个游戏谓词中的任何一个中找到一个解决方案，然后就……停下来？

我需要它继续下去，直到找到所有解决方案。为什么它在 2 个解决方案后停止？我怎样才能让它继续？

所以我想写一个代码来做无环图的传递减少。所以元素是：

(3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

这是我到目前为止所写的：

运行后，我希望删除 (4,1) 后得到以下内容：

但相反，它返回：

我无法弄清楚我做错了什么。如果有人能指出错误，那就太好了！

PS：传递减少是删除图的冗余边。例如：

如果 ( A -> B ) 和 ( B -> C )，则 ( A -> C )，换句话说：如果 A 连接到 B 并且 B 连接到 C，那么 A 也连接到 C。并且在这种情况（ A -> C ）是多余的，因为 A 可以通过 B 到达 C 因此应该被删除。

几个月前，我参加了一场关于 CodeForces 的比赛，从那以后我一直在尝试不同的解决方案来解决它。

该问题基本上由包含有向图的节点和边的输入组成。基本上，如果：A 指向 B，B 指向 C，C 指向 D，那么我们可以说 A 也指向 C，并且 D。B 也是如此，指向 D。你得到这个想法。

我现在的问题是，我尝试了一些不同的解决方案，其中一些有效但被时间限制卡住了。另一个是我提高效率的最佳尝试，但在某些测试中失败了。不幸的是，我不允许看测试。

这是我的代码的骨架，如果您不想在这里查看整个代码，下面会提到 TransitiveClosure() 函数：

这是 TransitiveClosure 的有效但缓慢的尝试：

我也尝试递归地做，但这恰好是错误的，我不确定它背后的逻辑是什么部分是错误的：

如果相关，我的代码使用邻接矩阵的其他尝试和其他可以在这里找到：http: //pastebin.com/A0a186V5。

感谢您对此的意见，以及我可以做些什么来使其更快。另外，如果你能告诉我我能做些什么来使我的第二次递归尝试工作。请原谅我在代码中缺少注释。

我不确定可以通过此实现的最佳复杂性是多少，因此请引导我走上正确的道路。也许还有其他一些我不知道的算法可以查看。

谢谢你，很抱歉这么长的帖子！

有人可以详细说明 travel(A,B,Visited,Path) 和 travel(A,B,P,[B|P]) 的功能/条件 .. 此代码在图中找到路径 A 和 B 之间的路径

这就是我到目前为止所拥有的。我需要证明，如果两个站通过第三个站连接，它们是相互连接的

我有这种类型的知识库：

我的目标是，给定一个起源和一个命运，在到达最终节点之前遍历所有现有节点一次。

到目前为止，这就是我所得到的：

为了处理双重连接，例如connect(a, b). connect(b, a).，我使用一个列表来保存我经过的每个节点，并且在进入递归调用之前，我确保我要访问的节点不属于该列表。

现在我需要确保在到达最后一个节点之前遍历所有现有节点。我完全不知道如何解决这个问题。我怎么能确定我在到达最后一个节点之前访问了所有其他节点？