记录生活中的点点滴滴

0%

回溯算法

写一下回溯算法,顺便用回溯算法解决这两道题:46. 全排列51. N 皇后

回溯算法概念

其实回溯算法其实就是我们常说的 DFS 算法,本质上就是一种暴力穷举算法。

解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:

1、路径:也就是已经做出的选择。

2、选择列表:也就是你当前可以做的选择。

3、结束条件:也就是到达决策树底层,无法再做选择的条件。

代码方面,下面是回溯算法的框架:

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

这样确实难以理解,下面我们先看看全排列这道题,我们可以一边看这道题一边结合上面的一些概念进行消化,效果更好!

全排列

我们在高中的时候就做过排列组合的数学题,我们也知道 n 个不重复的数,全排列共有 n! 个。

PS:为了简单清晰起见,我们这次讨论的全排列问题不包含重复的数字

那么我们当时是怎么穷举全排列的呢?比方说给三个数 [1,2,3],你肯定不会无规律地乱穷举,一般是这样:

先固定第一位为 1,然后第二位可以是 2,那么第三位只能是 3;然后可以把第二位变成 3,第三位就只能是 2 了;然后就只能变化第一位,变成 2,然后再穷举后两位……

其实这就是回溯算法,我们全都会的。

我们就称这棵树为决策树,因为我们求解问题就是围绕它进行的。

我们再贴出来上面回溯算法的框架:

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

接下来我们想一想我们是怎样解决这个问题的呢?

其实就是先遍历,也就是选择列表,对于这道题来说选择列表就是123,然后看是否满足条件,条件是什么?其实就是看123这三个数我们用完了没有。接着如果没有用完,那么就遍历123,首先要先判断,如果123已经有的数字前面已经使用,那么就要跳过这次,进行下一种情况。如果没有使用,那就把这次遍历到的数字添加,然后递归这个函数。递归完成之后,我们还需要把这次加入的数字删除掉,让它进行下一次递归。

其实,就是这样,主要的逻辑就是for循环中,记录结果情况,就是需要先进行判断满足结束条件那一段。

OK,这就是回溯,我们在代码的编写中,要往前看,看看是否符合情况。

好的,接下来,我们直接上代码了:

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
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
/**
采用回溯法,基本框架如下:
def backtrack:
判断是否满足条件,不满足就退出

for 选择 in 选择列表:
做选择
backtrack
撤销选择
**/
LinkedList<Integer> list = new LinkedList<Integer>();
backtrack(list,nums);
return res;
}
public void backtrack(LinkedList<Integer> list,int[] nums){
//判断条件,如果满了,说明已经有一种情况了
if(list.size()==nums.length){
res.add(new LinkedList(list));
return;
}
//迭代做选择
for(int i=0;i<nums.length;i++){
//排除不合法的选择
if(list.contains(nums[i]))
continue;
list.add(nums[i]);
backtrack(list,nums);
list.removeLast();
}
}

八皇后

上面的题目,如果我们能够将递归的逻辑弄明白之后,下面八皇后这道题大体上也是这样的逻辑。

我把题目截下来吧:

这道题,我们想自己想一想。

先定一行(或者一列)中皇后的位置,然后进行下一行皇后位置的确定,需要我们去判断是否符合情况。

就是这样一直循环,就可以了。

也是回溯的算法,我们还需思考一些小细节。

首先,结束条件是啥?就是遍历的行数(从0开始)等于n的时候。

做出选择其实就是那个位置的值为 ‘Q’。

撤销选择其实就是那个位置的值为 ‘.’。

对于主要的回溯函数:

1
2
3
4
5
6
// 路径:board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表:第 row 行的所有列都是放置皇后的选择
// 结束条件:row 超过 board 的最后一行
public void backtrack(List<char[]> list,int row){

}

那么判断是否合法的函数的书写:

先判断列是否有皇后冲突。接着是对角线,分左上边和右上边。

这里直接写出来把:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//判断是否合法
public boolean isValid(List<char[]> list,int row,int col){
int n = list.size();
for(int i = 0; i < n; i++) { // 检查列是否有皇后互相冲突
if(list.get(i)[col] == 'Q'){
return false;
}
}

// 检查右上方是否有皇后互相冲突
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++){
if(list.get(i)[j] == 'Q'){
return false;
}
}

// 检查左上方是否有皇后互相冲突
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
if(list.get(i)[j] == 'Q'){
return false;
}
}
return true;
}

好的,有了这些我们去完成函数的编写,直接贴出来了:

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
List<List<String>> res = new LinkedList<List<String>>();
public List<List<String>> solveNQueens(int n) {
List<char[]> list = new LinkedList<>();
//填充为.
for(int i=0;i<n;i++){
char[] chars = new char[n];
Arrays.fill(chars,'.');
list.add(chars);
}
backtrack(list,0);
return res;
}
// 路径:board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表:第 row 行的所有列都是放置皇后的选择
// 结束条件:row 超过 board 的最后一行
public void backtrack(List<char[]> list,int row){
// 触发结束条件
if(row==list.size()){
res.add(transform(list));
return;
}
int n = list.size();
for(int i=0;i<n;i++){//遍历所有选择
if(!isValid(list,row,i)) continue;
list.get(row)[i] = 'Q';//做出选择
backtrack(list,row+1);//进行下一个决策
list.get(row)[i] = '.';//撤销选择
}
}
//转换函数
public List<String> transform(List<char[]> list){
List<String> ret = new LinkedList<>();
for(char[] chars:list){
ret.add(new String(chars));
}
return ret;
}

OK,回溯算法入门篇就这样吧,明天继续肝回溯,光这些肯定还是不够的,冲!