回溯算法 backtrack

围巾🧣 2020年08月02日 545次浏览

解决的问题：

解决一个回溯问题，实际上就是一个决 策树的遍历过程。回溯算法的一 个特点，不像动态规划存在重叠⼦问题可以优化，回溯算法就是纯暴力穷 举，复杂度一般都很高。

要素：

  1. 路径：也就是已经做出的选择。

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

  3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

模板：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件: 
        result.add(路径) 
        return
    
	for 选择 in 选择列表: 
        做选择 
        backtrack(路径, 选择列表) 
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用 之后「撤销选择」，特别简单。

全排列例子：

问题：

我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的 数，全排列共有 n! 个。 PS：为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。

思路：

我们通常的思路是：先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以 把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2， 然后再穷举后两位……

回溯算法，我们高中无师自通就会用，或者有的同学直接画出如 下这棵回溯树：

image.png

只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不 妨把这棵树称为回溯算法的「决策树」。为啥说这是决策树呢，因为我们在每个节点上其实都在做决策。比如说你站在 下图的红色节点上：

image.png

[2] 就是「路径」，记录你已经做过的选 择； [1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。

如果明白了这几个名词，可以把**「路径」和「选择」列表作为决策树上每个 节点的属性**，比如下图列出了几个节点的属性：

image.png

我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要 正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。

再进一步，如何遍历一棵树？这个应该不难吧。各种搜索问题其实都是树的遍历问题，而多叉树的遍 历框架就是这样：

void traverse(TreeNode root) { 
	for (TreeNode child : root.childern) 
        // 前序遍历需要的操作 	
        traverse(child); 
    	// 后序遍历需要的操作
}

而所谓的前序遍历和后序遍历，他们只是两个很有用的时间点，我给你画张 图你就明白了：

image.png

前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在 离开某个节点之后的那个时间点执行。
回想我们刚才说的，「路径」和「选择」是每个节点的属性，函数在树上游 走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：

image.png

故可以看看回溯算法的这段核心框架：

for 选择 in 选择列表:
	# 做选择
    将该选择从选择列表移除 
    路径.add(选择) 
    backtrack(路径, 选择列表) 
    # 撤销选择 
    路径.remove(选择) 
    将该选择再加入选择列表

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到 每个节点的选择列表和路径。

代码：

	List<List<Integer>> res = new LinkedList<>();

    /* 主方法，输入一组不重复的数字，返回它们的全排列 */
    List<List<Integer>> permute(int[] nums) {
        // 记录路径
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素
    // 结束条件：nums 中的元素全都在 track 中出现
    void backtrack(int[] nums, LinkedList<Integer> track) {
        // 触发结束的条件
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }

        for (int num : nums) {
            // 不合法的
            if (track.contains(num)) {
                continue;
            }
            // 做选择
            track.add(num);
            // 下一层决策树
            backtrack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }

N皇后例子：

问题：

给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

思路：

这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一 行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

代码：

vector<vector<string>> res;

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

    return true;
}

// 路径：board 中⼩于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string> &board, int row) {
    // 触发结束条件
    if (row == board.size()) {
        res.push_back(board);
        return;
    }

    int n = board[row].size();
    for (int col = 0; col < n; ++col) {
        //排除不合法选择
        if (!isValid(board, row, col)) {
            continue;
        }
        // 做选择
        board[row][col] = 'Q';
        // 进入下一层决策
        backtrack(board, row + 1);
        // 撤销选择
        board[row][col] = '.';
    }
}

/* 输入棋盘边数 n，返回所有合法的放置 */
vector<vector<string>> solveNQueues(int n) {
    // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
    return res;
}
上一篇： Spring Cloud 开发环境