问题标签 [iterative-deepening]

我有一个正常的二叉树，我试图在使用 c 时应用迭代加深深度优先搜索：

我正在使用一个函数将节点插入树中，现在我需要将搜索函数实现为如下所示： function search(root,goal,maxLevel) 所以它使用深度优先搜索但搜索到特定的最大级别然后停止这是我的第一次尝试，它没有工作：

请帮忙，谢谢...

我正在尝试开发一个简单的国际象棋引擎，但我正在努力解决它的性能问题。我已经使用 alpha-beta 修剪和迭代加深（没有任何额外的启发式方法）实现了 Negamax，但我无法获得超过 3-4 层的合理搜索时间。这是游戏开始时我的程序日志的摘录：

它表明分支因子大约是 10。我已经读过，通过正确的移动排序，我应该得到大约 6 的东西，所以我怀疑我的排序是错误的。它目前以这种方式工作：

1. 游戏树节点有一个其子节点的链表；最初，捕获和提升是在安静的移动之前放置的
2. 在搜索过程中，增加 alpha 或导致 cutoff 的 child 被放置在列表的开头
3. 在下一次迭代加深 PV 时应先搜索

这是一种正确的方式来订购移动和我得到的分支因子是可以预期的吗？目前我正在使用一个简单的静态评估函数，它只考虑位置的材料差异 - 这可能是截止率低的原因（如果还考虑了数字的流动性，我会得到类似的结果）？诸如减少无效移动或杀手启发式等技术是否会显着帮助（不是 10-15%，而是一个数量级）？我不希望我的引擎很强大，但我希望分支因子约为 6。

我想实现迭代深化（增量树构建）。这是我将询问的代码的一部分：

从我读到的关于带有时间限制的 invokeAny() 的内容中，它应该在达到最后期限后立即结束执行其 Callable 对象。当我长时间睡眠而不是我的函数 iterativeDeepening(depthLimit, board) 时，它会起作用。如何使它与我的功能一起使用？下面我将代码粘贴到这个函数中：

如果您知道更好的方法或知道如何成功停止执行我的功能，请告诉我。我还尝试了本主题中提到的可运行接口： How to stop execution after a certain time in Java? 但它只是工作相同。

我已经在互联网上搜索了有关 IDS 算法的一些示例，但它们都是递归的，并且据我所知，迭代不是递归的。那么您能给我一些 IDS 算法的示例吗？（实现会很棒并且没有递归）

提前致谢！你会是一个救生员！

我有一个树遍历算法，它通常在 O(b ^m ) 中运行，其中 b 是分支因子，m 是最大深度。

使用迭代深化，这个算法一遍又一遍地运行，m 次以增加深度：

O(b ^m ) = b⁰ + b¹ + b² + ... + b ^m

基于我对时间复杂度的有限理解，我们采用最大元素，因为随着时间的推移，它是最重要的元素，因此该元素将是 b ^m，其中 m 是达到的最大深度。

因此，有了这些知识，我会得出结论，迭代深化算法也在 O(b ^m ) 中运行。

但是我很难理解，从逻辑的角度来看，无论算法是在深度 m 处运行一次，还是在深度 m 处运行一次，树遍历如何具有完全相同的时间复杂度。

b ^m本质上小于 Σ _k=0,..,m b ^k。因此迭代加深的时间复杂度不应该更高吗？

还是有什么我不明白的地方？

我似乎无法解决大多数时候 A* 优于 IDA* 的原因。我的教授说原因不是因为早期（更接近根）节​​点在达到 f 限制后随着 IDA* 回溯而不断被重新探索，而是因为 A* 维护了一个开放和封闭的列表，因此给定状态不会通过树多次探索，而在 IDA* 中，如果树中有多个路径到给定节点，它将一次又一次地探索这些节点。我的问题与 IDA* 相同，即。是否可以使用开放和封闭列表来实施 IDA*，如果不是，为什么？

我正在为计算机国际象棋程序的 alpha-beta 搜索实现迭代深化，并希望包含搜索的时间限制。我想知道在深度为 5 的搜索中达到时间限制的后果。如果这个不完整的搜索找到了一个新的主要变体，那是否可以保证至少与深度为 4 的完整搜索发现的主要变异？否则，我似乎应该丢弃在 5 深度处通过不完整搜索找到的任何内容。

我正在 Prolog 中编写目标搜索代理。我有两个谓词名为search. 一个有问题Type == explore，另一个在哪里Type == climb。
请注意，使用的深度是一个常数 = 10。该程序为我所有的测试用例提供了正确的路径，但是它们并不是最短的，所以从这里我得到了使用length(Actions,_).
它适用于第一个search谓词，但是当我尝试为后一个搜索谓词添加类似的Type == climb内容时，它会进入无限循环/花费太长时间。这就是我所拥有的：

为什么会这样？

这是完整的代码：

编辑：
好的，现在我知道它与指定的“深度”有关。MaxDepth我从中删除了约束depthfirst，它现在正在工作。然而，最初的 depthfirst 是在给定的 Depth 中找到解决方案，那么为什么它不能使用迭代深化来做到这一点 - 按照我指定的方式完成？

我目前有一个深度优先搜索，如下所示：

这是在节点上的树上工作。

是否可以以某种方式编辑此代码以执行迭代深化搜索？说限制2？我想不出一种方法来跟踪水平。

我有一个 DFS 搜索，现在我正在尝试用这个 DFS 实现迭代深化搜索，但我真的不明白我该怎么做。我尝试了很多方法，但最后我发现它是错误的！你对我应该做哪些改变有什么建议吗？