为什么ida $ ^ * $速度比$ ^ * $更快？为什么IDA $ ^ * $访问更多节点，而不是$ ^ * $？

Question

我使用iDA $ ^ * $ 用于最佳地解决8谜题和我的朋友使用 $ ^ * $也是如此（与曼哈顿距离启发式相同）。

我计算了20个例子和我朋友算法的算法的平均运行时间和数量。我的算法的时间平均比我朋友的算法要快得多，但我访问的平均节点数量比我朋友的更多数量。

我知道ida $ ^ * $ 多次访问每个节点，但为什么它比$ ^ * $ ？

Answer 1

自从您已经实现了IDA $ ^ * $ 您当然明白为什么它比 $ ^ * $ ，即，它从开始状态开始，在每次迭代中具有新的深度第一遍历。首先，请注意，IDA $ ^ * $ 访问的节点的总数，同时必须大于 $ ^ * $ 并不大得多。原因是每个深度的节点数根据带因子 $ b $ ，分支因子的几何系列进行。结果，深度 $ d $ ， $ b ^ d $ 。大于在上一个迭代处扩展的所有节点的总和，即 $ b ^ d> \ sum_ {i= 0} ^ {d-1} b ^ i $ 。从这种差异，事实证明IDA $ ^ * $ 需要 $ \ frac {b} {b-1} $ 渐近最佳的附加扩展为大 $ b $ 是1.结论，对于访问所有节点的任何算法在深度 $ d $ 比访问前面深度的所有节点都要困难得多。

如果您想要更多地进入此问题，我强烈建议您阅读原文：Korf，Richard E.深度首先迭代深化：最佳可允许树搜索。人工智能（27），97-109，1985.参见特别定理4.2：

深度首先迭代加深在渐近的最佳状态 Brute-Force树在时间，空间和长度方面搜索 解决方案。

当然，它提供最佳解决方案，以便它是可允许的，因此，渐近最佳。它只实践深度第一遍历，因此，它在空间方面是渐近最佳的（需要只有良好的实现 $ o（d）$ ）。

作为时间，我已经概述了主要的理论原因，但让我知道突出三个主要原因，为什么它在实践中如此迅速：

首先，出于几乎所有目的，任何算法的总运行时间都是展开节点所花费的时间（其他操作相当简单和原子）所在的主导。在扩展ida $ ^ * $ 中的节点时确实是非常快的，因为：

1.1。 IDA $ ^ * $ 递归地实现，以便所有所需的都需要作为参数给出的状态并一次生成一个孩子（对于您的特定情况只需将空白交换与相邻的瓷砖，这只是一个语句！）。但是，对于 $ ^ * $ 扩展操作需要：首先，从队列中弹出状态，然后生成其所有子项（即，移动空白瓦片可能的方向）。

1.2。虽然前面的操作产生了一些差异，但非常重要的是，一个非常重要的一个是 $ ^ * $ 需要打开排序节点。即使您使用1次桶（将使用 $ O（1）$ ），也请注意，IDA $ ^ * $ 根本不需要对节点进行排序，因此虽然 $ ^ * $ 在节点的数量中需要线性，但是IDA $ ^ * $ 完全没有。

1. 第三，最好的第一搜索算法的贡献之一（例如 $ ^ * $ ）是它们避免重新扩展节点使用封闭列表（尽管它的名称通常是作为一个集合实现的!!）。 IDA $ ^ * $ 没有重复检测机制，因此， $ ^ * $ 执行额外的操作，该操作不受IDA $ ^ * $ 。如果您想在IDA $ ^ * $ 中了解更多关于重复检测，请参阅：Reinefeld，a .; Marsland，T.增强了迭代深化的搜索。图案分析和机器智能的IEEE交易（16）7,701-710,1994。

最后一点真正相关。在滑动瓦片拼图的情况下，没有许多换位确实，最短的循环由12个移动组成，因此重新扩展的数量并不大。将所有这些放在一起，IDA $ ^ * $ 是一个杀手机器，适用于所有尺寸的滑块拼图。

然而，尽管存在所有优点，但它可能对那些具有大量换置的应用可能具有实际兴趣。有各种各样的尝试克服这种困难

有限的成功，参见例如：

Dow，P. Alex;Korf，Richard E.在深度首先使用应用程序到Treewth的避免重复避免。国际人工智能联席会议，480-485,2009。

希望这有帮助，