问题标签 [transitive-closure]

我正在尝试编写一个谓词，该谓词在无环图中写出从一个节点到另一个节点的所有方式。如果我有这些节点/边。

然后我尝试了类似的东西：

但不知何故，我需要递归地执行此操作，我需要帮助。有人有什么想法吗？谢谢

就我被告知我需要的方法而言，我已经有了该程序所需的框架。但是，除此之外，我在弄清楚如何开始编写这个程序时遇到了麻烦。详细情况如下。 我不是要求为我完成我的程序，实际上我只是对如何开始感到困惑。我知道我需要读取用户输入来获取文本文件，我们在我的大学使用扫描仪，但我不知道这是否需要在构造函数中、main 中或其他方法中。

1. 接受单个命令行参数 - 即包含行分隔的字符串对列表的文本文件。这些字符串对将表示依赖图中的边。例如，读取为：A.java B.java 的行表示从 A.java 到 B.java 的依赖边。表示上图的文件可能如下所示： Main.java A.java A.java B.java

2. 将从文件中读取的每个字符串映射到唯一的整数标识符。这种映射将使将文件名转换为数组索引变得容易。

3. 将每个唯一整数标识符（从上面）映射回原始字符串。

4. 计算表示字符串之间依赖关系的邻接矩阵。

5. 对邻接矩阵执行传递闭包操作以生成表示字符串之间传递依赖关系的新闭包矩阵。执行此操作的一种简单方法是 Floyd-Warshall 算法 - 您可能想对这个主题进行一些研究。

6. 您的输出必须遵循课程网站上示例输出文件所示的格式。课程网站上有一个示例输入文件和相应的输出文件。在此示例中，您的输出必须具有相同的格式。目标是使输出信息具有有吸引力、可读的格式，清楚地表明下面列出的每个方法都可以正常工作。

7. 具有私有字段返回类型的方法，例如 getNameIdMap、getIdNameMap、getRoots 等，而不是返回我们类的内部状态的可变部分，即应该返回该映射的副本（克隆）列表。这样，调用者就可以得到一个完全可用的对象（例如，列表或地图），而不会影响类的内部状态。

您的程序还应提供以下方法：

1. public Map getNameIdMap() - 返回从字符串到唯一整数标识符的映射。整数标识符表示给定字符串的邻接矩阵和闭包矩阵的索引。注意：在 Python 中，返回值必须是一个字典，其中键是字符串，值是整数。

2. public Map getIdNameMap() - 返回从唯一整数标识符到原始字符串的映射。注意：在 Python 中，返回值必须是一个字典，其中键是整数，值是字符串。

3. public int[][] getDependenceGraph() - 返回表示文件之间依赖关系的邻接矩阵。

4. public int[][] getTransitiveDependenceGraph() - 在应用传递闭包操作后返回依赖图。

5. public List getRoots() - 返回一个字符串列表，这些字符串对应于没有其他文件依赖的文件（例如，上面示例中的 Main）。注意：在 Python 中，返回值也是一个字符串列表。

6. public List getLeaves() - 返回一个字符串列表，这些字符串对应于不依赖其他文件的文件（例如，上例中的 B）。注意：在 Python 中，返回值也是一个字符串列表。

7. public void removeLeaf(String leaf) - 从邻接和传递闭包矩阵中删除一个叶子。这意味着如果 X 依赖于 Y 并且 Y 是被移除的叶子，那么 X 对 Y 的依赖也会被消除。这可能会或可能不会使 X 成为新的叶子。考虑在矩阵中使用一个特殊的数字（即，除了 0 和 1）来表示该文件已被逻辑删除。

8. public List firewall(String node) - 计算指定文件的“类防火墙”。在软件工程中，类防火墙概念指出，当对系统进行维护时，只有更改的类和受更改影响的类需要重新测试。注意：在 Python 中，返回值也是一个字符串列表。对于此方法，您应该重新测试间接和直接受影响的类。例如，如果 A 类依赖于 B 类，B 类依赖于 C 类，而你更改了 C 类，那么你应该重新测试 A 类和 B 类。

9. public void printParallelGroups() - 假设我们想要并行编译文件，我们需要识别不会触发其他文件编译的文件；这些是依赖图中的叶子。此方法识别可以并行编译的文件，打印该文件列表，并将它们从图中删除。该方法应重复此过程，直到所有文件都已“编译”。

我在 Prolog 中遇到以下问题，例如，我在知识库中有几个事实：

我只对获取从 X 到 Y 的所有可能路线的列表感兴趣。我知道我必须使用递归规则，并且必须将访问过的地方添加到列表中以停止循环反复运行作为飞行路径在知识库中有几个循环。

到目前为止我所拥有的是：

出于某种原因，当我查看跟踪时，规则在尝试检查 not(member(Y,T)) 时失败，但我不明白为什么会这样。

