一、回溯法的基本思想

1. 回溯法有“通用解题方法”的美称，解题过程是一个搜索过程。在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。因此，回溯法是一种能避免不必要搜索的穷举式搜索法，通常可以用递归来实现。许多复杂的、规模较大的问题都可以使用回溯法。
2. 回溯法是一个既带有系统性又带有跳跃性的搜索算法。
3. 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

二、案例

2.1 四后问题（n后问题的一个实例）

**【问题描述】**在4 ×4 的方格棋盘上放置4个皇后，使得没有两个皇后在同一行、同一列、也不在同一条45度的斜线上（彼此不攻击）。问有多少种可能的布局？

4后问题的可行解是：{2,4,1,3}和{3,1,4,2}

搜索空间：4叉树（每个结点有4个儿子）

1. 每个结点的4个儿子分别代表选择1,2,3,4列位置
2. 第i层选择向量中第i个分量的值
3. 最深层的树叶就是解
4. 按深度优先次序遍历，找到所有解

下图是4问题的搜索空间，图中每个状态由当前放置的皇后的行列号构成。它给出了4后问题的全部搜索过程，只有18个结点，其中标有 x 号的结点无法继续扩展。

2.2 0-1背包问题

**【问题描述】**给定n种物品和一背包，每种物品只有1个且不能分割。物品i的重量是wi，其价值为vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大。

实例：V={12, 11, 9, 8}，W={8, 6, 4, 3}，C=13
最优解：{0, 1, 1, 1}，总价值28，总重量13

搜索空间：0-1取值的二叉树（称为子集树）
子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。

遍历子集树需O(2n)计算时间

2.3 旅行商问题

**【问题描述】**有n个城市，已知任意两个城市之间的距离，求一条每个城市恰好经过一次的回路，使得总长度最小。
搜索空间：排列树（有(n-1)!个叶子节点）
排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。

遍历排列树需要O(n!)计算时间

2.4 回溯法示例总结

问题的解：都是向量形式
搜索空间：树，可能是n叉树、子集树、排列树等，树的结点对应于部分向量，可行解在叶结点
搜索方法：深度优先，跳跃式遍历搜索树，找到可行解或最优解

适用：求解搜索问题和优化问题
搜索空间：树，结点对应部分解向量，可行解在树叶上
搜索过程：采用系统的方法隐含遍历搜索树
搜索策略：深度优先
结点分支判定条件：
满足约束条件，分支扩张解向量
不满足约束条件，回溯到该结点的父结点
结点状态：动态生成
存储：当前路径

三、回溯法中的概念

3.1 结点状态

扩展结点：一个正在产生儿子的结点称为扩展结点
活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点：一个所有儿子已经产生的结点称做死结点

深度优先访问次序：
1 -> 2 -> 3 -> 5 -> 8 -> 9 -> 7 -> 4

广度优先访问次序：
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

3.2 生成问题状态的基本方法

1. 深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）。
2. 广度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点

3.3 避免无效搜索的策略 剪枝函数

回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高搜索效率

1. 用约束函数在扩展结点处剪去不满足约束的子树
2. 用限界函数(bounding function)剪去得不到最优解的子树

约束函数和限界函数统称为剪枝函数。

为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法（与分支限界法相对应）。

3.4 回溯法解题通常包含以下3个步骤

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

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

四、 回溯法与深度优先遍历的异同

相同点：
回溯法在实现上也是遵循深度优先的，即一步一步往前探索。

不同点：

1. 访问序不同：深度优先遍历目的是“遍历”，本质是无序的。而回溯法目的是“求解过程”，本质是有序的。
2. 访问次数的不同：深度优先遍历对已经访问过的顶点不再访问，所有顶点仅访问一次。而回溯法中已经访问过的顶点可能再次访问。
3. 剪枝的不同：深度优先遍历不含剪枝，而很多回溯算法采用剪枝条件剪除不必要的分枝以提高效能。

五、示例

5.1 装载问题

**【问题描述】**有一批总重为W的共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 W ≤c1+c2。
要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。此问题等价于以下特殊的0-1背包问题。

回溯法求解伪代码：

void backtrack (int i)
{if (i > n) // 到达叶结点更新最优解bestx,bestw;return;r - = w[i];if (cw + w[i] <= c1) {// 搜索左子树x[i] = 1;cw + = w[i];backtrack(i + 1);cw - = w[i]; }if (cw + r > bestw) {x[i] = 0; // 搜索右子树backtrack(i + 1); }r += w[i];
}

5.2 符号三角形问题

下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。

在一般情况下，符号三角形的第一行有n个符号。
**【问题描述】**符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。

符号三角形问题相应的解空间是一棵完全二叉树

解向量：用n元组x[1:n]表示符号三角形的第一行，可用一棵完全二叉树表示其解空间。 当第1行前i个符号确定后，就确定了一个由n*(n+1)/2个符号组成的符号三角形。
可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4
无解的判断：n*(n+1)/2为奇数

回溯法求解伪码：

void backtrack (int t)
{if ((count>half)||(t*(t-1)/2-count>half)) return;if (t>n) sum++;else for (int i=0;i<2;i++) {p[1][t]=i;count+=i;for (int j=2;j<=t;j++) {p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}backtrack(t+1);for (int j=2;j<=t;j++) count-=p[j][t-j+1];count-=i;}
}

六、回溯法效率分析

通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以
下因素：
(1) 产生x[k]的时间；
(2) 满足显约束的x[k]值的个数；
(3) 计算约束函数constraint的时间；
(4) 计算界限函数bound的时间；
(5) 满足约束函数和界限函数约束的所有x[k]的个数。

好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折中。

七、重排原理

对于许多问题而言，在搜索试探时选取x[i]的值顺序是任意的。在其他条件相当的前提下，让可取值最少的x[i]优先。从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。

图（a）

图（b）

1. 图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。
2. 对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。
3. 前者的效果明显比后者好。

八、小结

(1) 适于求解组合搜索问题及优化问题
(2) 解的表示：解向量，求解是不断扩充解向量的过程
(3) 回溯条件：
搜索问题——约束条件
优化问题——约束条件+ 限界函数（代价函数）
(4) 分支策略：深度优先
(5) 结点状态：死结点、活结点、扩展结点
(6) 算法时间复杂度：
W(n) = ( p(n) f(n) )
其中p(n) 为每个结点的工作量， f(n)为结点个数

最坏情况下时间通常为指数级
平均情况下比蛮力算法好
空间代价小

降低时间复杂性的主要途径：

1. 根据树的分支设计优先策略
2. 结点少分支优先
3. 解多分支优先
4. 利用搜索树的对称性裁减子树
5. 分解为子问题，利用分治策略求解