问题标签 [iterative-deepening]

我在做什么：我正在用 C++ 编写一个国际象棋引擎。我最近更新了我的引擎的 minimax 搜索算法，它使用 alpha-beta 修剪来利用迭代加深，以便它可以在时间限制下运行。这是它的外观：

我的问题：这个实现的问题是，在任何大于 1 的深度搜索时，它会在搜索所需深度之前搜索所有先前的深度。也就是说，这个迭代加深搜索首先搜索深度 1 处的所有移动。然后，它不会在下一次搜索时选择深度 2，而是再次搜索深度 1 ，然后搜索深度 2。然后它会搜索之前的深度 1 和 2搜索深度 3。等等。

我的问题：这是迭代深化应该起作用的方式吗？每次我们增加深度时，我们也搜索所有父节点？我想象每次我们增加深度时，它只会搜索新深度的所有兄弟节点。如果这实际上是迭代深化的工作方式，那么如何只搜索新的深度而不是搜索所有父节点呢？

每次我们增加深度时，我的迭代加深的极小极大值都将整个树搜索到给定深度：

我期望迭代加深的极小极大只在每次增加深度时才搜索新深度：

作为参考，这是我使用 alpha beta 剪枝的（草率的）极小极大函数：

另外，如果有人有兴趣检查它，这是我的完整项目：https ://github.com/ChopinDavid/Maestro-cpp

我不是 C++ 开发人员，所以它可能很糟糕。

我试图call_with_depth_limit/3在 SWI-Prolog 中使用来实现迭代深化，要么我不明白它是如何工作的，要么它行为不端。我有一个发生以下情况的示例：

根据文档，如果可以使用 Limit max recursion 或更少来证明目标，它应该会成功。在第一个限制为 30 的调用中，我们看到 Result 为 25 的结果，因此我希望以 26 的限制调用它会成功。我在模块中使用约束处理规则，以防那里可能存在一些使其行为不端的交互。

编辑：玩过伊莎贝尔的回答后，我想我明白它的行为方式：

• 它像往常一样运行深度优先搜索，但如果它达到 Limit+1 深度，它就像失败一样。
• 失败的分支计入结果。
• 每次它在成功回答后回溯时，都会将 Result 重置为堆栈的当前深度。

看这个例子：

我已经实现了 Korf's Algorithm（魔方的一种求解算法，总是产生最优解）。如果一个解决方案需要 15 到 20 次移动，那么计算机可能会花费整整一天的时间来生成、测试和评估每个节点。

我的解决方案是将这个工作负载分散到多个线程上……尽管我以前为不同的项目做过线程，但我对线程的经验并不多。

有谁知道我如何在 Java 中实现它？

非常欢迎任何意见、建议和想法。

谢谢

我有这种方法可以在二叉树上执行深度优先搜索

现在我必须使用迭代加深深度优先搜索，我知道迭代加深是如何工作的，但我不知道如何实现它。

我不需要任何目标，唯一的目的是搜索树并输出节点值。

编辑：我没有为迭代深化编写的任何代码，这就是我所要求的。

我尝试使用迭代深化深度优先搜索来解决 8 个难题，但有时它有时不起作用。

例如，当我从这个状态开始时：1、2、5、0、3、4、6、7、8 它会找到目标状态。

但在这种状态下找不到它：1、2、5、6、3、4、0、7、8

这是迭代深化搜索的代码：

这是节点类：

我想找到迷宫下面的路径

下面的查询失败，我的代码哪里错了？

我正在解决这个基于 IDDFS 的问题，我正在使用一个基于深度执行递归 DFS 的实用程序函数。我已经为其编写了完美运行的python代码，但我被要求将其转换为CPP，其中出现了问题。

让我借助我正在使用的示例图进行解释，其中有 7 个节点标记为从 0 到 6。它们的邻接列表如下：

我试图找到深度为 2 的 4 到 2 之间的 DFS，其答案应该是 [4,5,2]。

现在，我将附加工作 python 代码及其输出：

我在那里添加了额外的打印语句来帮助调试和理解流程。这为命令 dfs_util([4],2,2) 提供的输出是：

正如我们所看到的，这将返回正确的输出。

当我尝试将其转换为 CPP 时，我编写了以下函数：

使用相同的输入参数，理想情况下它应该返回与上面提到的 python 代码相同的输出。但相反，它会打印以下内容：

在写出逻辑的同时，我开始明白，在进入调用 dfs_util([4,1],2,1) 的递归循环后，它不会进入进一步提到的 for 循环，因此不会探索连接到的边节点 1。

我觉得它在技术上应该可行（至少当我尝试逐行解决并在纸上解决时）。

我正在解决一个类似的背包问题：这是打印出价值高于数字但重量低于限制的对象的第一个组合。

我试过了：

我知道这棵树看起来像这样

但我不知道如何用正确的逻辑修复代码希望有人能帮我一把。

谢谢！！