问题标签 [transitive-closure]

我想用可交换和传递的属性来模拟 Prolog 中的等价性，这就是我所做的：equal/2 将作为事实提供。

但是我在使用上述解决方案时遇到了性能问题，试图计算transitiveEqual/2（大约花了20分钟），我从equal/2计算得非常快，大约有2KsymmetricEqual/2事实，所以它一定是规则的原因对于transitiveEqual/2，任何人都可以提出任何改进建议吗？

非常感谢。

我有一个表表示组织层次结构的传递闭包（即，它是一个具有单个根的树）：

我有另一个表，其中包含每个用户被允许访问的组织：

系统向用户显示与用户可以访问的每个组织相关的支出汇总。我总是可以首先向用户展示公司的视图（即根），向用户展示直接子组织的列表以及他的组织对总数的贡献。在大多数情况下，只有一个孩子，并且用户需要在看到多个孩子之前向下钻取几个级别。我更愿意从第一个显示多个孩子的组织（即 LCA）开始演示。

对于给定的用户，我可以很容易地找到到根目录的路径集，但在找到最不共同的祖先时遇到了麻烦。我正在使用 postgresql 9.1，但更喜欢与数据库无关的解决方案。在最坏的情况下，我可以将 root 的路径拉回到应用程序的代码中并在那里计算 LCA。

我写这个程序给我这个结果：“X=john”“Y=jane”

但是如果运行这个程序这样结果：我认为程序进入循环！我想在真实答案后停下来！

我有错误！如何解决这个问题？

通过调试：

等等..为什么喜欢（简，_G2267）？？？？？？

我正在尝试实现 Warshall 的算法来快速计算 LR(1) 闭包。

我想我了解它对 LR(0) 的工作原理：

• 图的节点是LR 项，例如A → B • C
• 边缘是从A → B • C到的“过渡”C → • D

问题是，LR(1) 需要计算前瞻，我不知道如何将它们合并到算法中。
在我看来，即使我知道任何给定 LR 项目的传递闭包，我仍然需要通过所有相同的计算来确定每个项目的前瞻集是什么。

甚至可以使用 Warshall 的算法来计算规范的 LR(1) 闭包，还是仅适用于更受限制的情况（如 LR(0)、SLR(1) 等）？

我在 MySQL 存储过程中实现了 Warshall 算法。不幸的是，该过程需要很长时间才能完成。我是编写存储过程的初学者，你知道我能做些什么来让它更快吗？

简要说明：我正在尝试计算邻接表的传递闭包。我想知道，连接了哪些节点（直接在一条边上，或间接在更多边上）。例如：

下图说明了图表：

_{图片来自维基共享资源： https ://en.wikipedia.org/wiki/File:Transitive-closure.svg}

您可以在SQL Fiddle或此处查看代码：

在我的计算机上运行具有 1466 条记录的表需要 45 秒：

上下文，首先。我有以下双向图。

在 Prolog 中表示如下：

所以我有节点之间的关系，然后节点之间的连接相关，正如我之前所说，在两个方向上。

我想要做的是一个序言定义，path(X,Y)能够判断图中两个节点之间是否存在路径（如果两个节点之间至少存在一条路径，则为 true，如果两个节点之间不存在路径，则为 false）。

因此，此模型中的目标输出应如下所示：

我知道这涉及使用访问列表，并且我已经看到了这样的示例，但是给出了两个节点之间的所有可能路径。然而，这不是我要找的。我正在寻找的是一个定义，它检测两个节点之间是否存在路径，而不是给出两个节点之间的所有可能路径。

编辑：所以，感谢@mbratch，我现在可以将建议的问题调整为解决方案：

我得到了以下程序：

并询问是否将证明树算法应用于以下查询：

证明树是无限成功树，还是无限失败树？

现在我看到了，在树的构建过程中，你会一遍又一遍地应用路径规则 1，创建一棵无限的树，而永远不会达到路径规则 2。

从而创建一个无限的故障树。但是我的解决方案说这是一棵无限的成功树，我的问题是：我是对的还是我的教授是对的？:]

我很困惑，这两者有什么区别？

循环和电路，所以如果可能的话，请用图表来确定。

我想到的是循环总是在无向图中电路总是有向图。如果我错了，请纠正我？

我需要使用 Haskell 在列表上生成传递闭包。

到目前为止，我得到了这个：

输出 1：

输出 2：

问题在于第二个输出。它不是在新生成的列表上检查额外的传递闭包，而是返回结果。

为了原型 haskell 代码，我使用了这个Python 代码：

输出：

这是我在 Haskell 函数中需要的正确输出。

如何在我的 Haskell 代码中做同样的事情？（我需要if从 Python 代码重新创建语句到 Haskell 代码）

我试图通过解决节点和弧的存在约束来确定有向图的形状，例如，二进制变量V1V2是1是否存在从节点V1到的弧V2。我想表达可达性约束（或者，找到一个传递闭包），例如，要求图是连接的，或者有一条从一个给定节点到另一个给定节点的路径。

我已经看到 SICStus Prologfd_closure用于此目的，但我在 SWI Prolog 中找不到类似的东西。我应该使用CHR吗？我一直在查看弧/路径一致性示例，但我不确定我是否在寻找正确的方向。