回溯是递归的一种形式。

通常情况下，你会面临很多选择，你必须从中选择一个。在你做出选择后，你会得到一组新的选项；你得到的选择取决于你做出的选择。这个过程反复进行，直到达到最终状态。如果你做出了一系列正确的选择，你的最终状态就是目标状态；如果你没有，那就不是正确答案了

从概念上讲，你从树根开始，这棵树可能有一些叶子，这些叶子有可能是好的，又有可能是坏的。你要找到一片好叶子。

• 在每个节点上，从根节点开始，选择它的一个子节点进行移动，并一直这样做，直到到达叶节点。
• 假设你碰到一片坏叶子，通过撤销最近的选择，并尝试该选项集中的下一个选项，以继续搜索好叶子。如果你用尽了所有的选项，那么取消让你到底这里的选项，并在该节点尝试另一个选项。如果你在根上没有选择，那就没有好的叶子了。

看个例子：

1. 从根节点开始，你有两个选项，A和B。现在你选择A
2. 在A上，你有两个选项，C和D。然后你选择C
3. C是坏叶子，回退到A
4. 在A上，应该C已经选过了而且失败了，所以尝试D
5. D是坏叶子，回退到A
6. 现在A上已经没有剩下的选项可以尝试了，回退到根节点
7. 在根节点，A已经尝试过了，所以选择B
8. 在B节点上，有E、F两个选项。选择E
9. E是好叶子。OK

在这个例子中，我们画了一棵树。这棵树是我们可能做出的选择序列的抽象模型。虽然有一种叫做树的数据结构，但通常我们没有一个数据结构来告诉我们有什么选择。(如果我们确实有一个实际的树型数据结构，对它的回溯称为深度优先树搜索。)

回溯递归写法

以下是从给定节点n进行回溯的算法（伪代码）：

boolean solve(Node n) {
    if n 是叶子节点 {
        if 叶子节点是好叶子, return true
        else return false
    } else {
        for 遍历n的每个孩子 {
            if solve(孩子) 成功了, return true
        }
        return false
    }
}

请注意，该算法表示为布尔函数。这对理解算法至关重要。

• 如果solve（n）为true，则意味着节点n是解决方案的一部分——也就是说，节点n是从根节点到某个目标节点的路径上的节点之一。我们说n是可解的。
• 如果solve（n）为false，则不存在到任何目标节点的包含n的路径。

为什么呢？

• 如果n的任何子元素是可解的，那么n是可解的。
• 如果n的子代都不可解，那么n就不可解。

因此，要确定任何非叶节点n是否可解（目标节点路径的一部分），只需测试n的任何子节点是否可解。这是在n的每个子代上递归完成的。在上面的代码中，这是通过如下行来完成的

		for 遍历n的每个孩子 {
            if solve(孩子) 成功了, return true
        }
        return false

最终，递归将在叶节点处“底部”。如果叶子节点是一个目标节点，它是可解的；如果叶节点不是目标节点，则它不可解。这是我们的基本情况。在上面的代码中，这是由如下行完成的

    if n 是叶子节点 {
        if 叶子节点是好叶子, return true
        else return false
    }

回溯算法很简单，但很重要。你应该彻底理解它。另一种说法是：

要搜索树，请执行以下操作：

• 如果树由一片叶子组成，测试它是否是目标节点，
• 否则，搜索子树，直到找到一个包含目标节点的子树，或者直到搜索全部失败。

使用栈的非递归回溯

回溯是一种非常典型的递归算法，任何递归算法都可以重写为堆栈算法。事实上，这就是递归算法被翻译成机器或汇编语言的方式。

boolean solve(Node n) {
   将节点n压入栈；
    while the stack is not empty {
        if 栈顶部是叶子节点 {
            if it is a goal node, return true
            else 把它从栈顶弹出
        }
        else {
            if 栈顶部的节点有未尝试的子节点
                将下一个未尝试的子节点推到栈上
            else 把它从栈顶弹出

    }
    return false
}

从根节点开始，唯一可以被推送到堆栈上的节点是当前在堆栈顶部的节点的子节点，并且这些节点一次只能推送到一个子节点上;因此，堆栈上的节点在任何时候都描述了树中的一条有效路径。只有当已知节点的后代中没有目标节点时，才会从堆栈中删除节点。因此，如果根节点被删除(使堆栈为空)，那么肯定根本没有目标节点，也没有问题的解决方案。

当堆栈算法成功终止时，堆栈上的节点(以相反的顺序)形成一条从根节点到目标节点的路径。

类似地，当递归算法找到一个目标节点时，路径信息(以相反的顺序)体现在递归调用的序列中。因此，当递归展开时，可以通过(例如)打印当前级别的节点或将其存储在数组中，一次恢复一个节点的路径。

下面是递归回溯算法，稍微修改了一下，以倒序打印成功路径上的节点:

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node {
           print n
           return true
        }
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds {
                print n
                return true
            }
        }
        return false
    }
}

