问题标签 [iterative-deepening]

我读过（例如，http://radagast.se/othello/Help/order.html），首先搜索每个级别的最佳移动（可以使用迭代深化找到）使搜索速度更快。

在不使用太多额外内存和 CPU 时间的情况下，如何搜索可能的最佳动作？

有人可以解释一下迭代深化 A*吗？我仍然不明白它是如何工作的。 使用深度优先搜索进行迭代深化搜索，如果仍未找到解决方案；增加深度++ 直到找到解决方案。

如果使用Depth进行迭代加深，那么迭代加深 A* 使用什么来限制他们的搜索？

如果您需要解释 IDA* 的工作原理，这里有一张图片，我只是不明白它是如何工作的。

(1,2,4,9)等，是步骤

0+2=2 是f(n)=g(n)+h(n)

我正在编写棋盘游戏。我使用 alpha-beta 修剪生成了一个游戏树，并有 2 个选项：

1. 使用迭代深化来优化 alpha-beta，使其不断生成一层，直到时间结束。
2. 通过反复试验，我知道在时间限制内每个板配置可达到的最大深度，而无需事先检查下层。

哪种方法更好，并且会使搜索达到更深的深度？例如，我知道，一开始我可以生成一棵深度为 X 的树，消耗所有可用的时间......迭代加深可以增加更多深度吗？

让我知道我是否可以更清楚...

我在这里看到了这个问题的一些变化，但我不确定如何将它们应用于我的情况，所以我希望也许有人可以在这里帮助我。

我有一个类似于以下格式的平面 XML 文件：

我希望根据 id 属性分层设置标签，如下所示：

一些 id 值有两位数字（例如，“1.2.3.15.1”），这使得比较它们更具挑战性。

帮助？

更新：搜索第一个解决方案。

对于普通的深度优先搜索很简单，只需使用哈希集

但是，当它变得有限时，我不能简单地这样做

因为那时它不会在之前进行完整的搜索（从某种意义上说，如果有的话，总是能够找到解决方案）maxdepth

我应该如何解决它？它会增加算法的空间复杂度吗？

或者它根本不需要记忆状态。

更新：

例如，决策树如下：

从状态 A 开始，G 是一个目标状态。显然在深度 3 下有一个解决方案。

但是，使用我在深度 4 下的实现，如果搜索的方向恰好是

A(0) -> B(1) -> C(2) -> D(3) -> E(4) -> F(5)超过深度，那么它会回溯到A，但是E被访问，它会忽略检查方向A - E - F - G

深度优先搜索是搜索文件系统的一种可怕方式——实际上，使用 DFS 可能需要很长时间才能找到可能位于非常接近根目录的目录下的文件，因为 DFS 会被另一个深度分散注意力，不相关的目录层次结构。
然而，它的资源需求非常好——它需要保持打开的文件句柄的数量只与层次结构的深度成正比，而不是它的大小。

广度优先搜索是显而易见的解决方案——它非常快。
（上次我测量时，它与我系统上的 DFS 所用的时间大致相同，大约 8 秒。）

然而 BFS 有其自身的问题—— BFS 需要保持打开大量目录句柄，可能数百万。（在我的系统上，大约有 100,000 个句柄，这个数字高得离谱。它很容易更多。）

这会导致几个问题：

• 保持打开这么多句柄不仅会消耗内存（无论如何相对便宜），还会消耗许多其他类型的资源，例如虚拟文件系统（网络、挂载目录等）内的文件句柄，以及可能其他有限的内核-级资源。

• 它还给用户带来了其他实际问题：例如，一直处于打开状态的虚拟目录不再可关闭！这意味着，例如，用户可能无法关闭程序、弹出某些设备或关闭某种外部连接。这种方法可能会出现各种问题。

那么，似乎迭代深化就是解决方案。

问题？在实践中非常缓慢。我的麻烦是大型目录（例如Windows中的WinSxS）会为每个深度级别
重新枚举，即使它们不需要。上次我尝试这个时，迭代加深比我系统上的 DFS 慢了约 15 倍。所以 8 秒的搜索大约需要 120 秒左右，这是不可接受的。

当然，试图跟踪你不应该打开的目录（也许是因为你注意到你不再需要打开它们）通过发现我们在 BFS 中遇到的所有资源问题，首先破坏了使用迭代深化的目的.

所以，这个问题很简单：

如果您正在搜索一个您不熟悉的文件系统，您应该如何着手在速度和可用性之间取得可接受的平衡？有比 BFS 更好的选择吗？

我正在实施迭代深化深度优先搜索，以找到解决8 难题的解决方案。我对自己找到实际的搜索路径不感兴趣，而只是计算程序运行需要多长时间。（我还没有实现定时功能）。

但是，我在尝试实现实际搜索功能时遇到了一些问题（向下滚动查看）。我粘贴了到目前为止所有的代码，所以如果你复制并粘贴它，你也可以运行它。这可能是描述我遇到的问题的最佳方式......我只是不明白为什么我在递归期间会出现无限循环，例如在拼图 2（p2）的测试中，第一次扩展应该产生一个解决方案。我认为这可能与未在其中一行代码前面添加“Return”有关（下面对此进行了评论）。当我添加返回时，我可以通过拼图 2 的测试，但是像拼图 3 这样更复杂的东西失败了，因为现在代码似乎只扩展了最左边的分支......

一直在这几个小时，放弃希望。如果您能指出我的错误，我将非常感谢您对此有另一种看法。谢谢！

我编写了一个迭代深化算法，它可以工作，除非我添加循环检查，算法返回比它应该的更深的解决方案。但是当我不检查周期时，它确实可以正常工作，但需要的时间太长。任何人都可以发现错误吗？

编辑：这是扩展功能

这是其中一个动作，除了细微的变化外，它们都是相同的

谓词

我正在查看 Wikipedia 上的伪代码，并尝试使用它在 java 中编写算法。我的问题在于返回结果的方式有所不同。在维基百科上，返回一个结果，这超出了搜索范围。在我的情况下，每次找到相关节点时，都会将其添加到列表中，并且在处理完树后返回该列表。我将如何检测树的末端以打破并返回列表？

维基百科：

矿：

编辑：更改后：

我有一个搜索算法，它应该解析整个树，找到所有可以匹配搜索查询的结果，并将它们全部作为列表返回。我意识到这并不是算法的重点，但我这样做是为了进行广度优先和深度优先搜索的测试，以通过计时来查看最快的搜索结果。其他两个搜索按预期工作，但是当我输入与 DFID 搜索目标相同的搜索信息时，我得到一个空列表。所以我知道我的数据是正确的，只是算法中有问题，我不知道是什么。我是根据 Wikipedia 上的伪代码编写的。这是我所拥有的：