侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 174 篇文章
  • 累计创建 45 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

DFS与回溯算法阅读笔记

996worker
2021-07-07 / 0 评论 / 0 点赞 / 181 阅读 / 5,795 字
温馨提示:
本文最后更新于 2021-07-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. Copyright

总结拷贝自Fucking-algorithm
fucking-algorithm

2. 回溯算法是啥

回溯算法其实就是我们常说的 DFS 算法,本质上就是一种暴力穷举算法。

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

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

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

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

框架:

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

核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」

3. 案例

3.1 全排列问题

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

那么我们当时是怎么穷举全排列的呢?比方说给三个数 [1,2,3],你肯定不会无规律地乱穷举,一般是这样:

先固定第一位为 1,然后第二位可以是 2,那么第三位只能是 3;然后可以把第二位变成 3,第三位就只能是 2 了;然后就只能变化第一位,变成 2,然后再穷举后两位……

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

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

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

你现在就在做决策,可以选择 1 那条树枝,也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢?因为 2 这个树枝在你身后,这个选择你之前做过了,而全排列是不允许重复使用数字的。

现在可以解答开头的几个名词:

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

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

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

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

于是,可以把「路径」和「选择」列表作为决策树上每个节点的属性,比如下图列出了几个蓝色节点的属性

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

那么,如何遍历一棵树?这个应该不难吧。回忆一下之前「学习数据结构的框架思维」写过,各种搜索问题其实都是树的遍历问题,而多叉树的遍历框架就是这样:

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


前序遍历的代码在进入某一个节点之前的那个时间点执行,后序遍历代码在离开某个节点之后的那个时间点执行。

回想我们刚才说的,「路径」和「选择」是每个节点的属性,函数在树上游走要正确维护节点的属性,那么就要在这两个特殊时间点搞点动作:

总结成核心框架:

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

我们这里稍微做了些变通,没有显式记录「选择列表」,而是通过 nums 和 track 推导出当前的选择列表:

但是必须说明的是,不管怎么优化,都符合回溯框架,而且时间复杂度都不可能低于 O(N!),因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点,不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高。(对链表使用 contains 方法就需要 O(N) 的时间复杂度。)

3.2 N皇后问题

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

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

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

套用框架:

vector<vector<string>> res;

/* 输入棋盘边长 n,返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
    // '.' 表示空,'Q' 表示皇后,初始化空棋盘。
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
    return res;
}

// 路径:board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表:第 row 行的所有列都是放置皇后的选择
// 结束条件:row 超过 board 的最后一行
void backtrack(vector<string>& board, int row) {
    // 框架结束条件,结束一条遍历路线
    if (row == board.size()) {
        // 保存一组可能的结果
        res.push_back();
        return;
    }

    // 每一行有多少元素供使用呢
    int n = board[row].size();
    // 扫描这一个决策节点(行)
    for (int col = 0; com < n; col++) {
        // 跳过不可行的方案
        if(!isValid(board, row, col)) {
            continue;
        }
        // 作出选泽
        board[row][col] = 'Q';
        // 进入下一个决策节点
        backtrack(board, row+1);
        // 撤销选择,为了下个新的决策节点正常遍历出所有结果。
        board[row][col] = '.';
    }
}

至于规则函数isValid(board, row, col),需要自己考虑自己写:

/* 是否可以在 board[row][col] 放置皇后? */
bool isValid(vector<string>& board, int row, int col) {
    int n = board.size();
    // 检查列是否有皇后互相冲突
    // i < n处的 n 可以写为row
    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;

    // 检查一半是因为我们下面的和上面的互不干涉。
}

真正的leetcode解题代码:

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new LinkedList<>();

        // 初始化棋盘
        ArrayList<StringBuilder> board = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            StringBuilder str = new StringBuilder();
            for(int j = 0; j < n; j++) {
                str.append('.');
            }

            board.add(str);
        }

        // 从第一行回溯开始,求解
        backtrack(board, res, 0);

        return res;
    }

    private void backtrack(ArrayList<StringBuilder> board, List<List<String>> res, int row) {
        // 当前一条完整回溯树枝返回条件
        if (row == board.size()) {
            ArrayList<String> track1 = new ArrayList<>();
            //StringBuilder类转化为String类
            for (StringBuilder stringBuilder : board) {
                track1.add(stringBuilder.toString());
            }
            res.add(track1);
            return;
        }

        // 每行多少个元素?
        int n = board.get(row).length();
        for (int col = 0; col < n; col++) {
            // 跳过不可行:规则不允许的位置
            if(!isValid(board, row, col)) {
                continue;
            }

            // 选择一个落棋点
            board.get(row).setCharAt(col, 'Q');
            // 进入下一个回溯节点
            backtrack(board, res, row + 1);
            // 撤销之前的骡子点,为下一个节点元素作准备
            board.get(row).setCharAt(col, '.');
        }
    }

    private boolean isValid(ArrayList<StringBuilder> board, int row, int col) {
        // 维度
        int n = board.size();

        // 检查我头上的有没有Q呀。左右不用检查,因为一个row就一个
        for (int i = 0; i < row ; i++) {
            if (board.get(i).charAt(col) == 'Q') {
                return false;
            }
        }

        // 检查我右上方有没有Q
        for (int i = row - 1, j = col + 1; i>=0 && j <n; i--,j++) {
            if (board.get(i).charAt(j) == 'Q')
                return false;
        }

        // 检查我左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if(board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        return true;
    }
}

当 N = 8 时,就是八皇后问题,高斯穷尽一生都没有数清楚八皇后问题到底有几种可能的放置方法,但是我们的算法只需要一秒就可以算出来所有可能的结果。

不过真的不怪高斯。这个问题的复杂度确实非常高,看看我们的决策树,虽然有 isValid 函数剪枝,但是最坏时间复杂度仍然是 O(N^(N+1)),而且无法优化。如果 N = 10 的时候,计算就已经很耗时了。

所以我们可以只让它返回一个可行结果返回,然后停止就好。

// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
    // 触发结束条件, 直接返回
    if (row == board.size()) {
        res.push_back(board);
        return true;
    }
    ...
    for (int col = 0; col < n; col++) {
        ...
        board[row][col] = 'Q';

        if (backtrack(board, row + 1))
            return true;
        
        board[row][col] = '.';
    }

    return false;
}

4. Conclusion

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

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

写 backtrack 函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集。

其实想想看,回溯算法和动态规划是不是有点像呢?我们在动态规划系列文章中多次强调,动态规划的三个需要明确的点就是「状态」「选择」和「base case」,是不是就对应着走过的「路径」,当前的「选择列表」和「结束条件」?

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

0

评论区