算法第六期——DFS初入门(深度优先搜索)(Python)

���录 

一、蛮力的技术：搜索

1.1、【暴力法】

1.2、蛮力的基本方法——扫描

二、搜索的基本方法

2.1、BFS:一群老鼠走迷宫

2.2、DFS：一只老鼠走迷宫 

2.3、BFS和DFS的异同 

三、DFS详解

3.1、DFS访问示例

3.2、 DFS基础: 递归和记忆化搜索

3.2.1 递归——斐波那契数列

3.2.2改进递归:记忆化

3.3、DFS的常见操作

四、DFS的代码框架

五、例题：搜索和输出所有路径

5.1、样例分析 

5.2、DFS搜索所有路径

5.3、代码展示 

六、总结

---

一、蛮力的技术：搜索

1. 搜索：“暴力法”算法思想的具体实现
2. 搜索：“通用”的方法。一个问题，如果比较难，那么先尝试一下搜索，或许能启发出更好的算法。
3. 技巧：竞赛时遇到不会的难题，用搜索提交一下，有一部分判题数据很弱，得分了! 

1.1、【暴力法】

暴力法(Brute force，又译为蛮力法)：把所有可能性都列举出来，一 一 验证。简单直接，依靠于计算机强大的计算能力和存储能力。

• 蛮力法也是一种重要的算法设计技术:

  (1)、理论上，蛮力法可以解决可计算领域的各种问题

  (2)、蛮力法经常用来解决一些较小规模的问题

  (3)、对于一些重要的问题蛮力法可以产生一些合理的算法，具备一些实用价值，而且不受问题规模的限制。

  (4)、蛮力法可以作为某类问题时间性能的底限（基准），来衡量同样问题的更高效算法

  1.2、暴力的基本方法——扫描

  关键——依次处理所有元素

  基本的扫描技术——遍历

  1. 集合的遍历（也可以用前面提到过的用二进制模拟计算）
  2. 线性表的遍历（数组、链表、队列、栈）
  3. 树的遍历
  4. 图的遍历（树是特殊的图）

  树和图的遍历比较复杂，一般用DFS和BFS来搜索 

  二、搜索的基本方法

  【BFS]】Breadth-First Search，宽度优先搜索，或称为广度优先搜索

  【DFS】Depth-First Search，深度优先搜索

  2.1、BFS:一群老鼠走迷宫 

  • 老鼠无限多;
  • 在每个路口，都派出部分老鼠探索所有没走过的路；
  • 走某条路的老鼠，如果碰壁无法前行，就停下；
  • 如果到达的路口已经有别的老鼠探索过了，也停下；
  • 所有的道路都会走到，而且不会重复 。

     特点：全面扩散，逐层递进 

    用途：解决起始点到终点的最短路径(（步数）的问题 

    2.2、DFS：一只老鼠走迷宫 

    • 只有一只老鼠;
    • 在每个路口，都选择先走右边(当然，选择先走左边也可以)，能走多远就走多远；
    • 碰壁无法再继续往前走，回退一步，这一次走左边,然后继续往下走；
    • 能走遍所有的路，而且不会重复 (回退不算重复) 。

      特点：一路到底，逐层回退 

      用途：解决输出起始点到终点的所有路径的问题 

      2.3、BFS和DFS的异同 

      相同点：搜索整个空间 ；

      不同点：

      DFS：一路往最深的地方走；BFS：一层一层往外扩散

      DFS空间占用少，BFS时间效率高

      三、DFS详解

      3.1、DFS访问示例

      • 设先访问左节点，后访问右节点；
      • 模拟老鼠走迷宫
      •  访问顺序:{ E B A D C G F I H }，如下图：

        补充：如果是BFS的访问就简单多了，访问顺序：E→BG→ADFI→CH（一层一层的访问）

        这个访问方式是我们之前讲过的先序遍历 ，我们回顾一下那个小人：沿着外围跑一圈（直到跑回根节点）

        3.2、 DFS基础: 递归和记忆化搜索

        形式上，递归函数是“自己调用自己”，是一个不断“重复”的过程。

        递归有两个过程:递归前进、递归返回(回溯) 

        ①把大问题逐步缩小，直到变成最小的同类问题的过程，而最后的小问题的解是已知的，一般是给定的初始条件。

        ②到达最小问题后，再“回溯”，把小问题的解逐个带回给更大的问题，最终最大问题也得到了解决。 

                在递归的过程中，由于大问题和小问题的解决方法完全一样，那么大问题的代码和小问题的代码可以写成一样。一个递归函数，直接调用自己，实现了程序的复用。

        3.2.1 递归——斐波那契数列

        • 递推式: f(n) = f(n-1) + f(n-2)

          打印第20个项: 

          fib=[0]*25fib[1]=1fib[2]=1for i in range(3,21):    fib[i]=fib[i-1]+fib[i-2]print(fib[20])        # 6765

          改用递归来实现

          def fib(n):    global cnt       # 全局变量    cnt += 1         # 统计执行了多少次递归    if n==1 or n==2: # #到达终止条件，即最小问题        return 1    return fib(n-1)+fib(n-2) #递归调用自己2次，复杂度0(2的n次方)cnt =0print(fib(20))       # 6765print(cnt)           # 递归了cnt=13529次

          函数fib(20)计算斐波那契数
          递归过程:

          • 递归前进：fib(20) = fb(19) + fb(18)
          • 递归前进：fib(19) = fib(18) + fib(17)
          • 递归前进：fib(18) = fib(17) + fib(16)
          • …………………………………………
          • 递归前进: fib(3) = fib(2) + fib(1)

            到达终止条件: fib(2)= 1，fib(1) = 1 

            • 递归返回 (回溯)：fib(3) = fib(2) + fib(1) =1+1=2
            • 递归返回 (回溯)：fib(4) = fib(3) + fib(2) =2+1=3
            • ……………………………………………………
            • 递归返回 (回溯) ：fib(20)=fib(19)+fib(18)=4181+2584=6765

              ---

              提问： 递推和递归两种代码，结果一样，计算量差别巨大？（递推代码:一个for循环，计算20次。递归代码: 计算第20个斐波那契数，共计算cnt = 13529次）

              代码低效的原因:

              return fib (n-1) + fib (n-2)  递归调用了自己2次，倍增

              计算fib(n)时，共执行了O()次递归

              不过，很多递归函数只调用自己一次,不会额外增加计算量。

              3.2.2改进递归:记忆化

              • 递归的过程中做了重复工作，例如fb(3)计算了2次，其实只算1次就够了。
              • 为避免递归时重复计算，可以在子问题得到解决时，就保存结果，再次需要这个结果时，直接返回保存的结果就行了，不继续递归下去这种存储已经解决的子问题结果的技术称为“记忆化”(Memoization) 
              • 记忆化是递归的常用优化技术。动态规划也常常用递归写代码，记忆化也是动态规划的关键技术。

                import syssys.setrecursionlimit(30000)   #设置递归深度def fib(n) :    global cnt    cnt += 1    if n==1 or n==2:        data[n]=1        return data[n]    if data[n] != 0:            # 已经保存过，直接用        return data[n]    data[n] = fib(n-1)+fib(n-2) # 没有保存的，计算完后保存到data    return data[n]data=[0]*3005                   # 存储结果cnt =0print(fib(3000))   # 约等于4*10的626次方print(cnt)         # 递归次数，cnt=5997

                 递归的关键问题：递归深度不能太大。Python默认递归深度1000，如果递归深度太大，提示“maximum recursion depth exceeded in comparison”。    可以用sys.setrecursionlimit( )来扩展递归深度，因为常常有深度大于1000的递归题目

                3.3、DFS的常见操作

                DFS的代码比BFS更简短。

                DFS的主要操作：

                时间戳

                1. DFS序
                2. 树深度
                3. 子树节点数
                4. 中序输出
                5. 先序输出
                6. 后序输出

                后面三个在之前二叉树部分已经讲过啦！！！ 

                注：这部分在后面文章会详细讲解！

                四、DFS的代码框架（重点！！！）

                DFS的框架，请在大量编码的基础上，再回头体会这个框架的作用。

                ans                         #答案，用全局变量表示def dfs(层数,其他参数):    if 出局判断:             #到达最底层，或者满足条件退出（递归结束条件）        更新答案             #答案一般用全局变量表示        return             #返回到上一层    剪枝                    #在进一步DFS之前剪枝    # DFS主程序    for(枚举下一层可能的情况):      # 对每一个情况继续DFS            if used[i] == 0:          # 如果状态i没有用过，就可以进入下一层            used[i] =1            #  标记状态i,表示已经用过，在更底层不能再使用            dfs(层数+1,其他参数)   # 下一层            used[i] = 0           # 恢复状态，从底层状态进行回溯时，不影响上一层对这个状态的使用    return                        # 返回到上一层

                DFS：保护现场、恢复现场（记忆化）:

                第11行的used[i] = 1，称为“保存现场”，或“占有现场”

                第13行的used[i] = 0，称为“恢复现场”，或“释放现场”

                 上面框架可以简写为：

                def dfs():    if ():            # 搜索结束条件        ()            # 记录一些结果        return    if():             # 剪枝部分        return    for next in ():        ()            # 遍历下一层的路径        dfs(next)     # 递归下一层        ()            # 回溯恢复现场

                DFS函数的要素：

                • 终止条件
                • 剪枝(不一定每道题都有)：可行性剪枝、重复性剪枝、最优性剪枝
                • 递归搜索下一层
                • 保存现场和恢复现场 

                  五、例题：搜索和输出所有路径

                  【题目描述】给出一张图，输出从起点到终点的所有路径。

                  【输入描述】第一行是整数n，m，分别是行数和列数。后面n行，每行m个符号。'@’是起点，’*’是终点，’·’能走，’#’是墙壁不能走。在每一步，都按左-上-右-下的顺序搜索。在样例中，左上角坐标(0,0)，起点坐标(1,1)，终点坐标(0,2)。122->12->022: 11->21->22->12->13->03->023: 11->21->22->23->13->03->024: 11->21->22->23->13->12->025:11->12->026: 11->12->22->23->13->03->027:11->12->13->03->02

                  注：这道题需要输出所有路径，但一般比赛题目只要求输出字典序最小的路径。 

                  5.1、样例分析 

                  【第一条路经】

                  • 从起点(1,1)出发，查询它的“左-上-右-下”哪个方向能走，发现“左-上”不能走，可以走“右”。
                  • 第一步走到右边的(2,1)。然后从(2,1)继续走，它可以向上走到(2,0)，但是后面就走不通了，退回来改走下面的(2,2)。
                  • 逐步深入走到终点，最后得到一条从起点(1,1)到终点(0,2)的路径“11->21->22->12->02”。 
                    • 在这次DFS深入过程中，这条路径上曾经路过的点被“保存现场”，不允许再次经过。

                      例如上图，当从（2,1）走到（2,2）后，（2,1）被“保护现场”，所有不能再退回（2,1）。

                      • 到达终点后，从终点退回，回溯寻找下一个路径。退回后“恢复现场”。

                        例如下图，到达终点后，才可从终点退到（1,2） ，终点（2,0）被“恢复现场”。

                        【第二条路经】

                        搜到一条路径后，从终点(0,2)退回到(1,2)，继续走到(1,3)、(0,3)、(0,2)。 

                         

                         退回到（1,2）后，往上,往右都被“保护现场”，只能往下走到（1,3） ，再往左到（0,3），往左走不通，往上到终点。

                         【第三条路经】

                        • 从终点(0,2)一路退回到(2,2)后，才找到新路径。
                        • 在退回的过程中，原来被“保存现场的”(0,3)、(1,3)、(0,2)，重新被“恢复现场”，允许被经过。
                        • 例如(1,3)，在第二条路径中曾用过，这次再搜新路径时，在第三条路径中重新经过了它。
                        • 如果不“恢复现场”，这个点就不能在新路径中重新用了。

                          【第四条路径】 

                          5.2、DFS搜索所有路径

                                   “保存现场”的作用：禁止重复使用。当搜索一条从起点到终点的路径时，这条路径上经过的点，不能重复经过，否则就兜圈子了，所以路径上的点需要“保存现场”，禁止再经过它。没有经过的点，或者碰壁后退回的点，都不能“保存现场”，这些点可能后面会进入这条路径。

                                  “恢复现场”的作用：当重新搜新的路径时，方法是从终点(或碰壁的点) 沿着旧路径逐步退回，每退回一个点，就对这个点“恢复现场”，允许新路径重新经过这个点。

                          5.3、代码展示 

                          • 路径有很多条，需要记录每条路径然后打印，这个代码使用了“输出最短路径的简单方法”:每到一个点，就在这个点上记录从起点到这个点的路径。
                          •  p[ ][ ]记录路径，p[ i ][ j ]用字符串记录了从起点到点(i,j)的完整路径。
                          • 第14行把新的点(nx,ny)加入到这个路径。这种方法浪费空间，适用于小图。

                            def dfs(x, y):    global num    for i in range(0, 4):    # 每次搜索有四个方向可以选择        dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]             # 四个方向左、上、右、下        nx, ny = x + dir[i][0], y + dir[i][1]                # 新坐标        if nx = hx or ny  wy:          # 判断出局：不在地图内            continue                                         # 换个方向，继续找下一个路径        if mp[nx][ny]== '*':                                 # 到达终点一次            num += 1            print("%d:%s->%d%d" % (num, p[x][y], nx, ny))    # 打印路径:起点到上一个点的路径->终点            continue                                         # 换个方向，继续找下一个路径        if mp[nx][ny]== ".":                                 # 可以走的路            mp[nx][ny]="#"                                   # 保存现场(用#表示)。这个点在这次更深的dfs中不能再用            p[nx][ny] = p[x][y] + '->' + str(nx) + str(ny)   # 记录路径：起点到上一个点的路径——>下一个点            dfs(nx, ny)            mp[nx][ny] = '.'                                 # 恢复现场。回溯之后，这个点可以再次用num = 0                     # 统计路径个数wy, hx = map(int, input().split())  #Wy行，Hx列。a = [""] * 10                       # 用来保存迷宫for i in range(wy):                 #  读迷宫,每次读一行    a[i] = list(input())mp = [[' '] * 10 for i in range(10)]  #二维矩阵mp[][]表示迷宫# 把a存到mp中（x,y颠倒，因为第一维坐标是y，第二维坐标是x）；找到起点和终点for x in range(hx):    for y in range(wy):        mp[x][y] = a[y][x]        if mp[x][y] == '@': sx = x; sy = y  #  起点        if mp[x][y] == "*": tx = x; ty = y  #  终点print("from %d%d to %d%d" % (sx, sy, tx, ty))p = [[''] * 10 for i in range(10)]          # 记录从起点到点path[i][i]的路径p[sx][sy] = str(sx) + str(sy)               # 把起点存进路劲dfs(sx, sy)                                 # 从起点开始搜索并输出所有的路径

                            六、总结

                                    搜所有的路径，应该用DFS;如果只搜最短路径，应该用BFS。在一张图上，从起点到终点的所有路径数量是一个天文数字，读者可以用上面的代码试试一个8x8的图，看看路径总数是多少。但是搜最短的路径就比较简单，并不需要把所有路径搜出来之后再比较得到最短路。用BFS可以极快地搜到最短路。DFS适合用来处理暴力搜所有情况的题目。 

                            本文参考罗勇军老师的蓝桥云课