回溯算法

回溯算法思想简单，但是应用却非常广泛，常用的DFS(Depth-First-Search) 深度优先搜索算法利用的就是回溯算法思想。很多经典的数学问题也都可以用回溯算法解决，比如数独、八皇后、0-1 背包、图的着色、旅行商问题、全排列等等。

如何理解“回溯算法”

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

2004 年上映了一部非常著名的电影《蝴蝶效应》，讲的就是主人公为了达到自己的目标，一直通过回溯的方法，回到童年，在关键的岔路口，重新做选择。当然，这只是科幻电影，我们的人生是无法倒退的，但是这其中蕴含的思想其实就是回溯算法。

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

经典例子

八皇后问题：我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。你可以看我画的图，第一幅图是满足条件的一种方法，第二幅图是不满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。

我们把这个问题划分成8个阶段，依次将8个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放的方法，继续尝试。

回溯算法非常适合用递归代码实现，代码如下。

public class EightQueen {
    private final int[] result = new int[8];

    public static void main(String[] args) {
        EightQueen eightQueen = new EightQueen();
        eightQueen.cal8queens(0);
    }

    /**
     * 8皇后问题
     * @param row row
     */
    public void cal8queens(int row) {
        if (row >= 8) {
            printResult();
            return;
        }
        for (int column = 0; column < 8; column++) {
            if (isOk(row, column)) { // 回溯算法的经典场景，满足条件继续往下，不满足条件即可退出
                this.result[row] = column;
                cal8queens(row + 1);
            }
        }
    }

    /**
     * 是否符合要求
     * @param row    row
     * @param column column
     * @return boolean
     */
    private boolean isOk(int row, int column) {
        int leftUp = column - 1, rightUp = column + 1;
        for (int i = row - 1; i >= 0; i--) {
            if (this.result[i] == column) {
                return false;
            }
            if (leftUp >= 0 && this.result[i] == leftUp) {
                return false;
            }
            if (rightUp < 8 && this.result[i] == rightUp) {
                return false;
            }
            leftUp--;
            rightUp++;
        }
        return true;
    }

    private void printResult() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (result[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

思路：

1. 从第一行开始放置棋子，行数递增。因为第一行放置棋子的时候，棋面是空的，不存在冲突的情况，所以第一行的每一列都可以随意放置棋子。
2. 下一行再放置棋子的时候，就要进行校验控制。对比左上角、右上角、正上方是否已经放置棋子；如果已经放置了，说明当前位置存在问题不能再放置，遍历当前行的下一列；如果当前行所有列都存在问题，回溯到上一行的下一列再进行判断。
3. 对第一行所有列的位置进行一次测验，就可以得到最终结果。

实战案例

正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义。假设正则表达式中只包含 “*” 和 “?” 这两种通配符，并且对这两个通配符的语义稍微做些改变，其中，“*” 匹配任意多个（大于等于 0 个）任意字符，“?” 匹配零个或者一个任意字符。基于以上规则，如何判断一个给定的文本，能否跟给定的正则表达式匹配？

public class PatternTest {
    private boolean matched = false;

    /**
     * 是否匹配
     *
     * @param s 源字符串
     * @param p 正则表达式字符串
     * @return boolean
     */
    public boolean isMatch2(String s, String p) {
        this.matched = false;
        rmatch(0, 0, s, p);
        return this.matched;
    }
    private void rmatch(int si, int pi, String s, String p) {
        if (this.matched) {
            return;
        }

        if (pi == p.length()) {
            if (si == s.length()) {
                this.matched = true;
            }
            return;
        }

        if (p.charAt(pi) == '*') {
            for (int k = 0; k <= s.length() - si; k++) {
                rmatch(si + k, pi + 1, s, p);
            }
        } else if (p.charAt(pi) == '?') {
            rmatch(si, pi + 1, s, p);
            rmatch(si + 1, pi + 1, s, p);
        } else if (si < s.length() && p.charAt(pi) == s.charAt(si)) {
            rmatch(si + 1, pi + 1, s, p);
        }
    }
}

思路：

• 回溯算法终止条件：匹配表达式字符串p已经遍历完成
  • 成功：文本字符串s也已经遍历完成
  • 失败：文本字符串s还没有遍历完成
• 表达式字符串p，当前字符判断
  • • ： p字符串往后顺延一个，s可以往后顺延0到s.length()个
  • ? : p字符串往后顺延一个，s可以往后顺延0个或者1个
  • 当前字符和s的当前字符相等，则p和s都可以继续往后顺延一个。

总结分析

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

尽管回溯算法的原理非常简单，可以解决很多问题，但是从实际问题联想到回溯算法才是从学会到掌握的过程。比如我们开头提到的深度优先搜索、八皇后、0-1 背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等等。