17、数据结构与算法进阶:回溯

摘要

回溯本质就是前进不成,就后退一步换另外一条路继续前进,直到到达目的地。它在树结构、图结构中都有应用。本文通过解决八皇后的问题来了解回溯的思想。

回溯可以理解成在岔路口选择不同的道路,直到达到目的地。它的每一步都会选择一条路出发,能前进都前进,不能前进就退到上一步,选择其他的路走,直到走完所有路或者到达目的地为止。不能前进就退到上一步的过程就是回溯

典型的回溯应用有树、图的深度优先搜索、八皇后问题或者走迷宫等等。这里以八皇后的问题为例,来看一下回溯。

八皇后问题是在一个8X8的棋牌中放8个皇后,使其不能相互攻击,也就是任意两个皇后不能在同一行、同一列、同一斜率上。

解决思路

解决八皇后问题,有这样几种思路,第一种就是暴力破解,从64个格子中选择出任意的8个格子摆放皇后,然后检查摆法是否合适,检查完每一种,需要检查的次数非常的大。

那么,可以根据题意来减少暴力破解的次数,因为任意两个皇后不能在同一行,也就是每一行只能放一个皇后,所以摆放的次数就减少成 88 次。虽然次数减少了很多,但是次数还是比较多的。

最后一个思路就是用回溯法来处理,每次摆放皇后后,就将不能被摆放的格子给剔除掉,这种操作叫做剪切。当到了无法摆放,并且皇后也没有摆放完时,就退回到最初摆放第一个皇后的位置,排除这个位置,从下一个位置开始,这个操作叫做回溯。所以这个思路是回溯+剪切

实现代码

首先创建一个类,并定义数组,保存皇后摆放的位置 colscols 数组的索引对应的是第几行,从 0 开始,索引对应的元素是第几列,从 0 开始,也就是存储的数据是第几行中的第几列摆放了皇后,其次还定义一个属性 ways 记录有多少种摆法:

public class Queens {
   
     
    /**
     * 数组索引是行号,数组元素是列号
     */
    int[] cols;

    /**
     * 一共有多少种排法
     */
    int ways;
}

接下来创建摆放八皇后的函数,placeQueens(),函数中传递参数 n,表示摆放多少个皇后,让函数适应更多的同类场景,所以摆放八皇后就是 placeQueens(8),代码实现如下:

void placeQueens(int n) {
   
     
    if (n < 1) return;
    cols = new int[n];
    place(0);
    System.out.println(n + "皇后一共有" + ways + "种摆法");
}

函数中先定义了 cols 数组的大小,有多少个皇后,就创建多少空间的数组。place() 函数执行的是摆放皇后的过程,传递的参数表示从第几行开始摆放,具体代码如下:

void place(int row) {
   
     

    // 终止指令
    if (row == cols.length) {
   
     
        ways ++;
        return;
    }

    for (int col = 0; col < cols.length; col++) {
   
     
        if (isValid(row, col)) {
   
     
            cols[row] = col;
            place(row + 1);
        }
    }
}

函数中可以看到 place(row+1) 这行代码,就是跳到下一行执行。当某行某列已经确定可以摆放皇后后,就暂时结束该行的遍历,跳到下一行执行。这里使用到递归思想, for 循环结束都是回溯的条件,如果没有达到终止条件,那么就会走 for 循环,当走完for 循环仍然没有找到可以摆放的位置时,然后执行 place(row+1) 上一行的代码,这就达到了路不通,就回到上一步选择另外一条路isValid(row, col) 函数就是判断 (row, col) 的格子是否可以摆放皇后,代码如下:

boolean isValid(int row, int col) {
   
     
    // row 的遍历要从 i 开始
    for (int i = 0; i < row; i++) {
   
     
        // 第 col 列已经有皇后
        if (cols[i] == col) {
   
     
            return false;
        }

        // 第i行的皇后跟第row行第col列格子处于同一斜线上
        // 利用斜率解决,即 x1-x2 = y1-y2
        // row 永远大于 i ,所以不用取绝对值
        if (row - i == Math.abs(col - cols[i])) {
   
     
            return false;
        }
    }
    return true;
}

这就是摆放皇后的核心部分。首先判断 col 列是否已经有皇后了,即遍历 cols 数组中是否存在 col 元素。如果不存在,就判断该 i 行的皇后和 (row, col) 区域的格子是否在同一斜率上,这里使用了斜率公式,x1-x2 = y1-y2 就是在同一斜率上,因为摆放的皇后,它的斜率就是 1。

斜率公式

k= (y2-y1)/(x2-x1)

总结

  • 回溯很多时候使用递归来处理;
  • 使用斜率等于1来判断摆放皇后的斜线;
  • 代码中的回溯条件就是走完 for 循环,这个地方需要细品。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: