c++ - DFID（Dept-First 迭代深度）与 IDA*（迭代深度 A*）

Question

我想知道这两种算法的优缺点是什么。我想写AddEmUp C++ 解决，但我不确定我应该使用哪种（IDA 或 DFID）算法。

我找到的最好的文章是这篇文章，但它似乎太旧了 - 93 年。有更新的吗？

我认为 IDA* 会更好，但是.. ? 还有其他想法吗？

任何想法和信息都会有所帮助。

谢谢 ！（：

编辑：一些关于 IDA* 的好文章和算法的好解释？

EDIT2：或者那个游戏的一些好的启发式函数？我不知道怎么想一些：/

Answer 1

Russel & Norvig 的书是关于这些算法的极好参考，我会给 larsmans 一个虚拟的高五来推荐它；但是我不同意 IDA* 在任何方面都比 A* 更难编程。我已经为一个项目完成了它，我必须编写一个 AI 来解决一个滑块拼图 - 熟悉的问题是有一个 N x N 网格编号的瓷砖，并使用单个可用空间来滑动瓷砖直到它们是按升序排列。

记起：

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

TotalCost = PathCost + Heuristic.

g(n) = 路径成本，从初始状态到当前状态的距离

h(n) = 启发式，从当前状态到最终状态的成本估计。要成为一个可接受的启发式算法（从而确保 A* 的最优性），您在任何情况下都不能高估成本。有关高估/低估启发式方法对 A* 的影响的更多信息，请参阅此问题。

请记住，迭代深化 A* 只是A*，对允许遍历的节点的 F 值有限制。这FLimit随着每次外部迭代而增加；每次迭代你都在深化搜索。

这是我实现 A* 和 IDA* 以解决上述滑块难题的 C++ 代码。您可以看到我使用 astd::priority_queue和自定义比较器将拼图状态存储在按其 F 值优先排序的队列中。您还将注意到 A* 和 IDA* 之间的唯一区别是添加了一个FLimit检查和一个递增 this 的外循环FLimit。我希望这有助于阐明这个主题。

Answer 2

查看Russell & Norvig的第 3 章和第 4 章，并意识到 IDA* 很难正确编程。您可能想尝试递归最佳优先搜索 (RBFS)，也由 R&N 或普通旧 A* 描述。后者可以使用std::priority_queue.

IIRC、R&N 在第一版中描述了 IDA*，然后在第二版中将其替换为 RBFS。我还没有看到第三版。

至于您的第二次编辑，我没有研究过游戏，但推导启发式的一个好过程是轻松问题。你拿走游戏规则，直到你得到一个启发式易于表达和实现（并且计算成本低）的版本。或者，按照自下而上的方法，您检查主要规则以查看哪个允许简单的启发式，然后尝试并根据需要添加其他规则。

Answer 3

DFID is just a special case of IDA* where the heuristic function is the constant 0; in other words, it has no provision for introducing heuristics. If the problem is not small enough that it can be solved without using heuristics, it seems you have no choice but to use IDA* (or some other member of the A* family). That said, IDA* is really not that hard: the implementation provided by the authors of AIMA is only about half a page of Lisp code; I imagine a C++ implementation shouldn't take more than twice that.