回溯算法-通用算法

回溯算法框架

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

  1. 路径:也就是已经做出的选择。
  2. 选择列表:也就是你当前可以做的选择。
  3. 结束条件:也就是到达决策树底层,无法再做选择的条件。

如果你不理解这三个词语的解释,没关系,我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思,现在你先留着印象。
回溯算法的代码框架:

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

其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」
什么叫做选择和撤销选择呢,这个框架的底层原理是什么呢?下面我们就通过「全排列」这个问题来解开之前的疑惑,详细探究一下其中的奥妙!

全排列

为了简单清晰起见,我们这次讨论的全排列问题不包含重复的数字。
那么我们怎么穷举全排列的呢?比方说给三个数 [1,2,3],你肯定不会无规律地乱穷举,一般是这样:

先固定第一位为 1,然后第二位可以是 2,那么第三位只能是 3;然后可以把第二位变成 3,第三位就只能是 2 了;然后就只能变化第一位,变成 2,然后再穷举后两位……
其实这就是回溯算法,其回溯树如下:

只要从根遍历这棵树,记录路径上的数字,其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。

为啥说这是决策树呢,因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上:

你现在就在做决策,可以选择 1 那条树枝,也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢?因为 2 这个树枝在你身后,这个选择你之前做过了,而全排列是不允许重复使用数字的。
现在可以解答开头的几个名词:[2] 就是「路径」,记录你已经做过的选择;[1,3] 就是「选择列表」,表示你当前可以做出的选择;「结束条件」就是遍历到树的底层,在这里就是选择列表为空的时候。

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

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

现在,你是否理解了回溯算法的这段核心框架?

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

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

show code

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 i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

回溯算法不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。

N皇后

这个问题很经典了,简单解释一下:给你一个 N×N 的棋盘,让你放置 N 个皇后,使得它们不能互相攻击。

注意:皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

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

show code

/**
 * 八皇后问题:8x8 的棋盘,希望往里放 8 个棋子(皇后),每个棋子所在的行、列、对角线都不能有另一个棋子
 *
 * @author Mr.Huang at 2020-05-31 15:29
 **/
public class QueenSettle {
    private static Integer N = 8;

    /**
     * @param selectedColumns 已选解集合,下标表示行,值表示queen存储在哪一列
     * @param row             可选的空间解,第 n 行可选
     */
    public static void queenSettle(int[] selectedColumns, int row) {
        // 终止条件
        if (row > N - 1) {
            // 说明前 N 行都已经都选完皇后了,
            printQueens(selectedColumns);
            return;
        }

        for (int i = 0; i < N; i++) {

            // 剔除不合法的格子
            if (!isValid(row, i, selectedColumns)) {
                continue;
            }

            // 选择子节点(当前行)其中一个解
            selectedColumns[row] = i;

            // 选完之后再进入下个阶段的(下一行)遍历
            queenSettle(selectedColumns, row + 1);

            // 回溯,换一个解继续 dfs,回溯时要把回溯节点的解移除
            selectedColumns[row] = -1;

        }
    }

    /**
     * 判断相应的格子放置皇后是否OK
     *
     * @param row
     * @param column
     * @param selectedColumns
     * @return
     */
    private static boolean isValid(int row, int column, int[] selectedColumns) {
        //判断row行column列放置是否合适
        int leftup = column - 1, rightup = column + 1;
        // 逐行往上考察每一行

        for (int i = row - 1; i >= 0; --i) {
            // 第i行的column列有棋子吗?
            if (selectedColumns[i] == column) {
                return false;
            }
            // 考察左上对角线:第i行leftup列有棋子吗?
            if (leftup >= 0) {
                if (selectedColumns[i] == leftup) {
                    return false;
                }
            }
            // 考察右上对角线:第i行rightup列有棋子吗?
            if (rightup < 8) {
                if (selectedColumns[i] == rightup) {
                    return false;
                }
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] selectedColumn = new int[N];
        // 从第 0 行开始 DFS
        queenSettle(selectedColumn, 0);
    }

    private static void printQueens(int[] result) { // 打印出一个二维矩阵
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; ++column) {
                if (result[row] == column) {
                    System.out.print("Q ");
                }
                else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

总结

回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,算法框架如下:

def backtrack(...):
    for 选择 in 选择列表:
        做选择
        backtrack(...)
        撤销选择

写 backtrack 函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集
其实想想看,回溯算法和动态规划是不是有点像呢?

某种程度上说,动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质,可以用 dp table 或者备忘录优化,将递归树大幅剪枝,这就变成了动态规划。而今天的两个问题,都没有重叠子问题,也就是回溯算法问题了,复杂度非常高是不可避免的。

0 0 投票数
Article Rating
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x