回溯策略的基本思想
回溯策略是暴力搜索法中的一种。对于某些约束满足问题，要求给出问题全部或最优解时，尤其适合使用回溯策略。
回溯策略的基本思想是试错法，它尝试分步地去解决一个问题。在解决问题的过程中，当回溯策略发现现有的分步答案不能给出有效的解答时，它将向上回溯，取消前一步甚至是前几步的计算结果，然后再通过其他可能的分步解答再次尝试寻找问题的答案。通俗地说，就是选定一条路往前走，直到“撞了南墙”再回头换一条别的路。
在反复重复上述步骤后，可能产生两种情况：回溯策略找到了一个有效的解答，或者是在检查了所有的分步情况后宣告该问题在所给约束条件下无解。
我们现在采用更为形式化的语言来描述回溯策略：我们将解决一个问题的分步过程抽象出来，将每一个可能产生的分步答案都视作一个节点，而两个分步答案之间的相互关系则用一条连接两个节点的边表示。现在我们获得了一棵树，这棵树中包含问题在给定约束条件下的全部解，我们将这棵树称作解空间树。现在我们从根节点开始搜索整棵解空间树，当算法遍历至任意一个节点时，先判断该节点是否包含了问题的解；如果不包含，则跳过对以该节点为根节点的子树的搜索，逐层向其祖先节点回溯，否则进入该子树继续依照此规则进行搜索。按照上面描述的检查这些分步答案的方法来遍历解空间树的过程称作深度优先遍历。算法正在检查的节点通常也正在产生子节点，此时该节点称作扩展节点。如果该节点的所有子节点尚未全部生成，则该节点称作活节点，否则称作死节点。深度优先遍历的过程即是扩展节点不断转移的过程。
回溯策略产生一个或多个元组(\(x_{1}, x_{2}, \cdots, x_{n-1}, x_{n}\))作为问题的解，称为解向量。问题的所有解向量构成了解空间。在对某个节点进行判断时，我们可能会涉及到两个判断条件：问题中给定的约束条件，也是对每个分量的取值限制（称作显约束）和为产生问题的有效解而在不同分量间施加的约束（称为隐约束）。
当我们使用回溯策略解决现有问题时，应遵循以下几个步骤：
- 定义解空间。
- 利用适于搜索的方法组织解空间（有些问题的表示方法可能有多种，采用合适的方法可以减少所需空间或是简化搜索过程）。
- 利用深度优先遍历解空间树。
- 利用约束函数和限界函数来避免移动到不可能产生解的子空间（剪枝）。
可以通过判断某个子树无法产生有效解的方式来避免对该子树的搜索，进而减少总搜索量；这一过程称作剪枝。在回溯策略中，剪枝函数分为两种：约束函数与限界函数。两者都在现有的扩展节点处进行判断。其中，约束函数减去不满足约束条件的子树，而限界函数减去不能得到最优解的子树（因此限界函数是可选的）。
用回溯策略解决现有问题的一个显著特征是问题的解空间在搜索过程中动态生成。在任何情况下，算法只保存从根节点到当前扩展节点的路径。最坏情况下，回溯策略通常面临指数或阶乘级别的时间复杂度。
回溯策略的基本结构
在使用回溯策略解决现有问题时，考虑到问题的实际要求不同，我们通常使用两种树形结构来构造算法：子集树和排列树。其中，子集树是指从含有n个元素的集合S中找出符合某种性质的子集所对应的解空间树，而排列树则是指确定n个元素满足某种性质的排列时所对应的解空间树。
子集树
设集合\(S={a_{1},a_{2},\cdots,a_{n-1},a_{n}}\)，且元素\(a_{i}\)对应状态集合\(J_{i}={j_{1},j_{2},\cdots,j_{k-1},j_{k}}\)，则将第\(i\)层节点\(E_{i}\)均代表元素\(a_{i}\)，且每个节点均向下一层延伸出\(|J_{i}|\)条边的解空间树称为子集树。
子集树实际上是从含有n个元素的集合S中选取符合某种性质的子集所构成的解空间树。
一般地，如果元素\(a_{i}\)对应状态集合中元素数目之最大值为\(K\)，则遍历子集树的时间复杂度为\(O(K^{N})\)。
遍历子集树的一般算法为：
void SubsetTree (int level) {
if(level > n){ // 已经搜索完子集树的最底层
--STATEMENT--;
} else {
// 遍历该层元素的所有状态
for(int status = 1; status <= k; status++){
// 数组statusList存储第level号元素的所处状态
statusList[level] = status;
// 如果约束函数和限界函数给出结果为真，向下一层继续遍历
if(Constraint(level) && Bound(level))
SubsetTree(level + 1);
// 当向上回溯时，将该层元素所处状态重置为0
statusList[level] = 0;
}
}
}
下面我们将给出三个使用子集树的例子，其中前两个例子只使用约束函数进行剪枝，而最后一个例子同时用到了约束函数和限界函数。
举例：八皇后问题
我们将用一个著名的数学问题作为介绍子集树的例子：八皇后问题。
八皇后问题是一个以国际象棋为背景的问题：在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后，并要求任两个皇后都不能处于同一条行、列、对角线上。
八皇后问题需要考虑皇后所在位置的四个因素：行、列、主对角线、副对角线。但我们可以先人为处理一个：将八个皇后事先就摆在不同的行上。现在我们要考虑皇后所处的列、主对角线、副对角线。
如果我们不要求皇后处于不同的对角线上，则我们只需要枚举皇后所处的列。此时我们只需要用一个大小为8的int数组来存储某一列上是否有皇后的信息。对每一行的皇后，枚举该数组的8个元素（代表8个列），如果枚举到的某个元素为0，则置其值为1，代表该列已经放上了一个皇后；反之则继续向后枚举。保证皇后处于不同的对角线上似乎有点麻烦，因为我们没有一个很好的办法来直接对对角线进行枚举。但是如果我们考虑将8×8的棋盘中每个格填充上该格所在的行和列的和，则我们可以得到这样一张图：
我们可以看到，图中的每条副对角线上的元素都被赋予了相同的值。这意味着我们可以用行+列的值来区分副对角线了。运用类似的方法，当我们将每个格子填充上行-列的值时，我们可以得到这样一张图：
现在我们可以用与处理列相似的方法来处理对角线了。副对角线有15条，我们可以用一个0~14的int数组来存储副对角线的信息。主对角线也有15条，但是它的标识数中出现了负数。因此我们需要做一个变换：代表每条主对角线的下标为行-列+7。这样我们就把下标由-7~7转换成了0~14。现在主对角线可以用与副对角线相同的方式存储了。
下面给出解决八皇后问题的C语言代码：
#include <stdio.h>
#define LEN 15
#define QUEEN_NUM 8
int queen[3][LEN]; // 存储八个皇后所在的列、副对角线、主对角线
int num; // 保存已经找到解的个数
void QueenSearch(int row);
int main(void) {
QueenSearch(0);
printf("The number of different solutions is %d\n", num);
return 0;
}
void QueenSearch(int row) {
if(row == QUEEN_NUM) // 已经找到八皇后问题的一个解
num++;
else {
// 每行代表一个皇后，皇后可能处于的8列代表每个皇后可能处于的8种状态
for(int col = 0; col < 8; col++){
// 判断是否在对应的列和对角线上都没有发现别的皇后
if( !queen[0][col] && !queen[1][row + col] && !queen[2][row - col + 7] ){
// 将皇后放置在这个位置
queen[0][col] = queen[1][row + col] = queen[2][row - col + 7] = 1;
QueenSearch(row + 1);
// 恢复到原有状态
queen[0][col] = queen[1][row + col] = queen[2][row - col + 7] = 0;
}
}
}
}
最终将给出八皇后问题的解是92个。
举例：图的\(m\)着色问题
给定无向连通图\(G=(V,E)\)和m种颜色，对每个顶点用这m种颜色之一着色，且相连顶点不可着同色。求着色方案总数。
输入数据：v, e < 100, m < 10, 分别代表图的顶点数目、图的边数目、图的颜色数目。之后输入e行数据，每行数据含两个整数，代表某条边连接的两个顶点。输出着色方案的总数。
#include <stdio.h>
#define EDGENUM 110
int graph[EDGENUM][EDGENUM]; // 邻接矩阵，存储图信息
int vertex[EDGENUM * 2]; // 存储每个顶点所着颜色
int v, e, m; // 图的顶点数、边数、颜色数
int num; // 存储方案总数
void ColorUp(int n);
// 判断某个顶点是否与其相邻顶点存在同色情况
int check(int n);
int main(void) {
scanf("%d %d %d", &v, &e, &m);
int v1 = 0, v2 = 0;
for(int i = 0; i < e; i++){
scanf("%d %d", &v1, &v2);
graph[v1][v2] = graph[v2][v1] = 1;
}
ColorUp(1);
printf("The way of coloring the graph is %d\n", num);
return 0;
}
void ColorUp(int n) {
if(n > v)
num++;
else {
for(int i = 1; i <= m; i++){
vertex[n] = i;
if(check(n))
ColorUp(n + 1);
vertex[n] = 0;
}
}
}
int check(int n) {
for(int i = 1; i <= v; i++){
if(i == n)
continue;
else {
if(graph[i][n] == 1 && vertex[i] == vertex[n])
return 0;
}
}
return 1;
}
举例：最优装载问题
有\(n\)个集装箱要装上两艘轮船\(s_{0},s_{1}\)，\(n\)个集装箱的重量分别为\(w_{0},w_{1},w_{2},\cdots,w_{n-2},w_{n-1}\)，两艘轮船的载重量则分别为\(c_{0},c_{1}\)，且满足\(\sum_{i=0}^{n-1}w_{i} \leq c_{0}+c_{1}\)。两艘船都被希望尽可能装满，但两艘船不能并行装载货物，只能两艘船轮流进行。请你设计一个合适的装载方案。
既然两艘船装载货物有先后顺序，那么必定只有先装载货物的船能够尽量将自己的船装满，而第二艘船只能装载剩余的集装箱。不妨设\(s_{0}\)总能先到先得，即现在问题转化为：从给定的\(n\)个集装箱内挑选某些集装箱装在\(s_{0}\)上并将它尽量装满。即：选取全体集装箱集合的一个子集，使子集中集装箱的总重最接近\(c_{0}\)。
我们可以很容易地给出这个问题的约束剪枝方案：如果\(s_{0}\)上已经装载的集装箱重量与即将装载的集装箱的重量和超过了\(c_{0}\)，那么这个方案就将被剪掉。但此问题的剪枝方案还可以进一步优化：本问题的解空间树是一棵二叉树，而上面的约束剪枝只剪去了这个节点的右子树（状态为被选中）。我们现在尝试对左子树（状态为未被选中）进行处理：如果\(s_{0}\)上现有的集装箱总重与所有尚未被装入的集装箱重量之和小于等于已知最优方案，则现有方案一定不是最优方案（或与已知最优方案重复），因此予以剪去。
下面给出装载问题的代码：
#include <stdio.h>
#define CONT_MAX_NUM 1000
// 存储每个集装箱的重量，存储剩余集装箱总重
int contWeight[CONT_MAX_NUM], allContNum;
// 存储目前s0上的放置方案，存储目前s0上集装箱总重，
// 存储目前s0上集装箱数目
int nowPlan[CONT_MAX_NUM], nowWeight, nowContNum;
// 存储目前最优方案，存储目前最优方案中s0上集装箱总重，
// 存储目前最优方案中s0上集装箱数目
int bestPlan[CONT_MAX_NUM], bestWeight, bestContNum;
int c0, c1, n;
void ContainerLoading(int index);
int main(void) {
printf("Please enter the value of c0, c1, and n.\n");
scanf("%d %d %d", &c0, &c1, &n);
printf("Please enter the weight of each container "
"(separated by space): \n");
for(int i = 0; i < n; i++){
scanf("%d", &contWeight[i]);
allContNum += contWeight[i];
}
ContainerLoading(0);
printf("The best plan is: \n");
printf("Load the container(s) with weight ");
for(int i = 0; i < bestContNum; i++)
printf("%d ", contWeight[bestPlan[i]]);
printf("on ship s0.\n");
printf("The rest part will be loaded on ship s1.\n");
return 0;
}
void ContainerLoading(int index) {
if(index == n){
if(nowWeight > bestWeight){
for(int i = 0; i < nowContNum; i++)
bestPlan[i] = nowPlan[i];
bestWeight = nowWeight;
bestContNum = nowContNum;
}
} else {
// 取出第index个集装箱
allContNum -= contWeight[index];
// 判断该集装箱能否装上s0
if(nowWeight + contWeight[index] <= c0){
nowPlan[nowContNum++] = index;
nowWeight += contWeight[index];
ContainerLoading(index + 1);
nowPlan[--nowContNum] = 0;
nowWeight -= contWeight[index];
}
// 将该集装箱装上s1，同时判断目前方案能否产生比当前更优方案
if(nowWeight + allContNum > bestWeight)
ContainerLoading(index + 1);
allContNum += contWeight[index];
}
}
排列树
设集合\(U={a_{1},a_{2},\cdots,a_{n-1},a_{n}}\)，则从一个代表\(U\)的根节点发出，除根节点外的每个节点代表\(U\)的一个子集\(N\)，且从每个节点向下一层延伸出的每条边都代表\(U-N\)中的一个元素，这样的解空间树称为排列树。
排列树实际上是选取含有n个元素的集合S符合某种性质的排列。
一般地，遍历排列树的时间复杂度为O(N!)。
遍历排列树的一般算法为：
void PermutationTree (int level) {
if(level > n){ // 已经搜索完排列树的最底层
--STATEMENTS--;
} else {
// 枚举可能与第level个元素交换位置的所有元素
//初始条件不要改为level + 1，会导致最后一个level无法进入循环
for(int status = level; status <= n; status++){
swap(list[status], list[level]);
if(Constraint(t) && Bound(t))
PermutationTree(level + 1);
// 恢复原有状态
swap(list[status], list[level]);
}
}
}
由此可见排列树是子集树的衍生产物，且已经经过剪枝（循环从index而不是从1开始）。
下面将给出2个使用排列树的例子。
举例：求1~N的全排列
#include <stdio.h>
#define LEN 1000
int numList[LEN]; // 存放1~N的某个排列
int N, perNum; // 存放N和已知的不同排列数目
void permulation(int index);
// 打印1~N的某个排列
void printPer(void);
void swap(int *num1, int *num2);
int main(void) {
scanf("%d", &N);
for(int i = 1; i <= N; i++)
numList[i] = i;
permulation(1);
printf("The number of all permulations is %d.\n", perNum);
return 0;
}
void permulation(int index) {
if(index > N){
printPer();
perNum++;
} else {
for(int i = index; i <= N; i++){
swap(&numList[i], &numList[index]);
permulation(index + 1);
swap(&numList[i], &numList[index]);
}
}
}
void printPer(void) {
for(int i = 1; i <= N; i++)
printf(i == N ? "%d\n" : "%d ", numList[i]);
}
void swap(int *num1, int *num2) {
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
}
举例：批处理作业调度问题
给定作业集合\(J_{n},n=1,2,\cdots,n-1,n\)，每项作业需要先后经机器0和机器1处理，第i项作业在机器j上的处理时间记作\(t_{ji}\)。你可以任意安排处理作业的调度顺序。试分别给出两个安排方案，解决以下两个需求：
- 给出一个作业安排方案使得处理完所有作业的耗时最小。
- 令\(F_{ji}\)为从0时刻开始到作业\(i\)在机器\(j\)上处理完毕后的总时间。给出一个作业安排方案使得\(F_{21}+F_{22}+\cdots+F_{2(n-1)}+F_{2n}\)最小。
样例输入 3 2 1 3 1 2 3 样例输出 (1) The best permulation of works is: 1 3 2 Which costs 8 time unit(s) in total. (2) The best permulation of works is: 1 3 2 Which costs 18 time unit(s) in total.
我们考虑样例：样例给出了三个作业，在机器0和机器1上的耗时分别为{2, 3, 2}和{1, 1, 3}。我们以实际输出的最优调度来说明两台机器的工作方式：
下面给出批处理调度问题的C语言代码：
需求1：
#include <stdio.h>
#define LEN 1000
// 作业总数，每项作业需要的机器0和机器1的处理时间
int workNum, time[2][LEN];
// 作业的某个调度方案
int workList[LEN];
// 机器0安排的作业顺序
int m0List[LEN];
// 机器1安排的作业顺序
int m1List[LEN];
int bestList[LEN], bestAllTime = 999999;
void swap(int *a, int *b);
int max(int *a, int *b);
void BatchJob(int index);
int main(void) {
printf("Please enter the number of works. \n");
scanf("%d", &workNum);
for(int i = 1; i <= workNum; i++)
workList[i] = i;
printf("Please enter time which each work costs"
"(time needed by two machines separated by space). \n");
for(int i = 1; i <= workNum; i++)
scanf("%d %d", &time[0][i], &time[1][i]);
BatchJob(1);
printf("The best permulation of works is: \n");
for(int i = 1; i <= workNum; i++)
printf(workNum == i ? "%d\n" :"%d ", bestList[i]);
printf("Which costs %d time unit(s) in total. \n", bestAllTime);
return 0;
}
inline void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
inline int max(int *a, int *b) {
return *a > *b ? *a : *b;
}
void BatchJob(int index) {
if(index > workNum){
if(m1List[index - 1] < bestAllTime){
for(int i = 1; i <= workNum; i++)
bestList[i] = workList[i];
bestAllTime = m1List[index - 1];
}
} else {
for(int i = index; i <= workNum; i++){
swap(&workList[index], &workList[i]);
m0List[index] = m0List[index - 1] + time[0][workList[index]];
// 结合实际过程理解此处的max
m1List[index] = max(&m0List[index], &m1List[index - 1]) + time[1][workList[index]];
if(m1List[index] < bestAllTime)
BatchJob(index + 1);
swap(&workList[index], &workList[i]);
m0List[index] = 0;
m1List[index] = 0;
}
}
}
需求2：
#include <stdio.h>
#define LEN 1000
// 作业总数，每项作业需要的机器0和机器1的处理时间
int workNum, time[2][LEN];
// 作业的某个调度方案
int workList[LEN];
// 机器0安排的作业顺序
int m0List[LEN];
// 机器1安排的作业顺序及当前的所有F_{2i}之和
int m1List[LEN], m1AllTime;
int bestList[LEN], bestAllTime = 999999;
void swap(int *a, int *b);
int max(int *a, int *b);
void BatchJob(int index);
int main(void) {
printf("Please enter the number of works. \n");
scanf("%d", &workNum);
for(int i = 1; i <= workNum; i++)
workList[i] = i;
printf("Please enter time which each work costs"
"(time needed by two machines separated by space). \n");
for(int i = 1; i <= workNum; i++)
scanf("%d %d", &time[0][i], &time[1][i]);
BatchJob(0);
printf("The best permulation of works is: \n");
for(int i = 1; i <= workNum; i++)
printf(workNum == i ? "%d\n" :"%d ", bestList[i]);
printf("Which costs %d time unit(s) in total. \n", bestAllTime);
return 0;
}
inline void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
inline int max(int *a, int *b) {
return *a > *b ? *a : *b;
}
void BatchJob(int index) {
if(index > workNum){
if(m1AllTime < bestAllTime){
for(int i = 1; i <= workNum; i++)
bestList[i] = workList[i];
bestAllTime = m1AllTime;
}
} else {
for(int i = index; i <= workNum; i++){
swap(&workList[index], &workList[i]);
m0List[index] = m0List[index - 1] + time[0][workList[index]];
m1List[index] = max(&m0List[index], &m1List[index - 1]) + time[1][workList[index]];
m1AllTime += m1List[index];
if(m1AllTime < bestAllTime)
BatchJob(index + 1);
swap(&workList[index], &workList[i]);
m0List[index] = 0;
m1AllTime -= m1List[index];
m1List[index] = 0;
}
}
}