回溯算法

      回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

1、回溯法的一般描述

可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x₁，x₂，…，x_n）组成的一个状态空间E={（x₁，x₂，…，x_n）∣x_i∈S_i，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中S_i是分量x_i的定义域，且 |S_i| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x₁，x₂，…，x_i）满足D中仅涉及到x₁，x₂，…，x_i的所有约束意味着j（j<i）元组（x₁，x₂，…，x_j）一定也满足D中仅涉及到x₁，x₂，…，x_j的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n-1，使得（x₁，x₂，…，x_j）违反D中仅涉及到x₁，x₂，…，x_j的约束之一，则以（x₁，x₂，…，x_j）为前缀的任何n元组（x₁，x₂，…，x_j，x_j+1，…，x_n）一定也违反D中仅涉及到x₁，x₂，…，x_i的一个约束，n≥i>j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x₁，x₂，…，x_j）违反D中仅涉及x₁，x₂，…，x_j的一个约束，就可以肯定，以（x₁，x₂，…，x_j）为前缀的任何n元组（x₁，x₂，…，x_j，x_j+1，…，x_n）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：

      设S_i中的元素可排成x_i⁽¹⁾，x_i⁽²⁾，…，x_i^(mi-1)，|S_i| =m_i，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有m_i个儿子。这m_i个儿子到它们的双亲的边，按从左到右的次序，分别带权x_i+1⁽¹⁾，x_i+1⁽²⁾，…，x_i+1^(mi)，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组（x₁，x₂，…，x_n）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x₁，x₂，…，x_n，反之亦然。另外，对于任意的0≤i≤n-1，E中n元组（x₁，x₂，…，x_n）的一个前缀I元组（x₁，x₂，…，x_i）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x₁，x₂，…，x_i，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。

      因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x₁，x₂，…，x_n满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x_1i）、前缀2元组（x₁，x₂）、…，前缀I元组（x₁，x₂，…，x_i），…，直到i=n为止。

      在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。