IDDFS

Interative Deepening Depth-First Search 迭代加深搜索。

与普通的 DFS 的区别在于，IDDFS 限制搜索的距离，达到限制的距离将被剪枝，如果在当前限制的距离下无法达到目标状态，那么逐步扩大搜索的距离。

IDA *

与 IDDFS 类似，不过在每一次开始之前需要判断达到目标状态的距离的下界（严格的下界），如果下界在当前限制距离下是可达到的，才进行搜索，相当于通过一个对下界的预判断而提前剪枝。

步骤如下：

  1. 给出状态 v 到目标状态的距离下界的估算函数 h*(v)
  2. 令 x = 0 （限制的距离）
  3. 对满足 d(v) + h*(v) <= x的状态进行深度优先搜索，判断是否有不超过 x 的解（d(v) 表示从初始状态到 v 的距离）
  4. 如果找到解，则 x 就是最优解，程序结束
  5. 否则，将 x 增加 1 并回到第 3 步

A *

正如深度优先算法可以利用下界优化一样，宽度优先搜索和 Dijkstra 算法也可以利用下界优化。只要将优先队列中的键改成 d(v) + h*(v) 就可以了，其中 d(v) 是初始状态到状态 v 的距离，h*(v) 是到目标状态的距离下界。这种算法称为A*。只不过需要注意的是，与宽度优先搜索和 Dijkstra 算法不同，在选用某些下界进行估算的情况下，优先队列顶端的元素对应的 d(v) 未必已经是初始状态到 v 的最短距离。

如果对于所有的边 (w, v) 都有 cost(u, v) + h*(u) + h*(v) > 0 成立，那么第一次取出某个节点 v 时，对应的 d(v) 就一定是最短距离。不过，由于 A* 是到目标状态的距离的下界，所以第一次从队首取出的距离同样就是最短距离。

需要注意的是，A* 通常无法减少算法的复杂度（即 A* 对最坏的情况无效），只能减少平均复杂度。