算法-回溯算法-蒲公英云

算法-回溯算法

一、回溯

1、定义：通过选择不同的岔路口来通往目的地（找到想要的结果）

每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试【回溯很适合使用递归】
举例：二叉树的前序遍历、图的深度优先搜索、八皇后、走迷宫都是典型的回溯应用

2、八皇后问题

任意两个皇后都不能处于同一行、同一列、同一斜线上，请问有多少种摆法？

■ 解法：回溯+剪枝

☆ 巧妙的地方：

1、类比二叉树，二叉树是以 节点 为单位，比如前序遍历，是一个节点又一个节点的往下遍历；同样，八皇后是以 行 为单位，第几行放第几个皇后。

2、充分利用了数据结构一维数组，索引表示皇后的行，元素的值表示皇后所在位置，即第几行(第几个皇后)在第几个列位置

3、斜线判断是否存在皇后，利用了**数学的斜率公式**

int[] cols;//表示皇后的位置，索引是行号，元素值是皇后所在的具体位置
    int ways;//一共有多少种摆法
    void placeQueens(int n) {
        if(n < 1) return;
        cols = new int[n];
        place(0);//从第一个皇后开始摆
        System.out.println(n + "皇后一共有 " + ways + "种摆法");
    }
    /**
     * 从第几行开始摆皇后(摆第几个皇后-以行为单位)
     */
    private void place(int row) {
        if(row == cols.length) {
    //成功放完所有的皇后
            ways++;//找到一种方法
            show();//打印所有皇后的情况
            return;
        }
--------------------------------------------------- 核心代码开始 ---------------------------------------------------
        for(int col = 0; col < cols.length; col++) {
    //遍历所有的列
            if(isValid(row, col)) {
    //该位置可以放皇后
                cols[row] = col;//第row行的col列放上一个皇后
                place(row + 1);//处理下一个皇后，下一行开始摆皇后
            }
        }        
    }
    /**
     * 判断当前位置是否可以放皇后，第几row第几col是否可以放皇后
     */
    private boolean isValid(int row, int col) {
        for(int i = 0; i < row; i++) {
    //遍历在当前位置(新的一行)之前摆放过的皇后
            //判断当前位置是否和之前的皇后处于同一列--col相同
            if(col == cols[i])    return false;
            //判断当前位置是否和之前的皇后处于同一斜线--斜线相同
            if(row - i == Math.abs(col - cols[i]))    return false;//利用数学45度的斜率公式 (y坐标差)/(x坐标差)=1
        }
--------------------------------------------------- 核心代码结束 ---------------------------------------------------        
        return true;
    }