回溯法的基本思想

在回溯法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解就通过在该集合中选择构造而成。这样的状态集合，其结构是一棵多叉树，每个树结点代表一个可能的部分解，它的儿子是在它的基础上生成的其他部分解。树根为初始状态，这样的状态集合称为状态空间树。

回溯法对任一解的生成，一般都采用逐步扩大解的方式。每前进一步，都试图在当前部分解的基础上扩大该部分解。它在问题的状态空间树中，从开始结点（根结点）出发，以深度优先搜索整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。

回溯法与穷举法有某些联系，它们都是基于试探的。穷举法要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。而对于回溯法，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。1

回溯法的算法框架问题的解空间应用回溯法求解问题时，首先应明确定义问题的解空间，该解空间应至少包含问题的一个最优解。例如，对于有n种物品的 0-1 背包问题，其解空间由长度为n的 0-1 向量组成，该解空间包含了对变量的所有可能的0-1 赋值。当 n=3 时，其解空间是{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) }

在定义了问题的解空间后，还需要将解空间有效地组织起来，使得回溯法能方便地搜索整个解空间，通常将解空间组织成树或图的形式。例如，对于n= 3的0-1 背包问题，其解空间可以用一棵完全二叉树表示，从树根到叶子结点的任意一条路径可表示解空间中的一个元素，如从根结点A到结点J的路径对应于解空间中的一个元素(1, 0, 1)。

回溯法解题的关键要素确定了问题的解空间结构后，回溯法将从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。开始结点成为活结点，同时也成为扩展结点。在当前的扩展结点处，向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处，并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

运用回溯法解题的关键要素有以下三点：

(1) 针对给定的问题，定义问题的解空间；

(2) 确定易于搜索的解空间结构；

(3) 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

递归和迭代回溯一般情况下可以用递归函数实现回溯法，递归函数模板如下：

void BackTrace(int t) {

if(t>n)

Output(x);

else

for(int i = f (n, t); i n时，算法已搜索到一个叶子结点，此时由函数Output(x)对得到的可行解x进行记录或输出处理。用 f(n, t)和 g(n, t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；h(i)表示在当前扩展结点处x[t] 的第i个可选值；函数 Constraint(t)和 Bound(t)分别表示当前扩展结点处的约束函数和限界函数。若函数 Constraint(t)的返回值为真，则表示当前扩展结点处x[1:t] 的取值满足问题的约束条件；否则不满足问题的约束条件。若函数Bound(t)的返回值为真，则表示在当前扩展结点处x[1:t] 的取值尚未使目标函数越界，还需由BackTrace(t+1)对其相应的子树做进一步地搜索；否则，在当前扩展结点处x[1:t]的取值已使目标函数越界，可剪去相应的子树。

采用迭代的方式也可实现回溯算法，迭代回溯算法的模板如下：

void IterativeBackTrace(void) {

int t = 1;

while(t>0) {

if(f(n, t)

来源: 百度百科