BackTrack or DFS?

发表于 | 阅读次数:

今天在Leetcode练习算法的时候，不禁思考一个问题，DFS和回溯算法，有什么区别呢？

先来回顾一下我们所熟知的DFS，拿FloodFill问题举例的话，先手写一个伪代码看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//int map[N][N]里面0表示海，1表示岛屿，要求一个map里面连通岛屿的个数
//bool mark[N][N]表示该位置是否被访问过
//int go[][2]表示上下左右四个方向位置转移
int counter;
void DFS(int x,int y){
    for(i in 四个方向){
        int newX=x+go[i][0];int newY=y+go[i][1];
        if(x越界 或者 y越界) continue;
        if(该点不是1) continue;
        if(该点已经被访问过) continue;
        mark[newX][newY]=true; //标记访问
        DFS(newX,newY);
    }
}
main(){
    ...
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
         	if(该点是1 并且 该点未被访问){
                counter++;DFS(i,j);
            }
        }
}

可见，传统DFS一般不会有“解空间”或者复杂解空间结构之类的说法。在之前的《算法》学习中，我一直把二者平等看待，但发现二者还是应该区别看待。DFS是一个劲的往某一个方向搜索，而回溯算法建立在DFS基础之上的，但不同的是在搜过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。状态管理是回溯的核心，回溯算法应用很多，今天就来手写三个典型的数学问题的回溯。首先，我们来看一下回溯算法的基本模板

1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表或者选择的出发点):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

求N个元素的子集，从数学的角度，该子集的个数是2^n个，如果要输出这些子集呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums){
    vector<int> track;
    backTrack(nums,0,track); //0表示深度,track即路径
    return res;
}
void backTrack(vector<int>& nums,int start, vector<int>& track){
    res.push_back(track); //这里不用判断是否满足结束条件,每一处都是结束点
    for(int i=start;i<nums.size();i++)
    {
        //做选择
        track.push_back(nums[i]);
        backTrack(nums,i+1,track);
        //撤销选择
        track.pop_back();
    }
}

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>>res;
vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n <= 0) return res;
    vector<int> track;
    backtrack(n, k, 1, track);
    return res;
}
void backtrack(int n, int k, int start, vector<int>& track) {
    // 到达树的底部
    if (k == track.size()) {
        res.push_back(track);
        return;
    }
    // 注意 i 从 start 开始递增
    for (int i = start; i <= n; i++) {
        // 做选择
        track.push_back(i);
        backtrack(n, k, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

输入一个不包含重复数字的数组 nums，返回这些数字的全部排列。

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
List<List<Integer>> res = new LinkedList<>();
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。大部分回溯算法问题了，无非就是 start 或者 contains 剪枝，也没啥别的技巧了。