我们的一生会遇到很多岔路口，每个选择都会影响我们今后的人生。有的人在每个岔路口都能做出最正确的选择，最后生活、事业都达到了一个很高的高度；而有的人一路选错，最后碌碌无为。如果人生可以量化，那如何才能在岔路口做出最正确的选择，让自己的人生最优呢？

我们可以借助贪心算法，在每次面对岔路口的时候，都做出在当时看起来最优的选择，但是，贪心算法并不一定能得到全局的最优解。那有没有什么办法能得到最优解呢？回溯算法就是用来解决这类问题的。笼统地讲，回溯算法很多时候都应用在“搜索”这类问题上。不过这里的搜索，并不是狭义的指前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通时（不符合期望的解）就回退到上一个岔路口，另选一种走法继续走。

八皇后问题

八皇后问题是回溯算法应用的典型例子。我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。以下图所示，第一幅图是满足条件的一种方法，第二幅图是不满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。
image.png
我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置过程中，我们不停地检查当前放法，是否满足要求。满足则跳到下一行继续放置棋子；不满足就换种放法继续尝试。

代码实现

  1. public class EightQueen {
  3.     /** 数组下标为行，值为棋子在该行所处的列 */
  4.     private static final int[] queen = new int[8];
  6.     /**
  7.      * 放棋子(皇后)，获取符合条件的每种排列组合
  8.      *
  9.      * @param row 行数，从0开始
  10.      */
  11.     public void putQueen(int row) {
  12.         // 棋子放置完毕，打印棋盘
  13.         if (row == queen.length) {
  14.             printEightQueen();
  15.             return;
  16.         }
  17.         // 循环每列，即会获取第一个棋子在第一行中的每一列的所有排列组合
  18.         for (int column = 0; column < queen.length; column++) {
  19.             // 判断本次放法是否满足要求
  20.             if (putSuccess(row, column)) {
  21.                 queen[row] = column;
  22.                 // 递归放置棋子
  23.                 putQueen(row + 1);
  24.             }
  25.         }
  26.     }
  28.     /**
  29.      * 判断row行column列放置是否合适，row、column都是从0开始
  30.      */
  31.     private boolean putSuccess(int row, int column) {
  32.         int leftUp = column - 1;
  33.         int rightUp = column + 1;
  35.         // 遍历row上面的已经放置了棋子的所有行，i表示row的上一行，因为row从0开始，所以i>=0
  36.         for (int i = row - 1; i >= 0; i--) {
  37.             // 判断在该行以上的其他行中，有没有棋子放在了同一列上的
  38.             if (queen[i] == column) {
  39.                 return false;
  40.             }
  41.             // 判断该位置的左上位置是否已经有棋子了，即左对角线
  42.             if (leftUp >= 0) {
  43.                 if (queen[i] == leftUp) {
  44.                     return false;
  45.                 }
  46.             }
  47.             // 判断该位置的右上位置是否已经有棋子了，即右对角线
  48.             if (rightUp < 8) {
  49.                 if (queen[i] == rightUp) {
  50.                     return false;
  51.                 }
  52.             }
  53.             leftUp--;
  54.             rightUp++;
  55.         }
  56.         return true;
  57.     }
  59.     /**
  60.      * 打印二维矩阵的棋盘
  61.      */
  62.     private void printEightQueen() {
  63.         for (int row = 0; row < queen.length; row++) {
  64.             for (int column = 0; column < queen.length; column ++) {
  65.                 if (queen[row] == column) {
  66.                     System.out.print("Q ");
  67.                 } else {
  68.                     System.out.print("* ");
  69.                 }
  70.             }
  71.             System.out.println();
  72.         }
  73.         System.out.println();
  74.     }
  75. }

0-1 背包问题

0-1 背包是非常经典的算法问题，很多场景都可以抽象成这个问题模型。这个问题的经典解法是动态规划，不过还有一种简单但没有那么高效的解法，就是回溯算法。我们先来看下，如何用回溯法解决这个问题？

假设我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等且不可分割。我们期望选择几件物品装到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

之前在讲贪心算法时讲到了背包问题，不过那里讲的物品是可以分割的，我们可以装某个物品的一部分到背包里。今天讲的这个背包问题，物品是不可分割的，要么装要么不装，所以叫 0-1 背包问题。显然，这个问题已经无法通过贪心算法来解决了。那我们现在来看看，用回溯算法如何解决呢？

解题思路
对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2n 种，我们去掉总重量超过 Wkg 的装法，然后从剩下的装法中选择总重量最接近 Wkg 的，就是总重量最大的装法。但是，我们要如何才能不重复地穷举出这 2n 种装法呢？

这里就可以用回溯算法的处理思想。我们可以把物品依次排列，那整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。在处理过程中，当发现已经选择的物品的重量超过 Wkg 后，我们就停止继续探测剩下的物品，提前结束本次递归。

代码实现

  1. public class ZeroOnePackage {
  3.     /** 每个物品的重量 */
  4.     private final int[] itemWeight;
  6.     /** 背包可承载的总容量 */
  7.     private final int packageCapacity;
  9.     /** 选择装入到背包中的物品的总容量 */
  10.     private int maxSelectCapacity = 0;
  12.     public ZeroOnePackage(int packageCapacity, int[] itemWeight) {
  13.         this.itemWeight = itemWeight;
  14.         this.packageCapacity = packageCapacity;
  15.     }
  17.     /**
  18.      * 把物品放入背包中
  19.      *
  20.      * @param index 当前要装载物品的索引
  21.      * @param currentWeight 当前背包已装载的重量
  22.      */
  23.     private void put(int index, int currentWeight) {
  24.         // 如果背包容量装满了或者物品装完了
  25.         if (currentWeight == packageCapacity || index == itemWeight.length) {
  26.             // 更新当前背包装载的最大重量
  27.             if (currentWeight > maxSelectCapacity) {
  28.                 this.maxSelectCapacity = currentWeight;
  29.             }
  30.             return;
  31.         }
  32.         // 表示不选择当前物品，直接考虑下一个
  33.         put(index + 1, currentWeight);
  34.         // 如果已经超过了背包容量，就不再装了
  35.         if (currentWeight + itemWeight[index] <= packageCapacity) {
  36.             // 选择当前物品，更新currentWeight
  37.             put(index + 1, currentWeight + itemWeight[index]);
  38.         }
  39.     }
  40. }

总结

回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率（比如超过背包容量就提前结束递归）。

尽管回溯算法的原理非常简单，但是却可以解决很多问题，比如深度优先搜索、八皇后、0-1 背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等等。