回溯算法的两种写法
题目描述（面试题）：为了迎接新同学的加入，小飞飞组织了丰富多彩的活动，这一次他随机在区的树篱迷宫中放置了一个奖品，请帮助同学以最快的速度找到奖品吧。树篱迷宫是一个4x4的正方形，用一个二维数组来表示，其中0代表可以走的路，1代表树篱不可行走，8表示奖品。迷宫有一到多个入口，且随机分布。请帮助新人找出到奖品的最短路径并输出。
思路：咋一看这题数据范围小得离谱，只有4*4=16种情况，即使是指数级别的时间复杂度也能接受。求最短路的问题一般有：记忆化搜索、动态规划、BFS、Dijkstra、Floyd等方法，但是这道题要求出最短的路径是什么，涉及到这种路径上所有节点都要进行求解的，考虑用暴力回溯。我们可以枚举每个合法的出发点，从每个合法的出发点进行DFS搜索，搜索过程中可选的下一步为：上下左右&&合法；同时为了避免走回头路导致StackOverFlow要当前轮搜索过的节点进行标记，搜索的同时要进行记录，搜索完了要进行撤回。那么出口只有一个，那就是找到礼品了，退出的时候我们记录当前记录的长度并与之前的比较，当且仅当长度比之前的小才是最短路径。
时间复杂度:O(N^3) 空间复杂度:O(N^2)
写法1：先处理再进行dfs
先处理完再进行DFS的方式，要求在每个DFS进行之前就进行处理（标记访问+记录数据），每个DFS结束之后要进行对应的撤回（注意是每个DFS方法），这样才能保证遍历该层的下一个选择时是正确的状态。
PS：其实这题还可以进行一些剪枝处理加速：比如从某个边缘出发点到达不是这个出发点的边缘的情况可以进行剪枝加速。
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));
}
}
List<int[]> res = new ArrayList<>(), cur = new ArrayList<>();
int min = 0x3f3f3f3f;
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++) {
if ((i == 0 || i == 3 || j == 0 ||j == 3) && grid[i][j] == 0) {
vis[i][j] = true;
cur.add(new int[]{i, j});
dfs(i, j);
vis[i][j] = false;
cur.remove(cur.size() - 1);
}
}
}
return res;
}
private void dfs(int i, int j) {
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;
cur.add(new int[]{newI, newJ});
dfs(newI, newJ);
vis[newI][newJ] = false;
cur.remove(cur.size() - 1);
}
}
}
}
|
输出：
2:写法二：在dfs内部进行处理
这种在dfs内部处理的方式，在DFS一开始就要进行处理（标记访问+记录数据），DFS结束之前要进行撤回（注意出口可能不止一处），保证DFS函数执行完后当前的递归树深度不变。
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));
}
}
List<int[]> res = new ArrayList<>(), cur = new ArrayList<>();
int min = 0x3f3f3f3f;
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++) {
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) {
vis[i][j] = true;
cur.add(new int[]{i, j});
if (grid[i][j] == 8) {
if (cur.size() < min) {
res = new ArrayList<>(cur);
min = cur.size();
}
vis[i][j] = false;
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;
cur.remove(cur.size() - 1);
}
}
|
输出：
回溯法暴力遍历:(参考官方题解)
括号可以直接忽略,因为暴力遍历已经包含所有运算次序
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)
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;
public boolean judgePoint24(int[] cards) {
List<Double> list = new ArrayList<>();
for(int num : cards) {
list.add((double)num);
}
return dfs(list);
}
private boolean dfs(List<Double> list) {
if(list.size() == 0) {
return false;
}
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));
}
}
for(int k = 0; k < 4; k++) {
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) {
if(list.get(j) < ERROR) {
continue;
}else {
remain.add(list.get(i) / list.get(j));
}
}
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，因此这种情况就要舍弃了
怎样进行舍弃?
很简单，将[2,4,4]最后加入元素删掉就相当于返回上一层，可以继续进行下一个运算符的计算，再放进去[2,4]里面进行递归…
若某个dfs([x,x,x])返回true就说明这条路径是可行的
