回溯算法专题-工具盒子

回溯算法的两种写法 {#回溯算法的两种写法}

题目描述（面试题）：为了迎接新同学的加入，小飞飞组织了丰富多彩的活动，这一次他随机在区的树篱迷宫中放置了一个奖品，请帮助同学以最快的速度找到奖品吧。树篱迷宫是一个4x4的正方形，用一个二维数组来表示，其中0代表可以走的路，1代表树篱不可行走，8表示奖品。迷宫有一到多个入口，且随机分布。请帮助新人找出到奖品的最短路径并输出。

思路：咋一看这题数据范围小得离谱，只有4*4=16种情况，即使是指数级别的时间复杂度也能接受。求最短路的问题一般有：记忆化搜索、动态规划、BFS、Dijkstra、Floyd等方法，但是这道题要求出最短的路径是什么，涉及到这种路径上所有节点都要进行求解的，考虑用暴力回溯。我们可以枚举每个合法的出发点，从每个合法的出发点进行DFS搜索，搜索过程中可选的下一步为：上下左右&&合法；同时为了避免走回头路导致StackOverFlow要当前轮搜索过的节点进行标记，搜索的同时要进行记录，搜索完了要进行撤回。那么出口只有一个，那就是找到礼品了，退出的时候我们记录当前记录的长度并与之前的比较，当且仅当长度比之前的小才是最短路径。

时间复杂度:O(N^3) 空间复杂度:O(N^2)

写法1：先处理再进行dfs {#写法1：先处理再进行dfs}

先处理完再进行DFS的方式，要求在每个DFS进行之前就进行处理（标记访问+记录数据），每个DFS结束之后要进行对应的撤回（注意是每个DFS方法），这样才能保证遍历该层的下一个选择时是正确的状态。

PS：其实这题还可以进行一些剪枝处理加速：比如从某个边缘出发点到达不是这个出发点的边缘的情况可以进行剪枝加速。

|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | public class t1 { @Test public void test() { int[][] grid = { {0, 1, 1, 1}, {0, 0, 0, 1}, {1, 0, 8, 1}, {1, 0, 1, 1}}; List<int[]> res = winMaze(grid); for (int[] p : res) { System.out.println(Arrays.toString(p)); } } // res存储当前遍历到的最短路径，cur存储当前正在遍历的路径 List<int[]> res = new ArrayList<>(), cur = new ArrayList<>(); int min = 0x3f3f3f3f; // 当前找到的最短路径长度，初始化为INF int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 方向向量 boolean[][] vis = new boolean[4][4]; // 标记是否被访问 int[][] grid; public List<int[]> winMaze(int[][] _grid) { grid = _grid; // 枚举每个合法起点 for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { // 仅仅边缘且可以走的格子才进行dfs if ((i == 0 || i == 3 || j == 0 ||j == 3) && grid[i][j] == 0) { vis[i][j] = true; // 进入dfs之前就进行标记和处理 cur.add(new int[]{i, j}); dfs(i, j); vis[i][j] = false; // dfs完成之后再撤回 cur.remove(cur.size() - 1); } } } return res; } private void dfs(int i, int j) { // base case -> 找到礼品了 if (grid[i][j] == 8) { // 当且仅当找到更短的路径才进行保存 if (cur.size() < min) { res = new ArrayList<>(cur); min = cur.size(); // 更新当前最短长度 } return; // 结束 } // 遍历下一步能到的格子 for (int[] dir : dirs) { int newI = i + dir[0], newJ = j + dir[1]; // 没有越界&&没有访问过&&可行的 if (newI >= 0 && newI < 4 && newJ >= 0 && newJ < 4 && !vis[newI][newJ] && grid[newI][newJ] != 1) { vis[newI][newJ] = true; // 进入dfs之前就进行标记和处理 cur.add(new int[]{newI, newJ}); dfs(newI, newJ); vis[newI][newJ] = false; // 撤回 cur.remove(cur.size() - 1); } } } } |

输出：

|---------------|------------------------------| | 1 2 3 | [3, 1] [2, 1] [2, 2] |

2:写法二：在dfs内部进行处理 {#2-写法二：在dfs内部进行处理}

这种在dfs内部处理的方式，在DFS一开始就要进行处理（标记访问+记录数据），DFS结束之前要进行撤回（注意出口可能不止一处），保证DFS函数执行完后当前的递归树深度不变。

|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | public class t1 { @Test public void test() { int[][] grid = { {0, 1, 1, 1}, {0, 0, 0, 1}, {1, 0, 8, 1}, {1, 0, 1, 1}}; List<int[]> res = winMaze(grid); for (int[] p : res) { System.out.println(Arrays.toString(p)); } } // res存储当前遍历到的最短路径，cur存储当前正在遍历的路径 List<int[]> res = new ArrayList<>(), cur = new ArrayList<>(); int min = 0x3f3f3f3f; // 当前找到的最短路径长度，初始化为INF int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 方向向量 boolean[][] vis = new boolean[4][4]; // 标记是否被访问 int[][] grid; public List<int[]> winMaze(int[][] _grid) { grid = _grid; // 枚举每个合法起点 for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { // 仅仅边缘且可以走的格子才进行dfs if ((i == 0 || i == 3 || j == 0 || j == 3) && grid[i][j] == 0) dfs(i, j); } } return res; } private void dfs(int i, int j) { // dfs最开始进行标记+记录 vis[i][j] = true; cur.add(new int[]{i, j}); // base case -> 找到礼品了 if (grid[i][j] == 8) { // 当且仅当找到更短的路径才进行保存 if (cur.size() < min) { res = new ArrayList<>(cur); min = cur.size(); // 更新当前最短长度 } vis[i][j] = false; // dfs结束之前要撤回 cur.remove(cur.size() - 1); return; // 结束 } // 遍历下一步能到的格子 for (int[] dir : dirs) { int newI = i + dir[0], newJ = j + dir[1]; // 没有越界&&没有访问过&&可行的 if (newI >= 0 && newI < 4 && newJ >= 0 && newJ < 4 && !vis[newI][newJ] && grid[newI][newJ] != 1) { dfs(newI, newJ); } } vis[i][j] = false; // dfs结束之前要撤回 cur.remove(cur.size() - 1); } } |

输出：

|---------------|------------------------------| | 1 2 3 | [3, 1] [2, 1] [2, 2] |

回溯例题：LC679.24点游戏 {#回溯例题：LC679-24点游戏}

回溯法暴力遍历:(参考官方题解)

括号可以直接忽略,因为暴力遍历已经包含所有运算次序

4*3*4*3*2*4*2*1*4=9216种可能性

1.这个游戏的本质就是将其中两个数进行相乘的结果重新加入并进行新一轮原来的24点计算

2.排除几种特殊情况:

2.1 除0计算:这种情况直接跳过

2.2 乘法与加法的运算可以进行剪枝

2.3 误差考虑:当误差<1e-6时,认为就是0

3.若最终都没有返回true说明找不到最后返回false

时间复杂度与空间复杂度均为:O(1)

|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | class Solution { // 计算误差 private static final double ERROR = 1e-6; // 目标值 private static final double TARGET = 24; // 加减乘除 private static final int PLUS = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3; /* 判断是否能凑成24 */ public boolean judgePoint24(int[] cards) { List<Double> list = new ArrayList<>(); for(int num : cards) { list.add((double)num); } return dfs(list); } /* dfs主函数:返回list中是否能计算出24 */ private boolean dfs(List<Double> list) { // 递归出口1:空列表 if(list.size() == 0) { return false; } // 递归出口2:运算结果为24 if(list.size() == 1 && Math.abs(list.get(0) - TARGET) < ERROR) { return true; } // 先抽出两个要进行运算的数 int size = list.size(); for(int i = 0; i < size; i++) { for(int j = 0; j < size; j++) { // 注意是索引不同的两个数才能进行运算 if(i != j) { // 再创建一个列表存放剩余的元素 List<Double> remain = new ArrayList<>(); for(int k = 0; k < size; k++) { if(k != i && k != j) { remain.add(list.get(k)); } } // 在对选中的两个数list[i]与list[j]进行计算并加入remain列表 for(int k = 0; k < 4; k++) { // 加法与除法进行剪枝(只保留i>j部分一半) if(k < 2 && i < j) { continue; } if(k == PLUS) { remain.add(list.get(i) + list.get(j)); }else if(k == MULTIPLY) { remain.add(list.get(i) * list.get(j)); }else if(k == SUBTRACT) { remain.add(list.get(i) - list.get(j)); }else if(k == DIVIDE) { // 排除除0的情形 if(list.get(j) < ERROR) { continue; }else { remain.add(list.get(i) / list.get(j)); } } // 将加入运算结果的remain列表进行递归运算,若得到24直接返回true if(dfs(remain)) { return true; } // 撤回操作刚刚的添加操作继续下一种符号的运算 remain.remove(remain.size() - 1); } } } } // 若最后都找不到正确的选项,说明就是没有了 return false; } } |

一点思考：

其实回溯本质上就是递归+回退从而找到所有的路径(组合的可能)，最关键的就是要找到子问题

问题：n个数进行组合运算能否得出24这个结果

开始是4个数进行运算[1,2,3,4]

选其中两个数尝试，例如选了selected=[1,3]，剩余的是remain=[2,4]

那么将selected中的两个数进行 [+, -, *, /] 4种运算得到的结果[4, -2, 3 , 0.3333...]分别再次放入remain中

判断这3个数进行运算的结果是否能得到24？

子问题由此产生：由4个数字的组合变成了3个数字的组合

若3个数字的组合能算出24可以马上推出4个数字的组合能就算出24！

此时我们重复调用原本的函数就能解决这个3个数能否组成24的问题了→这就是递归！

在递归过程有不合格的案例进行回退并往另一条路径走，这就是回溯了！

例如我通过1+3=4，而[2,4,4]通过递归发现不能使得结果为24，因此这种情况就要舍弃了