美文网首页
LeetCode 回溯专题 8:回溯法是经典的人工智能的基础

LeetCode 回溯专题 8:回溯法是经典的人工智能的基础

作者: 李威威 | 来源:发表于2019-05-28 23:20 被阅读0次

    回溯法是经典的人工智能的基础,这句话中"经典"可以理解为"传统"。现如今,人工智能领域有一个非常流行的话题,那就是机器学习。

    下面我们就来介绍一个传统的人工智能问题:n 皇后问题。同样地,它是典型的递归回溯问题。

    例题: LeetCode 第 51 题:N 皇后

    传送门:英文网址:51. N-Queens ,中文网址:51. N皇后

    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    LeetCode 第 51 题:N 皇后

    上图为 8 皇后问题的一种解法。

    给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

    每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

    示例:

    输入: 4
    输出: [
     [".Q..",  // 解法 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // 解法 2
      "Q...",
      "...Q",
      ".Q.."]
    ]
    解释: 4 皇后问题存在两个不同的解法。
    

    分析:虽然看起来,这是一个人工智能的问题,但是我们的代码实现方式完全可以理解为暴力解法,只不过我们使用“递归回溯”方式的暴力解法,可以很快地判断暴力的过程中产生的结果是否符合条件,而不是把所有的暴力解都的出来以后再去掉不符合条件的;
    例如:我们在第 1 行第 1 列已经放置了元素,那么很显然,在第 2 行第 1 列和第 2 列放置元素的情况就已经被排除掉了,第 2 行的第 3 列我们发现可以放置元素,于是继续遍历下去;

    从上面的分析中,我们可以看到“递归”、“回溯”与“暴力解法”、“深度优先遍历”有着千丝万缕的联系;

    其实这道问题,很像我们前面介绍的排列问题。我们想想,是不是每一层的一开始其实我们都有 n 种摆放的方法,但是因为游戏规则,在每一层我们会排除掉一些可能,在每一层我们都会记录之前的状态,回溯以后,状态还要恢复;

    在解题思路上,我们采用还是一行一行去思考皇后位置的摆放,因此外层只要用一层循环。

    Java 实现:

    public class Solution {
    
        private boolean[] col; // 记录在列上第几列已经放置了元素
        private boolean[] dia1; // 记录在主对角线上哪些位置已经放置了元素
        private boolean[] dia2; // 记录在副对角线上哪些位置已经放置了元素
        private List<List<String>> res = new ArrayList<>();
    
        public List<List<String>> solveNQueens(int n) {
            col = new boolean[n];
            dia1 = new boolean[2 * n - 1]; // 可以用归纳法得到对角线上的元素个数
            dia2 = new boolean[2 * n - 1]; // 可以用归纳法得到对角线上的元素个数
            putQueue(n, 0, new ArrayList<Integer>());
            return res;
        }
    
        /**
         * 尝试在一个 n 皇后的问题中,摆放第 index 行的皇后的位置
         *
         * @param n
         * @param index
         * @param row
         */
        private void putQueue(int n, int index, List<Integer> row) {
            if (index == n) {
                res.add(generateBoard(n, row));
                return;
            }
            // i 表示第几列,循环的过程就是在尝试给每一行的每一列放置皇后,看看在列上能不能放,看看在对角线上能不能放
            // 其实 n 皇后问题和使用回溯解决排列问题的思路是一致的:暴力遍历,使用额外数组记录状态,一层层减少,递归到底以后回溯,回溯的过程中,一层一层地恢复状态
            for (int i = 0; i < n; i++) {
                if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                    row.add(i);
                    col[i] = true;
                    dia1[index + i] = true;
                    dia2[index - i + n - 1] = true;
                    putQueue(n, index + 1, row);
                    col[i] = false;
                    dia1[index + i] = false;
                    dia2[index - i + n - 1] = false;
                    row.remove(row.size() - 1);
                }
            }
        }
    
    
        private List<String> generateBoard(int n, List<Integer> row) {
            List<String> res = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(".");
            }
            StringBuilder cur = null;
            for (int i = 0; i < n; i++) {
                cur = new StringBuilder(sb);
                int queueLoc = row.get(i);
                cur.replace(queueLoc, queueLoc + 1, "Q");
                res.add(cur.toString());
            }
            return res;
        }
    
        // 测试用例
        public static void main(String[] args) {
            Solution solution = new Solution();
            List<List<String>> solveNQueens = solution.solveNQueens(8);
            for (int i = 0; i < solveNQueens.size(); i++) {
                System.out.println("第 " + (i + 1) + " 种解法:");
                List<String> sloveOne = solveNQueens.get(i);
                printList(sloveOne);
                System.out.println("********");
            }
        }
    
        private static void printList(List<String> sloveOne) {
            for (int i = 0; i < sloveOne.size(); i++) {
                System.out.println(sloveOne.get(i));
    
            }
        }
    }
    

    知识补充:n 皇后问题有很多优化的思路,可以加快搜索的过程。(因为时间关系,以后我们再关注)

    练习

    练习1:LeetCode 第 52 题:N-Queens II

    传送门:英文网址:52. N-Queens II ,中文网址:52. N皇后 II

    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    LeetCode 第 52 题:N-Queens II

    上图为 8 皇后问题的一种解法。

    给定一个整数 n,返回 n 皇后不同的解决方案的数量。

    示例:

    输入: 4
    输出: 2
    解释: 4 皇后问题存在如下两个不同的解法。
    [
     [".Q..",  // 解法 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // 解法 2
      "Q...",
      "...Q",
      ".Q.."]
    ]
    

    Java 代码:

    import java.util.Stack;
    
    public class Solution {
    
        private boolean[] marked;
        private int count;
    
        public int totalNQueens(int n) {
            if (n == 0 || n == 1) {
                return n;
            }
            int[] board = new int[n];
            for (int i = 0; i < n; i++) {
                board[i] = i;
            }
            permuta(board);
            return count;
        }
    
        // 生成一个 [0,1,...,n-1] 的全排列
        private void permuta(int[] board) {
            int len = board.length;
            marked = new boolean[len];
            Stack<Integer> pre = new Stack<>();
            findPermutation(board, 0, len, pre);
        }
    
        private void findPermutation(int[] board, int usedCount, int len, Stack<Integer> pre) {
            if (usedCount == len) {
                // 判断是否是符合要求的棋盘布局
                if (noDanger(pre, len)) {
                    count++;
                }
                return;
            }
    
            for (int i = 0; i < len; i++) {
                if (!marked[i]) {
                    marked[i] = true;
                    pre.push(board[i]);
                    findPermutation(board, usedCount + 1, len, pre);
                    marked[i] = false;
                    pre.pop();
                }
    
            }
        }
    
        private boolean noDanger(Stack<Integer> pre, int len) {
            int[] board = new int[len];
            for (int i = 0; i < len; i++) {
                board[i] = pre.get(i);
            }
            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    // 得到所有不同的 i j 的组合,是一个组合问题,按顺序来就行
                    // System.out.println(i + "\t" + j);
                    if (i - j == board[i] - board[j]) {
                        return false;
                    }
                    if (i - j == -(board[i] - board[j])) {
                        return false;
                    }
                }
    
            }
            // 走到这里表示通过检验
            // System.out.println(Arrays.toString(board));
            return true;
        }
    
        public static void main(String[] args) {
            Solution solution = new Solution();
            int totalNQueens = solution.totalNQueens(8);
            System.out.println(totalNQueens);
        }
    }
    

    练习2:LeetCode 第 37 题:求解数独

    传送门:37. 解数独

    分析:这是比 n 皇后问题更酷的问题,典型的人工智能的问题,自动来解决,递归加上回溯,有效剪枝,人工智能的开始章节一般就将搜索问题。

    编写一个程序,通过已填充的空格来解决数独问题。

    一个数独的解法需遵循如下规则

    1. 数字 1-9 在每一行只能出现一次。
    2. 数字 1-9 在每一列只能出现一次。
    3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

    空白格用 '.' 表示。

    LeetCode 第 37 题:求解数独-1
    一个数独。
    LeetCode 第 37 题:求解数独-2

    答案被标成红色。

    Note:

    • 给定的数独序列只包含数字 1-9 和字符 '.'
    • 你可以假设给定的数独只有唯一解。
    • 给定数独永远是 9x9 形式的。

    Python 代码:

    import time
    import sys
    
    
    # 虽然成功了,但是已经超时!!!
    
    # 37. 解数独
    # 编写一个程序,通过已填充的空格来解决数独问题。
    #
    # 一个数独的解法需遵循如下规则:
    #
    # 数字 1-9 在每一行只能出现一次。
    # 数字 1-9 在每一列只能出现一次。
    # 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    # 空白格用 '.' 表示。
    class Solution:
    
        def __print(self, board):
            result = ''
            # i 表示行,是纵坐标,要特别注意
            for i in range(9):
                # j 表示列,是横坐标,要特别注意
                for j in range(9):
                    if board[i][j] == '.':
                        result += ' '
                    else:
                        result += board[i][j]
                    result += ' '
                result += '\n'
            return result
    
        def check(self, board, x, y):
            # x 表示横坐标,y 表示纵坐标
            num = board[x][y]
            # 水平方向上,已经出现的数
            h_nums = [board[x][col_index] for col_index in range(9) if col_index != y and board[x][col_index] != '.']
            # 判断
            if num in h_nums:
                return False
            # print('h_nums', h_nums)
    
            # 垂直方向方向上,已经出现的数
            v_nums = [board[row_index][y] for row_index in range(9) if row_index != x and board[row_index][y] != '.']
            # 判断
            if num in v_nums:
                return False
            # print('v_nums', v_nums)
    
            # 重点理解下面这个变量的定义:所在小正方形左上角的横坐标
            x_left = (x // 3) * 3
            # 重点理解下面这个变量的定义:所在小正方形左上角的纵坐标
            y_up = (y // 3) * 3
    
            block_nums = []
            for row in range(3):
                for col in range(3):
                    if not ((x_left + row) == x and (y_up + col) == y):
                        if board[x_left + row][y_up + col] != 0:
                            block_nums.append(board[x_left + row][y_up + col])
    
            # print('block_nums', block_nums)
    
            if num in block_nums:
                return False
            # 以上 3 个条件都判断完以后,才能把 val 放在坐标 (x,y) 处
            return True
    
        def next(self, board):
            # i 表示每一行
            for i in range(9):
                # j 表示每一列
                for j in range(9):
                    if board[i][j] == '.':
                        return i, j
            # 表示没有下一个元素了,数独任务完成
            return False
    
        def __accept(self, board):
            # 如果没有了,就表示填完,返回 True
            if self.next(board) is False:
                return True
            # 否则就表示数独任务没有完成
            return False
    
        def __solve(self, board):
            # time.sleep(0.1)
            # print(board)
            # sys.stdout.flush()
    
            # 先写递归终止条件
            if self.__accept(board):
                return True
            x, y = self.next(board)
            for i in range(1, 10):
                board[x][y] = str(i)
                if self.check(board, x, y) and self.__solve(board):
                    return True
                board[x][y] = '.'
            return False
    
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            self.__solve(board)
    
    
    if __name__ == '__main__':
        board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
                 ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
                 ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
                 ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
                 ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
                 ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
                 ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
                 ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
                 ['.', '.', '.', '.', '8', '.', '.', '7', '9']]
        solution = Solution()
        solution.solveSudoku(board)
    
        for row in board:
            print(row)
    

    这一部分的内容到此为止,下一部分我们学习动态规划。

    (本节完)

    相关文章

      网友评论

          本文标题:LeetCode 回溯专题 8:回溯法是经典的人工智能的基础

          本文链接:https://www.haomeiwen.com/subject/prattctx.html