搜索-IDDFS from BFS、DFS

IDDFS 迭代深化深度优先搜索

摘要：

本文通过一个简单的迷宫的例子，简单介绍了深度优先搜索（DFS）和广度优先搜索（BFS）的实现、优点和局限，由此引出迭代深化深度优先搜索IDDFS的算法，介绍了它的原理、实现和简单应用。

1.什么是IDDFS

在计算机科学中，迭代深化搜索（iterative deepening search）或者更确切地说迭代深化深度优先搜索（iterative deepening depth-first search (IDS or IDDFS)） 是一个状态空间（状态图）搜索策略。在这个搜索策略中，一个具有深度限制的深度优先搜索算法会不断重复地运行，并且同时放宽对于搜索深度的限制，直到找到目标状态。IDDFS 与广度优先算法是等价的，但对内存的使用会少很多；在每一步迭代中，它会按深度优先算法中的顺序，遍历搜索树中的节点，但第一次访问节点的累积顺序实际上是广度优先的。
不知各位是否看懂了上面的一长串话？反正我是一脸懵逼的…… 看不懂没关系，让我们从一个问题的另外一个角度“小题大做”一番吧。

2.一个小问题

给定一个迷宫，知道路径，是否能够找到某种算法，找到迷宫中的宝藏（或者出口之类的东西）？

3.深度优先搜索（DFS）的解法

对于这样一个判断寻找图中结点的问题，我们自然可以使用DFS轻松解出。事实上，对于很多类似的问题，DFS是一个优秀的算法：不断搜索其子节点，直到找到为止。确实，对于这个问题，这是一个非常优秀的算法，在这里，我给出对于一般问题DFS的伪代码：

Point *dfs(Point &point){
    if (point是需要的元素){
        return &point;
    }
    else if (point含有子节点){
        for (每一个未遍历的子节点){
            return dfs(该节点);
        }
    }
    return NULL;
}

4.和深度优先搜索（DFS）广度优先搜索（BFS）

诚然，DFS的简洁高效，作为一个非常实用的算法被人们广泛使用。对于这个问题，它当然是非常优秀的算法。但它在一些极端情况，可能会给我们造成一些时间的浪费。显然，我们可以构造一种极端的情况：

如图所示，黑色的是根节点（可以理解为迷宫的起点），绿色的是所要搜索的元素（可以理解为迷宫的终点）。如果采用先序遍历的方式（先搜索根结点，递归地先序遍历左子树，递归地遍历右子树），那么，终点将在最后遍历。换句话说，我们可以在迷宫中构造一个极长的“死胡同”，让DFS搜索算法深陷其中，极大地降低搜索的速度。
总而言之，如果在搜索过程中，有一个很长的“陷阱”，而DFS很可能掉入这个“陷阱”中，不断递归，浪费时间，甚至有可能栈溢出。
也就是说，我们希望能在一个较少步数内，找到结果。

我们再考虑DFS的兄弟，广度优先搜索。
和DFS一样，BFS是非常优秀和常用的搜索算法。其原理可以简单地理解为先搜索起点，然后搜索所有距离起点有且只有一步的点，然后搜索距离起点有且只有两步，依次类推，知道搜索到为之。这样，我们就可以求出起点到所有点的最短距离，在最短距离内搜索到想要的节点自然也不在话下。
很显然，BFS能找到到终点的最短路径，但是，与我们期望找到终点的目标似乎有些偏离。**为了找到目标，我们用一种十分暴力的方法，找到到终点的最小值，以此达到目的。**很显然，这种算法太浪费资源了。我们没有必要找到到达终点的最小值，只是期望能以一个较少的步数找到终点。最重要的是，在BFS的过程中，我们需要维护一个队列，使用大量的空间记录我们所要搜索的子节点。

总而言之，在某些极端情况下，DFS可能会在搜索的过程中陷入“死胡同”，BFS会造成极大空间的浪费。在运行时间充裕的情况下，我们能否考虑优化我们的搜索算法，以追求时间与空间的平衡？

5.迭代深化深度优先搜索（IDDFS）

上两节中，我们分别讨论了对于迷宫找出口这种问题的解法和其局限性。并得出了对于迷宫问题，我们可以采用DFS轻松解出。但是对于一些特殊情况（例如迷宫中极长的死胡同），DFS与BFS可能会造成时间或空间的浪费。

我们考虑优化这种情况：
BFS的优点在于，层层推进，不易陷入死胡同；而DFS的优点在于，空间占用小，搜索直接。
我们考虑取长补短，将两者算法的优点结合起来，就得到了迭代深化深度优先搜索（IDDFS）的算法的核心思想——对DFS搜索的深度加以限制，即我们定义中所指出的：

在这个搜索策略中，一个具有深度限制的深度优先搜索算法会不断重复地运行，并且同时放宽对于搜索深度的限制，直到找到目标状态。

我们可以估计一个深度，例如2，让DFS搜索前2步所能到达的节点，如果搜不到，也不继续搜索，直接返回，然后搜索其它的节点。如果找不到，就放款限制，让深度变为4，即搜索前4步内所能到达的节点，若没找到，就让深度变为8、16、32。依次类推，直到找到终点。这样我们就可以给出IDDFS的大致框架了：

Point *iddfs(){
    int lim_dep = 2;    // 数不一定为2，请根据实际情况估值
    Point *ans = dfs(root, lim_dep, 0);
       if(lim_dep < dep_now){
        return NULL;
    }
    else if (pnow是需要的元素){
        /* 省略一波操作，例如在全局变量中更新终点信息 */
        return &pnow;
    }
    else if (pnow含有子节点){
        for (每一个未遍历的子节点){
            Point *ans = dfs(该节点, lim_dep, dep_now + 1);
            if(ans){
                return ans;
            }
        }
    }
    return NULL;
}

6.IDDFS的要点

迭代深化深度优先搜索，适合于对空间要求比较高，而对时间要求不那么敏感的问题，在使用IDDFS时，需要注意时间效率与空间效率之间的平衡。

IDDFS中输入的数据必须保证问题会有解，否则可能会陷入无限递归的境地。当然。如果实在避免不了，我又一个大胆的想法（没有仔细验证过可行性），不妨试着增加一个全局变量，用来记录信息。如果没有因为深度超限返回的，就说明全部遍历完成。

7.结尾

恭喜你看到这里了，不知道你现在有没有什么疑问，对我而言呢是比较困惑的，可能是参加的比赛比较少的缘故，我发现大多数的题都对时间复杂度要求比较严格，而空间复杂度往往被我忽视。不知道你有没有遇到必须要IDDFS才能解的题，欢迎(恳求)留言。