回溯算法

发表于 | 分类于

定义

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

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

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 的。