我有以下事实构成了我地牢的翅膀。

现在我想检查我的一个房间是否连接到另一个房间，然后可能显示其中一个可能的路径。我试图做这样的事情， connected(X,Y):-path(X,_,Z),path(Z,_,Y). 但它一直给我错误，我做错了什么。

许多谓词本质上使用某种形式的传递闭包，只是发现也必须解决终止问题。为什么不使用以下方法一劳永逸地解决这个问题closure0/3：

是否存在此定义不能用于实现传递闭包的情况？

为什么要区分 / 2？

详细回答@WouterBeek 的评论：dif/2或者iso_dif/2是理想的，因为它们能够显示或发出潜在问题的信号。然而，在当前的实现中，顶层循环通常隐藏了实际问题。考虑一下这个目标closure0(\_^_^true,a,b)，它本身肯定是有问题的。使用以下系统时，实际问题直接不可见。

两个顶级循环都没有显示我们真正想看到的：悬空约束。在 SICStus 中，我们需要一个伪变量来产生一些替换，在 SWI 中，查询必须用call_residue_vars/2. 以这种方式，现在显示了所有附加了约束的变量。

我需要定义一个谓词 acyclic/1 ，它将一个图作为输入并确定该图是否是非循环的。所以根据我的理解

将返回 no 和

将返回是

我做了一个谓词来确定图中的 2 个节点是否连接，如果连接，它们将返回是。

有没有办法可以使用它来确定图形是否是非循环的？

我不想使用任何预定义的谓词。

我需要创建一个谓词isConnected/1，将图形作为参数并确定对之间是否存在无向路径。

假设我有一个边列表（G图在哪里）：

因此，由于 3 和 4 之间没有边，这应该会失败。
我将如何解决这个问题？我是否必须遍历每个边缘并将边缘记录在列表中？还是有更好的方法来做到这一点？

假设我们有一个机器人，它在棋盘上，可以像国王一样移动。

棋盘的坐标从 [1,1] 到 [8,8]。

起始位置是 [1,1]，最终位置是 [8,8]。有一个列表 X 包含障碍物坐标列表，例如 [[1,4],[2,5],[5,6]]。问题是：有没有一种可能的方式让机器人从起始位置移动到最终位置。

我做了这个谓词：

但是有一个错误，它没有返回任何值。递归永远不会停止我找不到原因。

我希望你能帮我解决这个问题。

我正在尝试了解 Prolog 中的深度优先搜索算法，我遇到了以下代码

我有点明白发生了什么，但我一辈子都找不到或发明一些我可以用它的事实。

请帮忙。即使这是一组非常简单的事实，我只需要从某个地方开始

先感谢您

我需要帮助来解决迷宫路径。提前致谢

编写一个谓词，定义任意两个相邻点（例如 X 和 Y）之间的路线，基于它们之间存在链接这一事实，以及一个涵盖任意两个非相邻点之间路线的更一般情况的递归谓词（例如 X 和 Z）通过建立一个事实，即 X 和迷宫中的第三点（比如 Y）之间存在链接以及 Y 和 Z 之间的路线。

两个特殊房间——一个连接到“a”并称为“Entry”，另一个连接到“f”并称为“Exit”。添加一组事实以反映两个新房间。使用任务 1 中的谓词，编写一个谓词，查找入口和出口之间的所有可能路线，并创建已访问房间的列表。编写另一个谓词，在每次迭代结束时，或者换句话说，每次到达 Exit 时，在交互式控制台中显示列表。编写一个测试计划，显示您的预期结果和实际结果。评估此解决方案并确定任何潜在问题以及可能导致其发生的情况。

这个解决方案的问题是循环。如果我想链接（a，f）序言说不。我的谓词有什么问题。

| ?-链接（a，b）。链接（b，c）。链接（c，d）。链接（f，c）。链接（b，e）。链接（d，e）。链接（e，f）。

路线（X，Y）：-链接（X，Y）。路线（X，Y）：- 链接（X，Z），路线（Z，Y）。是的

是的

是的

是的

是的

是的

是的

！---------------------------------------- ！错误 20：未定义谓词！目标：路线（_31102，_31104）：-链接（_31102，_31104）

中止 | ?- 链接（a，f）。不

| ?- 路线（X，Y）。X = a , Y = b ;

X = b , Y = c ;

X = c , Y = d ;

X = f , Y = c ;

X = b , Y = e ;

X = d , Y = e ;

X = e , Y = f ;

X = a , Y = c ;

X = a , Y = e ;

X = a , Y = d

;

X = a , Y = d

| ?- 链接（X，Z）。X = a , Z = b

| ?- | ?- 链接（X，Z）。X = a , Z = b ;

X = b , Z = c ;

X = c , Z = d ;

X = f , Z = c ;

X = b , Z = e ;

X = d , Z = e ;

X = e , Z = f