学习要点

···理解回溯法的深度优先搜索策略

···掌握用回溯法解题的算法框架：

　　（1）递归回溯

　　（2）迭代回溯

　　（3）子集树算法框架

　　（4）排列数算法框架

···应用范例：

……

回溯法：

　　回溯法有“通用的解题法”之称。用它可以系统的搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适合于解组合数较大的问题。

问题的解空间树：　　

　　用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个（最优）解。

　　　　例如，对于有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背包问题，可用一颗完全的二叉树表示其解空间，如下图。

　　　　解空间树的第i层到第i+1层边上的标号给出了变量的值。从树根到叶子的任一路径表示解空间中的一个元素。例如，从根节点到节点H的路径相当与解空间中的元素(1,1,1)。

回溯法的基本思想：

　　确定了解空间的组织结构后，回溯法从根节点出发，以深度优先搜索方式搜索整个解空间。回溯法以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间所有解都被遍历过为止。
　　回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在当前节点（扩展节点）处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。

　　回溯法解题通常包含以下三个步骤：

　　　　 1.针对所给问题，定义问题的解空间；
　　　　2.确定易于搜索的解空间结构；
　　　　3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

递归回溯：

　　回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。一般函数结构如下：

 1 void Bcktrack(int t) //参数t表示当前递归深度
 2 {
 3     if(t>n)Output(x); //遍历到解，则将解输出或其他处理
 4     else
 5     {
 6         //f(n,t)和g(n,t)表示当前节点（扩展节点）处未搜索过的子树的起始编号和中指编号
 7         for(int i=f(n,t);i<=g(n,t);i++)    
 8         {
 9             x[t]=h(i);    //h(i)表示当前节点（扩展节点）处x[i]的第i个可选值
10             if(Constarint(t)&&Bound(t)) //剪枝函数：约束函数，限界函数
11                 Bcktrack(t+1);
12         }
13     }
14 }

迭代回溯：

　　采用树的非递归深度优先算法遍历算法，也可以将回溯法表示为一个非递归的迭代过程。一般函数形式如下：

 1 void IterativeBacktrack(void)
 2 {
 3     int t=1;    //t表示当前递归深度
 4     while(t>0)
 5     {
 6         if(f(n,t)<=g(n,t))
 7         {
 8             //f(n,t)和g(n,t)表示当前节点（扩展节点）处未搜索过的子树的起始编号和中指编号
 9             for(int i=f(n,t);i<=g(n,t);i++)
10             {
11                 x[t]=h(i);
12                 if(Constraint(t)&&Bound(t))    //剪枝函数：约束函数，限界函数
13                 {
14                     if(Solution(t)) Output(x);    //判断当前节点是否已经得到问题的可行解
15                     else t++
16                 }
17             }
18         }
19         else t--;
20     }
21 }

算法复杂度：

　　用回溯法解体的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根节点到当前节点（扩展节点）的路径。如果解空间树从根节点到叶节点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。

子集树：

　　当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树常有2^n个叶子结点，其结点总个数为2^(n+1)-1。遍历子集树的任何算法均需O(2^n)的计算时间。例如下图，n个物品的0-1背包问题所对应的解空间树就是一棵子集树。（分支相同的树状结构）

　　用回溯法搜索子集树的一般算法可描述如下：

1 void backtrack (int t)
2 {
3   if (t>n) output(x);
4     else
5       for (int i=0;i<=1;i++) {
6         x[t]=i;
7         if (constraint(t)&&bound(t)) backtrack(t+1);
8       }
9 }

排列树：

　　当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n！个叶结点。因此遍历排列树需要O(n!)的计算时间。例如下图，旅行售货员的问题的解空间树就是一棵排列树。（分支不同的树状结构）

　　用回溯法搜索排列树的算法框架可描述如下：(在调用backtrack(1)执行回溯搜索之前，先将变量数组x初始化为单位排列(1,2,3,...,n))

 1 void backtrack (int t)
 2 {
 3   if (t>n) output(x);   //x初始化为排列的其中一种
 4     else
 5       for (int i=t;i<=n;i++) {
 6         swap(x[t], x[i]);    //调换位置
 7         if (constraint(t)&&bound(t)) backtrack(t+1);
 8         swap(x[t], x[i]);    //调回原位
 9       }
10 }