问题标签 [iterative-deepening]

问题是关于树搜索。我相信我了解 DFS、BFS 和 IDDFS 之间的区别。在最优性、完整性、时间复杂度和空间复杂度方面，IDDFS 在树搜索方面具有更好的性能。

那么，我什么时候想在树搜索中运行 BFS 或 DFS 而不是 IDDFS？

谢谢

这是迭代深化搜索，我想跟踪目标状态之前生成的节点。我使用 RUNNING_TIME 作为计数器，然后将其分配给树中的每个节点。问题是，因为递归 RUNNING_TIME 增加了不止一次，并且该值不再有效。因此，我得到了 BFS 的 RUNNING_TIME，它比理论上没有意义的这个更好（仅在最坏的情况下）。你知道我应该如何在我的方法中增加这个值吗？我真的不知道，谢谢。

编辑：我也忘了提到我得到了到目的地的正确路径，但只有“RUNNING_TIME”变量错误地增加了。

在阅读了国际象棋编程维基和其他资源之后，我一直对迭代深化的确切目的感到困惑。我原来的理解是这样的：

它包括在深度 = 1、深度 = 2 等处执行的极小极大搜索，直到达到所需的深度。在对每个深度进行极小极大搜索之后，根据该搜索的结果对根节点的移动进行排序，以便在下一次搜索中以深度+1 的最佳移动排序，因此在下一次更深的搜索中，搜索 PV 移动，然后是下一个最佳移动，然后是之后的下一个最佳移动，依此类推。

这个对吗？当我读到关于 MVV-LVA 排序，特别是关于排序捕获，以及使用哈希表等时，我产生了疑问。例如，此页面推荐以下移动顺序：

1. 最左边路径的迭代深化框架的上一次迭代的主要变化的 PV 移动，通常由 2 隐式完成。
2. 从哈希表中移动哈希
3. 获奖捕获/促销
4. 平等的捕获/促销
5. 杀手动作（非捕获），通常首先是伴侣杀手
6. 按历史启发式排序的非捕获等
7. 丢失捕获

如果是这样，那么如果只需要 PV-move，那么从每个深度对 minimax 进行排序又有什么意义呢？另一方面，如果 ID 的全部点是 PV-move，那么从每个单个 minimax 深度搜索到所需的深度只是为了计算每个深度的 PV-move 不是浪费吗？

ID的具体用途是什么，它节省了多少计算量？

我正在尝试对 k 谜题实施迭代深化搜索。我设法找到了目标节点。但是，我无法从目标节点回溯到开始节点以找到最佳移动。我认为这与 IDS 中的重复状态有关。目前，我正在跟踪 IDS 算法中的所有访问状态。

这是我算法的当前实现。在下面的代码中，moves_dict存储每个节点的先前状态并移动到当前状态。

我已经有一段时间了。我使用一个 hashMap 将状态字符串映射到它的深度，并且当相同的状态出现在较浅的深度时添加节点

编辑 此测试用例的最佳解决方案深度为 22。初始状态：[[1,8,3],[5,2,4],[0,7,6]] 目标状态：[[1,2,3],[4,5,6],[7,8,0]]

我正在尝试通过迭代搜索来解决 15 个拼图（滑动拼图）。这是我的初始状态：

这是我的目标状态：

我有一类节点来代表我的状态。这个类看起来像这样：

这是我的 ids(iterative deppening search) 功能：

我不知道为什么，但是当 depth = 1 和 limit = 1 时，该函数卡在 while 循环中。我不明白为什么它无法达到目标。

我正在尝试通过迭代深化搜索来解决 15 谜题（滑动谜题）。

这是我的初始状态：

这是我的目标状态：

我有一类节点来代表我的状态。这个类看起来像这样：

这是我的搜索功能：

目标状态位于搜索树的深度 9，但我的函数卡在限制 6 中，我不知道为什么。当目标深度为 6 或更少时，函数会找到解决方案，但当深度大于 6 时，函数会运行很多时间并卡住。

我有以下代码：

在哪里move给我们你可以使用的可能的动作，并且path应该给我们你必须从 X 到 Y 采取的路径。

问题是谓词path不能按我的意愿工作，即，如果我输入path(state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X).错误：超出本地堆栈，但我希望那个 X 是

那么我做错了什么？

我知道我可以通过在 negamax 和静息函数中调用移动生成器之前检查时间限制来实现这一点。但我想知道是否有一种方法可以在单独的线程上运行时间限制检查，并在 C++ 中超过时间限制时中断循环的执行。

我在 python 中创建了一个连接 4 AI，并且为此使用了具有迭代加深和 alpha beta 修剪的 minimax。对于更大的深度，它仍然很慢，所以我想实现一个转置表。在阅读了它之后，我想我明白了一般的想法，但我还没有完全让它发挥作用。这是我的代码的一部分：（极小值的最大化部分）：

现在我正在使用 zobrist 散列方法对板进行散列，并且我正在使用有序 dict 将散列板添加到其中。在这个哈希键中，我添加了该板的值和该板的 bestMove。不幸的是，这似乎使算法选择了错误的动作（它以前工作过），有谁知道你应该将棋盘状态放在缓存中的什么位置，以及你应该从缓存中的哪个位置获取它们？

我创建了一个带有 alpha beta 修剪的 minimax 函数，我用迭代加深来调用它。问题是，当计时器完成时，该函数会继续运行，直到它在计时器用完之前开始的深度完成。

我想要什么：当计时器用完时，minimax 函数应该退出并且要么不返回（我将最佳移动保持在 minimax 之外，请参阅下面的 minimax 调用代码），或者返回先前计算的最佳移动。我似乎无法弄清楚如何在 minimax 函数中实现它，我尝试的所有结果都导致它仍然完成它当前的深度。

极小极大函数：

迭代深化的函数调用：