IDA*算法

IDA* 的全称为：Iterative deepening A，即基于迭代加深的 A* 算法。迭代加深只有在状态呈指数级增长时才有较好的效果，而A*就是为了防止状态呈指数级增长的。
IDA* 实质：对迭代加深加了一个启发式的剪枝（全局最优性剪枝）。在迭代加深代码框架基础上，对每个状态点引入一个估价值(该点距离目标点所需的最小步数)，如果某状态点的深度加上该点的估价值>迭代加深限制的最大层数则直接返回不再向下层继续搜索。同 A* 算法一样，都需要保证 估价值 <= 真实值。该算法的难点仍在于如何确定估价函数。
IDA* 和 A* 的区別：
A* = BFS +启发函数
IDA* = IDDFS +启发函数
IDA* 由于是深搜，空间消耗相对 A* 更少。