从电影《蝴蝶效应》中学习回溯算法的核心思想

#技术派的书架#

深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单，但应用却 非常广泛。它除用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，如正则表达式匹配、编译原理中的语法分析等。除此之外，很多经典的数学问题也可以用回溯算法解决，如数独、八皇后、0-1背包、图的着色、旅行商、求全排列等。在本文，我们就来学习一下回溯算法思想。

— 01 —

如何理解回溯算法

在我们的一生中，会遇到很多重要的“岔路口”。在人生的岔路口，每个选择都会影响我们今后的人生。有的人在每个“岔路口”都能做出正确的选择，生活、事业可能达到了一个很高的高度；而有的人一路选错，最后可能碌碌无为。如果人生可以量化，那么如何才能在人生的岔路口做出正确的选择，让自己的人生“最优”呢？我们可以借助贪心算法，在每次面对人生岔路口的时候，都做出当下看起来最优的选择，期望这一组局部最优选择可以使得我们的人生达到全局“最优”。

但是，贪心算法并不一定能得到最优解。那么，有没有其他办法能得到最优解呢？2004年，著名的电影《蝴蝶效应》上映，该部电影讲的就是主人公为了达到自己的目标，一直通过回溯的方法，回到童年，在关键的人生岔路口，重新做选择。当然，这只是科幻电影，我们的人生是无法倒退的，但这其中蕴含的思想其实就是回溯算法。回溯算法一般用到与“搜索”有关的问题上。不过这里说的搜索，并不是狭义地指图的搜索，而是在一组可能的解中搜索满足期望的解。回溯的处理思想有点类似枚举（或穷举）。

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

— 02 —

八皇后问题

我们来看一个有关回溯的经典例子：八皇后问题，以进一步解释回溯算法思想。有一个8×8的棋盘，我们往里放 8 个棋子（皇后），要求每个棋子所在的行、列、对角线都不能有另外一个棋子。如图1所示，左侧 图是符合要求的放法，右侧图是不符合要求的放 法。

八皇后问题就是期望找到所有满足这种要求的放棋子方式。我们把求解这个问题的过程划分成8个阶段：在第1行放置棋子、在第2行放置棋子、在第3行放置棋子……在第8行放置棋子。在放置的过程中，我们不停地检查当前的放法是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，就换一种放法，继续尝试。回溯算法比较适合用递归代码实现。

（1）八皇后问题中符合要求的放法和不符合要求的放法

八皇后问题的递归代码实现如下所示:

int[] result = new int[8];//下标表示行，值表示皇后存储在哪一列
public void cal8queens(int row) { //调用方式：cal8queens(0);
  if (row == 8) { //8个棋子都放置好了，输出结果
 printQueens(result);
 return; //8行棋子都放好了，已经没法再往下递归了，因此返回
 }
  for (int column = 0; column < 8; ++column) { //每一行都有8种放法
    if (isOk(row, column)) { //有些放法不满足要求
      result[row] = column; //第row行的棋子放到了column列
      cal8queens(row+1); //考察下一行
 }
 }
}
//判断row行、column列放置是否合适
private boolean isOk(int row, int column) {
 int leftup = column - 1, rightup = column + 1;
  for (int i = row-1; i >= 0; --i) { //逐行往上考察每一行
    if (result[i] == column) return false; //第i行、第column列有棋子
    if (leftup >= 0) { //考察左上对角线：第i行、第leftup列有棋子吗？
 if (result[i] == leftup) return false;
 }
    if (rightup < 8) { //考察右上对角线：第i行、第rightup列有棋子吗？
 if (result[i] == rightup) return false;
 }
 --leftup; ++rightup;
 }
 return true;
}
private void printQueens(int[] result) { //输出一个二维矩阵
 for (int row = 0; row < 8; ++row) {
 for (int column = 0; column < 8; ++column) {
 if (result[row] == column) System.out.print("Q ");
 else System.out.print("* ");
 }
 System.out.println();
 }
 System.out.println();
}

— 03 —

0-1 背包问题

0-1背包是一个非常经典的算法问题，很多场景可以抽象成这个问题模型。这个问题的经典解法是动态规划，不过还有一种简单但没有那么高效的解法，就是本文讲的回溯算法。

如何用回溯法解决这个问题。

0-1背包问题有很多变体，这里介绍一种比较基础的：假设有一个背包，可承载的最大重量是Wkg。现在有n个物品，每个物品的重量不等，并且不可分割。我们期望选择几件物品装到背包中。在不超过背包最大承载重量的前提下，如何让背包中的物品总重量最大？实际上，在贪心算法时，我们已经讲过一个背包问题了。

不过，那里讲的物品（豆子）是可以分割的，允许将某个物品的一部分装到背包中。对于本文讲的这个背包问题，物品是不可分割的，要么装要么不装，因此称为0-1背包问题。显然，这个问题已经无法通过贪心算法来解决了。现在我们来看一下，如何用回溯算法来解决。对于每个物品，都有两种选择：装进背包或者不装进背包。对于n个物品，总的装法就有2n种，从这些装法中选出总重量小于或等于Wkg并且最接近Wkg的。

不过，如何才能不重复地穷举出这2n种装法呢？这里就可以用到回溯算法思想。我们把物品依次排列，整个问题的求解过程就分解为了n个阶段，每个阶段对应一个物品怎么选择。首先，对第一个物品进行处理，选择装进去或者不装进去，然后递归地处理剩下的物品。对于该问题的处理思路，描述起来很费劲，我们直接看如下所示的代码。

