问DFID (Dept-第一次迭代深度)与IDA* (迭代-深度A*)

EN

Russel & Norvig的书是关于这些算法的一个极好的参考，我将给larsmans一个虚拟的副词，因为它提出了它；但是我不同意IDA*在任何明显的方式上比A*更难编程。我这样做是为了一个项目，我不得不写一个人工智能来解决一个滑块谜题，这是一个常见的问题，有一个N×N个编号瓷砖的网格，并且使用单个的自由空间滑动瓷砖，直到它们按升序排列。

召回：

F(n) = g(n) + h(n).

TotalCost = PathCost + Heuristic.

g(n) =路径成本，从初始状态到当前状态的距离 h(n) =启发式，从当前状态到结束状态的成本估计。要成为一个可接受的启发式(从而确保A*的最优性)，您无论如何都不能高估成本。*。

请记住，迭代深化A*只是A*，它限制了允许遍历的节点的F值。每个外部迭代都会增加这个FLimit；对于每一个迭代，您都在深化搜索。

这是我的C++代码实现了A*和IDA*来解决上述滑块难题。您可以看到，我使用带有自定义比较器的std::priority_queue来存储按F值排序的队列中的迷口状态。您还将注意到，A*和IDA*之间唯一的区别是添加了一个FLimit检查和一个增加这个FLimit的外部循环。我希望这有助于对这个问题有所了解。

请查看罗素与诺维格，第3章和第4章，并认识到IDA*很难正确编程。您可能希望尝试递归最佳优先搜索(RBFS)，也由R&N或普通的老A*描述。后者可以使用std::priority_queue实现。

IIRC、R&N在第一版中对IDA*进行了描述，然后在第二版中用RBFS替换了IDA*。我还没看过第三版呢。

至于你的第二次编辑，我还没有看过这个游戏，但一个很好的过程，推导启发式是放松的问题。你把游戏规则拿走，直到你得到一个版本，这个版本的启发式很容易表达和实现(而且计算起来也很便宜)。或者，按照自下而上的方法，检查主要规则，看看哪条规则允许使用简单的启发式方法，然后尝试并根据需要添加其他规则。

DFID只是IDA*的一个特例，其中启发式函数是常量0；换句话说，它没有引入启发式的规定。如果问题还不够小，不需要使用启发式方法就可以解决，那么您似乎别无选择，只能使用IDA* (或A*家族的其他成员)。也就是说，IDA*并没有那么难: AIMA的作者提供的实现仅仅是半页Lisp代码；我认为C++实现不应该超过这一页的两倍。