摘要:本文通过一个简单的迷宫的例子,简单介绍了深度优先搜索(DFS)和广度优先搜索(BFS)的实现、优点和局限,由此引出迭代深化深度优先搜索(IDDFS)的算法,介绍了它的原理、实现和简单应用,并提出了我的一点优化的想法。

  1. 什么是IDDFS

    维基百科是这么阐释迭代深化深度优先搜索(IDDFS):
    > In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal like breadth-first search, but uses much less memory; at each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

    在计算机科学中,迭代深化搜索(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的兄弟,广度优先搜索。
    和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);
        while (!ans)
        {
            lim_dep < dep_lim)
        {
            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. 一个大胆的想法

    每次迭代,深度不断加深,但却要重新DFS先前遍历过的所有点。由此,我想到了像BFS一样,维护一个队列,记录每次DFS因深度限制搜索不下去的点,不清除访问记录。如果没搜到,可以直接在原队列上进行更深入地搜索,从而越过每次更新限制深度时,需要重复搜索已搜过的节点。
    这样的算法是否能可行?优点和缺点在哪里?欢迎大家留言讨论。

  8. 尾声

    本文首次发布于2019年7月27日,欢迎转载(其实应该没人会看我的文章),转载请注明出处。

最后修改日期: 2019年8月27日

作者

0 0 投票数
文章评分
订阅评论
提醒
0 评论
内联反馈
查看所有评论