这里用到了搜索剪枝的技巧，当发现已经选择的物品的总重量超过Wkg之后，我们就停止继续探测剩下的物品。

public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
//cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了
//w表示背包可以承载的最大重量；items表示每个物品的重量；n表示物品个数
//假设背包可承受重量为100，物品个数为10，物品重量存储在数组a中，
//那么可以这样调用函数：f(0, 0, a, 10, 100)
public void f(int i, int cw, int[] items, int n, int w) {
  // cw==w表示装满了；i==n表示已经考察完所有的物品
 if (cw == w || i == n) {
 if (cw > maxW) maxW = cw;
 return;
 }
 f(i+1, cw, items, n, w);
 if (cw + items[i] <= w) { //没有超过背包可以承载的最大重量
 f(i+1,cw + items[i], items, n, w);
 }
}

— 04 —

正则表达式匹配问题

讲完了0-1背包问题，我们再来看另外一个例子：正则表达式匹配。对于软件工程师，在平时的开发中，或多或少用过正则表达式。其实，正则表达式里非常 重要的一种算法思想就是回溯。在正则表达式中，最重要的就是通配符。利用通配符可以表达非常丰富的语义。为了方便讲解，我们对正则表达式稍加简化，假设正则表达式中只包含“*”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变。

其中，“*”匹配任意多个（大于或等于0个）任意字符，“?”匹配0个或者1个任意字符。基于以上背景假设，我们来探讨一下，如何用回溯算法判断一个给定的文本能否与给定的正则表达式匹配？我们依次考察正则表达式中的每个字符，如果是非通配符，就直接与文本串中的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯。

如果遇到的是特殊字符，就有多种处理方式，也就是所谓的“岔路口”，如“*”可以匹配任意个文本串中的字符，我们就先随意地选择一种匹配方案，然后继续考察剩下的字符。

如果中途发现无法继续匹配下去，就再回到这个“岔路口”，重新选择一种匹配方案，然后继续匹配剩下的字符。我们将上述处理过程“翻译”成代码，如下所示。

public class Pattern {
 private boolean matched = false;
  private char[] pattern; //正则表达式
  private int plen; //正则表达式的长度
 public Pattern(char[] pattern, int plen) {
 this.pattern = pattern;
 this.plen = plen;
 }
  public boolean match(char[] text, int tlen) { //文本串及其长度
 matched = false
 rmatch(0, 0, text, tlen)
;
 return matched;
 }
 private void rmatch(int ti, int pj, char[] text, int tlen) {
    if (matched) return; //如果已经匹配，就不要继续递归了
    if (pj == plen) { //正则表达式到结尾了
      if (ti == tlen) matched = true; //文本串也到结尾了
 return;
 }
    if (pattern[pj] == '*') { //*匹配任意个字符
 for (int k = 0; k <= tlen-ti; ++k) {
 rmatch(ti+k, pj+1, text, tlen);
 }
    } else if (pattern[pj] == '?') { //?匹配0个或者1个字符
 rmatch(ti, pj+1, text, tlen);
 rmatch(ti+1, pj+1, text, tlen);
    } else if (ti < tlen && pattern[pj] == text[ti]) { //纯字符匹配才行
 rmatch(ti+1, pj+1, text, tlen);
 }
 }
}

— 05 —

内容小结

回溯算法思想非常简单，大部分情况下，用来解决广义的搜索问题，也就是从一组可能的解中选出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高搜索效率的一种技巧。利用剪枝，我们可以提前终止搜索不能满足要求的解的过程。

尽管回溯算法的原理非常简单，但可以解决很多问题，如深度优先搜索、八皇后、0-1背包、图的着色、旅行商、数独、求全排列和正则表达式匹配等。如果读者感兴趣，那么可以自己研究一下这些经典的问题，最好还能用代码实现。对于这几个问题，如果读者都能顺利地用代码实现，那么说明读者基本掌握了回溯算法。

本文摘自《数据结构与算法之美》，如果你想了解的更多，请查看本书。

? NO.1 ?

《数据结构与算法之美》

• 点击上图，即可购买《数据结构与算法之美》！

本书结合实际应用场景讲解数据结构和算法，涵盖常用、常考的数据结构和算法的原理讲解、代码实现和应用场景等。

本书分为11章。第1章介绍复杂度分析方法。第2章介绍数组、链表、栈和队列这些基础的线性表数据结构。第3章介绍递归编程技巧、8种经典排序、二分查找及二分查找的变体问题。第4章介绍哈希表、位图、哈希算法和布隆过滤器。第5章介绍树相关的数据结构，包括二叉树、二叉查找树、平衡二叉查找树、递归树和B+树。第6章介绍堆，以及堆的各种应用，包括堆排序、优先级队列、求TopK、求中位数和求百分位数。第7章介绍跳表、并查集、线段树和树状数组这些比较高级的数据结构。第8章介绍字符串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie树和AC自动机。第9章介绍图及相关算法，包括深度优先搜索、广度优先搜索、拓扑排序、Dijkstra算法、Floyd算法、A*算法、最小生成树算法、最大流算法和最大二分匹配等。第10章介绍4种算法思想，包括贪心、分治、回溯和动态规划。第11章介绍4个经典项目中的数据结构和算法的应用，包括Redis、搜索引擎、鉴权限流和短网址服务。

另外，附录A为书中的思考题的解答。尽管本书的大部分代码采用Java语言编写，但本书讲解的知识与具体编程语言无关，因此，本书不但适合各种类型的研发工程师，而且可以作为高校计算机相关专业师生的学习用书和培训学校的教材。

—END—