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

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

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

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

谢谢！ (:

编辑： 有没有关于 IDA* 的好文章，以及对该算法的良好解释？

EDIT2： 或者有没有适用于该游戏的好的启发式函数？ 我不知道该如何思考一些 :/

回答：

《人工智能：一种现代方法》(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* 只是 对允许遍历的节点的 F 值有限制的 A*。 这个 FLimit 随着每次外部迭代而增加；每次迭代你都在加深搜索。

这是我的 C++ 代码，实现了 A* 和 IDA* 来解决前面提到的滑动方块拼图。 你可以看到我使用带有自定义 Comparator 的 std::priority_queue 来存储 Puzzle 状态，并按照它们的 F 值进行优先级排序。 你还会注意到 A* 和 IDA* 之间的唯一区别是添加了 FLimit 检查和一个递增 FLimit 的外部循环。 我希望这有助于阐明这个问题。