signed

QiShunwang

“诚信为本、客户至上”

《算法》系列—大白话聊分治、回溯,手撕八皇后

2021/1/28 16:52:51   来源:

1.分治

分治就是分而治之,即把一个问题分解成很多个子问题,且这些问题与原问题结构相似,然后递归解决子问题,最后合并子问题的结果,得到原来问题的结果。

分治解题三个步骤:

分解:将问题分解成与原问题结构相似的子问题

解决:递归求解各个子问题,当子问题足够小,直接返回结果(问题分解到足够小,分解终止条件)

合并:将子问题的结果合并,得到原问题的结果

分治算法也是一种递归,之前有写到过递归的模板,这里也贴一下分治算法的模板。

接下来看个问题,深入了解一下分治算法,并套用一下模板。

Pow(x,n)

首先按照分治解题的三个步骤分析一下这个问题:

分解:x的n次幂可以分解为子问题:x^n/2 ……

解决:问题还没有分解最小时,就进行递归,当问题分解到足够小时,如n=0时,结果为1;n=1时,结果为x;n=-1时,结果为 1/x。

合并:将得到的结果合并

当n%2==0时,x^n = (x^n/2)*(x^n/2)

当n%2==1时,x^n = x* (x^n/2)*(x^n/2)

下面来看一下代码:

public double myPow(double x, int n) {
    //当结果足够小时,直接返回结果
    if (n == 0) { return 1; }
    if (n == 1) { return x; }
    if (n == -1) { return 1 / x; }
    //解决子问题,递归调用
    double half = myPow(x, n / 2);
    //这里取模进行调用(考虑到n可能为负数)
    double rest = myPow(x, n % 2);
    //合并,返回结果
    return rest * half * half;
}

这就是一个典型分治算法的题目,先对原问题进行分解,在求解子问题(递归求解,当问题足够小的时候,返回结果),然后对子问题的结果进行合并。

2.回溯

回溯利用了试错的思想,它尝试分步的去解决问题。当分步计算的时候,发现答案错误或者无效时,它会取消上一步,甚至上几步的操作,然后再通过其他的分步解答去找到正确答案。

八皇后

来看看经典的八皇后问题

来说说解题思路,把这个题目放在这篇文章里,当然就是用递归回溯法解决了...好了,接下来就该手撕八皇后了~

首先题目中要求每个皇后都不同行,不同列,也不在对角线上(其实就是题目给我们的过滤条件),不同行,不同列好理解,也好解决,我们就来看看不在对角线上(丿斜对角线、捺斜对角线)

丿对角线有个特点:行下标和列下标之和相等。(图来自LeetCode)

捺斜对角线有个特点:行下标和列下标之差相等。(图来自LeetCode)

好了,题目给我们的过滤条件就罗列出来了,我们需要去穷举皇后出现的位置(不能被攻击到),并记录当前皇后位置可以攻击到的位置。

很多分析都写到代码的注释里了,直接看代码吧~

/**
 * N皇后问题
 * @param n n
 * @return result
 */
public List<List<String>> solveNQueens(int n) {
    //存放结果集
    List<List<String>> solutions = new ArrayList<List<String>>();
    //记录皇后的位置
    int[] queens = new int[n];
    //赋予默认值
    Arrays.fill(queens, -1);
    //记录皇后攻击的列
    Set<Integer> columns = new HashSet<Integer>();
    //记录皇后攻击的丿斜线
    Set<Integer> pie = new HashSet<Integer>();
    //记录皇后攻击的捺斜线
    Set<Integer> na = new HashSet<Integer>();
    //递归调用
    backtrack(solutions, queens, n, 0, columns, pie, na);
    //返回结果
    return solutions;
}

/**
 * 递归函数,穷举皇后的位置
 * @param solutions 结果集
 * @param queens 皇后可以放置的列(数组记录)
 * @param n n个皇后
 * @param row 当前递归是第 row 行
 * @param columns 已有的皇后能攻击到的列
 * @param pie 已有的皇后能攻击到的丿斜线
 * @param na 已有的皇后能攻击到的捺斜线
 */
public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> pie, Set<Integer> na) {
    if (row == n) {
        //当行 等于 n 时,说明已经穷举完,记录结果集
        List<String> board = generateBoard(queens, n);
        solutions.add(board);
    } else {
        //遍历当前行的所有列
        for (int i = 0; i < n; i++) {
            //被攻击的列包含了当前列,跳过当前列,不进行后面的逻辑
            if (columns.contains(i)) {
                continue;
            }
            //被攻击的丿斜线包含了当前位置,跳过当前位置
            if (pie.contains(row + i)) {
                continue;
            }
            //被攻击的捺斜线包含了当前位置,跳过当前位置
            if (na.contains(row - i)) {
                continue;
            }
            //记录当前皇后存放的列
            queens[row] = i;
            //记录当前皇后攻击到的列
            columns.add(i);
            //记录当前皇后攻击到的丿斜线
            pie.add(row+i);
            //记录当前皇后攻击到的捺斜线
            na.add(row-i);
            //递归调用,穷举下一行的皇后位置
            backtrack(solutions, queens, n, row + 1, columns, pie, na);
            /**
             * 经过上面的递归,自顶向下递归完成时就已经穷举出了一种皇后所有可能出现的位置
             * 然后这里需要把之前修改的数据进行清理,穷举另一种皇后所有可能出现的位置,这里是自底向上清理数据(即回溯)
             */
            //清理皇后存放的列
            queens[row] = -1;
            //清理皇后攻击的列
            columns.remove(i);
            //清理皇后攻击的丿斜线
            pie.remove(row+i);
            //清理皇后攻击的捺斜线
            na.remove(row-i);
        }
    }
}

/**
 *
 * @param queens 皇后位置
 * @param n n皇后
 * @return 所有皇后的位置(用.和Q表示)
 */
public List<String> generateBoard(int[] queens, int n) {
    List<String> board = new ArrayList<String>();
    for (int i = 0; i < n; i++) {
        char[] row = new char[n];
        Arrays.fill(row, '.');
        row[queens[i]] = 'Q';
        board.add(new String(row));
    }
    return board;
}

看完代码你学废了吗?八皇后问题这里主要是想来说明一下递归中的回溯,当我们列举一种可能,到最后发现不正确时,需要清理之前的数据,即取消上一步,甚至上好多步的操作。递归函数调用(自顶向下)完成后去清理数据(自底向上),多理解一下这种归去来兮的感觉。

总结

分治:递归调用后,去合并递归得到的结果。

回溯:递归调用后,去取消上一步,上好多步的操作。

分治和回溯本质上都是递归的一种,具体的问题,我们要具体分析,是需要分解后合并结果,还是不断穷举试错,然后回溯。

欢迎关注微信公众号「山主」,公众号文章首发,解锁更多干货~