算法思想：迭代加深

废话不多说，我们从一个小例子开始。
假定一个游戏，有一个2*4的棋盘，棋盘上有1到8的数字。每一步可以选择4种操作中的一种来改变棋盘。问从初始状态最终操作成一个给定的状态最少要几步。

游戏的具体操作并不是我们讨论的主题，先略去。

最朴素的想法

搜索。我们用搜索树表示搜索的过程。一个结点就是棋盘的一个状态，结点的孩子就是经过操作后棋盘新的状态。对于棋盘的一个状态，每步可以做4种操作，也就是父节点有4个孩子。

深搜
对于棋盘的一个状态，由于每步可以做4种操作，我们递归的尝试每一种。就是基本的深搜。

深搜的缺点很明显。如果答案状态所在的结点深度不大，那么搜到这个结点之前，对非常深的状态进行的搜索都是徒劳的。何况每一步都有4种选择，深度加深了时间呈指数级上升。

广搜
对上述的问题，广搜可以很好的解决。每步的四个操作同时加入队列，第一个到达目标状态的结点就是步数最少的。

但广搜的问题也很明显。如果目标状态的深度稍微深一些，用于保存状态的队列所需的空间就会指数级增长。以本题为例，如果到达目标状态最少要10步，在第10层队列就需要保存4^10个，约1,000,000个结点。深度再深一些，分支再多一些，空间需求就会大的无法接受。

迭代加深(iterative deepening)

深搜广搜都有自己的缺点。迭代加深(以下简称ID)则结合两者的优点，用深搜模拟广搜。
ID不过是由以下两个思想启发产生。

为了避免过大的空间需求，必须使用深搜。

为了避免搜索无用且过深的搜索树，必须按广搜的模式控制搜索深度。

控制深度的深搜，就是ID。
深搜之前，我们设定一个限定的深度，要求深搜不得超过这个深度。
每一次深搜，我们检查当前所处的深度。如果达到限定的深度，立刻返回。
一次完整的深搜完成，如果没有找到答案，增加限定的深度，继续ID。

很明显，无论深搜存在的搜索过深问题，还是广搜存在的空间问题，都能解决。

现在，ID唯一令人怀疑的问题是：由于没有用空间保存信息，每次迭代都会把上一个深度的搜索树再次搜索一遍。这是否会让时间复杂度上升？
我们进行一次证明。
设D(x)是深度为x时搜索树内的结点数(0<=x)。节点的分支数，也就是每一步的可操作数，为k。可以看出，D(x)=……+。等比数列，得D(x)=。
如果答案的深度是h，那么如果只搜索深度为h的搜索树，也就是最好情况下的广搜，搜索的结点数是D(h)=。
ID搜索的结点数则是：D(0)+D(1)+D(2)+……+D(h)，等于

+++……++
=+
=+
=

我们认为这一项不影响复杂度，所以舍去。得原式等于：

=

也就是说，ID搜索的结点数是广搜的倍。
情况最坏时k等于2（k不等于1，只有一个操作就不需要搜索了），ID的花的时间仅仅是最好的时间的2倍，属于常数范围。况且和广搜庞大的空间代价相比这点额外的时间简直是小巫见大巫。更何况当k更大，更趋近于1，ID几乎没有浪费太多时间。
证毕。

伪代码

最伟大的算法，代码永远是最简洁的。ID也不例外。

IterativeDeepening()
{
    /*max depth limited in DFS*/
    global maxdepth=1;
    while (answer hadn't been found)
    {
        dfs(0);
        maxdepth++; 
    }
    return answer;
}

dfs(int depth)
{
    /*reach depth limit*/
    if (depth==maxdepth)    return;
    check whether answer is found;
    /*do dfs*/
    do dfs(depth+1);
}

最后

ID思想之巧妙，一言难尽。实际应用很可能用其他方法剪枝，但ID的思想依然足够伟大。这里仅仅记录下一点心得，证明自己也有幸与这样的伟大思想碰撞。
2018.12.20