编程技巧

所有这些版本的回溯算法都非常简单，但当应用到实际问题时，它们可能会变得非常混乱。甚至确定节点是否是叶子也可能很复杂：例如，如果路径代表国际象棋终局问题中的一系列动作，那么叶子就是将死和相持的解决方案。

因此，为了保持程序干净，像这样的测试应该被埋入方法中。例如，在国际象棋游戏中，您可以通过编写gameOver方法（或者您甚至可以将其称为isLeaf）来测试节点是否为叶子。这种方法将封装所有难看的细节，以确定是否还有任何可能的举措。

请注意，回溯算法要求我们跟踪当前路径上的每个节点，其中哪些子节点已经尝试过（因此我们不必再次尝试）。在上面代码中，只需要for 遍历n的每个孩子 {即可。但是实际应用时，可能很难找出可能的孩子是什么，并且可能没有明显的方法来跨越他们。例如，在国际象棋中，一个节点可以表示棋盘上棋子的一种排列方式，该节点的每个子节点可以在某个棋子做出合法移动后表示该排列方式。你是如何找到这些孩子的？你是如何记录你已经检查过的孩子的？

跟踪节点的哪些子节点已被尝试的最直接的方法如下：

• 在初始进入节点时（即，当您第一次从上面到达节点时），列出其所有子节点。
• 当你尝试每一个孩子时，把它从列表中去掉。
• 当列表为空时，没有剩余的未尝试的子项，您可以返回“失败”

这是一个简单的方法，但它可能需要相当多的额外工作。

如果你可以排序子节点，那么有一种更简单的方法来跟踪哪些孩子被试过。如果有一个命令，并且你知道你刚刚尝试了哪个孩子，你可以决定下一个要尝试哪个孩子。

• 例如，您可以将子项1编号到n，然后按数字顺序尝试。然后，如果你刚刚尝试了子k，你知道你已经尝试了子1到k-1，你还没有尝试过子k+1到n。
• 或者，如果你试图用四种颜色给地图上色，你总是可以先尝试红色，然后黄色，然后绿色，然后蓝色。如果child yellow失败，你知道下一步要尝试child green。
• 如果你在迷宫中搜索，你可以按左、直、右（或者北、东、南、西）的顺序尝试选择。

要找到一种简单的方法来排序节点的子节点并不总是那么容易。

• 如果你能找到简单的排序方法，那么就使用它
• 如果太麻烦，最好保留一份未经测试的子节点的名单

例子：树搜索

假如有一个二叉树：

public class BinaryTree {
    BinaryTree leftChild = null;
    BinaryTree rightChild = null;
    boolean isGoalNode = false;
    String name;
    
    BinaryTree(String name, BinaryTree left, BinaryTree right, boolean isGoalNode) {
        this.name = name;
        leftChild = left;
        rightChild = right;
        this.isGoalNode = isGoalNode;
    }
}

接下来，我们将创建一个TreeSearch类，并在其中定义一个方法makeTree（），该方法构造上述二叉树。

static BinaryTree makeTree() {
    BinaryTree root, a, b, c, d, e, f;
    c = new BinaryTree("C", null, null, false);
    d = new BinaryTree("D", null, null, false);
    e = new BinaryTree("E", null, null, true);
    f = new BinaryTree("F", null, null, false);
    a = new BinaryTree("A", c, d, false);
    b = new BinaryTree("B", e, f, false);
    root = new BinaryTree("Root", a, b, false);
    return root;
}

主程序：

public static void main(String args[]) {
    BinaryTree tree = makeTree();
    System.out.println(solvable(tree));
}

最后，这里是递归回溯例程，通过查找目标节点来“求解”二叉树。

static boolean solvable(BinaryTree node) {
/* 1 */  if (node == null) return false;
/* 2 */  if (node.isGoalNode) return true;
/* 3 */  if (solvable(node.leftChild)) return true;
/* 4 */  if (solvable(node.rightChild)) return true;
/* 5 */  return false;
}

现在，我们来看看每一行在做什么：

1. 如果给我们一个空节点，它是不可解的。这样我们就可以用一个节点的子节点调用这个方法，而不用先检查这些子节点是否确实存在。
2. 如果给我们的节点是目标节点，则返回success。
3. 查看节点的左子节点是否可解，如果是，则得出节点可解的结论。to说：“只有当节点非空且不是目标节点时，我们才能到达这一行。”
4. 为右子节点做同样的事情。
5. 因为节点的子节点都不可解，所以节点本身也不可解

该程序运行正确，并产生令人失望的结果。

每次我们请求另一个节点时，我们都必须检查它是否为空。在上面的例子中，我们把检查作为可解的第一件事。另一种方法是首先检查每个孩子是否存在，只有在他们存在时才会触发。以下是另一个版本：

static boolean solvable(BinaryTree node) {
    if (node.isGoalNode) return true;
    if (node.leftChild != null && solvable(node.leftChild)) return true;
    if (node.rightChild != null && solvable(node.rightChild)) return true;
    return false;
}

第一个版本更简单，但第二个版本效率略高。

What are the children?

简化上述二叉树搜索的一个方法是，在每个选择点，你可以忽略之前所有的选项。之前的选择并没有告诉你下一步该做什么的信息：左节点和右节点都是可能的解决方案。然而，在许多问题中，能够立即消除子项，而不需要递归。

例如，考虑一下地图的四色问题。这是一个数学定理，在一个平面上的任何地图，无论国家多么复杂，最多可以有四种颜色，因此没有两个共享边界的国家是相同的颜色。

要给地图着色，首先为第一个国家选择一种颜色，然后为第二个国家选择一种颜色，依此类推，直到所有国家都着色。有两种方法:

• 方法1：尝试四种可能的颜色，然后重复。当您离开国家时，检查您是否处于目标节点。
• 方法2：只尝试那些没有在邻近国家使用过的颜色，然后重复使用。如果你用完了所有的国家，你就成功地为地图上色了。

让我们分别用这两种方法来解决给棋盘上色的问题。这应该很容易解决;毕竟，一个棋盘只需要两种颜色。

在这两种方法中，颜色都用整数表示，从RED=1到BLUE=4。我们定义了以下辅助方法。这里没有显示helper方法代码，因为它对于理解执行回溯的方法并不重要。

• boolean mapIsOK()：
  • 用于检查(在叶节点)整个地图的颜色是否正确。
• boolean okToColor(int row, int column, int color)
  • 用于检查在每个节点上是否有一个相邻的节点已经用给定的颜色着色。
• int[] nextRowAndColumn(int row, int column)
  • 用于查找下一个“国家”(实际上是棋盘上下一个方格的行和列)。

下面是方法1的代码：

boolean explore1(int row, int column, int color) {
    if (row >= NUM_ROWS) return mapIsOK();
    map[row][column] = color;
    for (int nextColor = RED; nextColor <= BLUE; nextColor++) {
        int[] next = nextRowAndColumn(row, column);
        if (explore1(next[0], next[1], nextColor)) return true;
    }
    return false;
}

下面是方法2的代码：

boolean explore2(int row, int column, int color) {
    if (row >= NUM_ROWS) return true;
    if (okToColor(row, column, color)) {
        map[row][column] = color;
        for (int nextColor = RED; nextColor <= BLUE; nextColor++) {
            int[] next = nextRowAndColumn(row, column);
            if (explore2(next[0], next[1], nextColor)) return true;
        }
    }
    return false;
}

下面是运行效率：

上表中的0表示时间太短，无法测量(小于1毫秒)。为什么会有这么大的差异?这两种方法都可以呈指数增长。消除一个节点会自动消除它的所有派生节点，这通常会阻止指数增长。相反，通过等待直到到达叶节点才进行检查，实际上可以保证指数增长。如果有任何方法可以消除子元素(减少选择的集合)，那么就这么做吧!