回溯算法

定义

回溯算法实际上一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

N 对括号问题

给出 N 代表生成括号的对数,请写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 N = 3,生成结果为:

1
2
3
4
5
6
7
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

这是一个很经典的回溯法问题,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backTracking("", result, n, n);
return result;
}

public static void backTracking(String s, List<String> result, int left, int right) {
if (left == 0 && right == 0) {
result.add(s);
return;
}
if (right > left) {
backTracking(s + ")", result, left, right - 1);
}
if (left > 0) {
backTracking(s + "(", result, left - 1, right);
}
}

对于回溯法来说,必须齐备的三要素:

  1. 选择。在这个例子中,解就是一个合法的括号组合形式,而选择无非是放入左括号,还是放入右括号。

  2. 条件。在这个例子中,选择是放入左括号,还是放入右括号,是有条件约束的,不是随便放的。而这个约束就是括号的数量。只有剩下的右括号比左括号多,才能放右括号。只有左括号数量大于0才能放入左括号。这里if的顺序会影响输出的顺序,但是不影响最终解;

  3. 结束。这里的结束条件很显然就是,左右括号都放完了。

下面列出了每次递归调用时,一些主要的参数(从左至右分别为当前结果,左括号剩余数,右括号剩余数,绿色为最终结果):

N 皇后问题

N 皇后问题是指在 N * N 的棋盘上放置 N 个皇后,使这 N 个皇后无法吃掉对方(也就是说两两不在一行,不在一列,也不在对角线上)。经典的是 8 皇后问题,这里我们为了简单,以 4 皇后为例。

  1. 首先利用回溯算法,先给第一个皇后安排位置,如下图所示,安排在(1,1)
  2. 然后给第二个皇后安排位置,可知(2,1),(2,2)都会产生冲突,因此可以安排在(2,3)
  3. 然后安排第三个皇后,在第三行没有合适的位置,因此回溯到第二个皇后
  4. 重新安排第二个皇后的位置,安排到(2,4),然后安排第三个皇后到(3,2),安排第四个皇后有冲突,因此要回溯到第三个皇后
  5. 第三个皇后也就仅此一个位置,无处可改,故继续向上回溯到第二个皇后,也没有位置可更改,因此回溯到第一个皇后
  6. 更改第一个皇后的位置,继续上面的做法,直至找到所有皇后的位置,如下图所示。

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

public class NQueensII {
int[] x;//当前解
int N;//皇后个数
int sum = 0;//当前已找到的可行方案数
public int totalNQueens(int n) {
N = n;
x = new int[N+1];
backTrace(1);
return sum;
}

/**
* 判断该位置能不能放,需要判断对角线和同列上是否可放
*/
private boolean place(int col){
for(int i = 1; i < col; i++){
if(Math.abs(col - i)==Math.abs(x[col]-x[i])||x[col]==x[i]){
return false;
}
}
return true;
}

private void backTrace(int t) {
if(t>N){
sum++;
}else {
//第t行,遍历所有的节点
for(int j = 1; j <= N; j++) {
x[t] = j ;
//如果第j个节点可以放下皇后
if(place(t)){
//接着放下一个
backTrace(t+1);
}
}
}

}

public static void main(String[] args) {
NQueensII n = new NQueensII();
System.out.println(n.totalNQueens(4));
}
}

总结

回溯法有通用解法的美称,是一个很重要的算法,对于很多问题,如迷宫等都有很好的效果。

回溯算法的精髓就是在不满足条件后进行“回溯”,尝试其他路径,直至找出所有解。

回溯算法虽然也是 Brute-Force (暴力破解),但是它可以避免去搜索很多的不可能的情况,因此算法是优于 Brute-Force 的。