第5章〓回溯法
回溯法采用类似穷举法的搜索尝试过程，在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时就“回溯”(即回退)，尝试其他路径，所以回溯法有“通用解题法”之称。本章介绍用回溯法求解问题的一般方法，并给出一些用回溯法求解的经典示例。本章的学习要点和学习目标如下：
(1) 掌握问题解空间的结构和深度优先搜索过程。
(2) 掌握回溯法的原理和算法框架。
(3) 掌握剪支函数(约束函数和限界函数)设计的一般方法。
(4) 掌握各种回溯法经典算法的设计过程和分析方法。
(5) 综合运用回溯法解决一些复杂的实际问题。
5.1回溯法概述
5.1.1问题的解空间
在3.1节讨论穷举法时简要介绍过解空间，由于解空间是回溯法等的核心概念，这里作进一步讨论。一个复杂问题的解决方案往往是由若干个小的决策(即选择)步骤组成的决策序列，所以一个问题的解可以表示成解向量x=(x0，x1，…，xn-1)，其中分量xi对应第i步的选择，通常可以有两个或者多个取值，表示为xi∈Si(0≤i≤n-1)，Si为xi的取值候选集，即Si=(vi,0，vi,1，…，vi,|Si|-1)。x中各个分量xi所有取值的组合构成问题的解向量空间，简称为解空间，解空间一般用树形式来组织，树中每个结点对应问题的某个状态，所以解空间也称为解空间树或者状态空间树。
解空间的一般结构如图5.1所示，根结点(为第0层)的每个分支对应分量x0的一个取值(或者说x0的一个决策)，若x0的候选集为S0={v0,1，…，v0,a}，即根结点的子树个数为|S0|，例如x0=v0,0时对应第1层的结点A0，x0=v0,1时对应第1层的结点A1，A2,…。对于第1层的每个结点Ai，Ai的每个分支对应分量x1的一个取值，若x1的取值候选集为S1={v1,0，…，v1,b}，Ai的分支数为|S1|，例如对于结点A0当x1=v1,0时对应第2层的结点B0，…。以此类推，最底层是叶子结点层，叶子结点的层次为n，解空间的高度为n+1。从中看出第i层的结点对应xi的各种选择，从根结点到每个叶子结点有一条路径，路径上每个分支对应一个分量的取值，这是理解解空间的关键。
图5.1解空间的一般结构
从形式化角度看，解空间是S0×S1×…×Sn-1的笛卡儿积，例如当|S0|=|S1|=…|Sn-1|=2时解空间是一棵高度为n+1的满二叉树。问题的解包含在解空间中，剩下的问题就是在解空间中搜索满足问题要求的解，回溯法就是这样的一种搜索方法，但不是唯一的搜索方法。
需要注意的是，问题的解空间是虚拟的，并不需要在算法运行中真正地构造出整个树结构，然后在该解空间中搜索问题的解。实际上，有些问题的解空间因过于复杂或结点过多难以画出来。
5.1.2什么是回溯法
先看一下求解问题的类型，通常求解问题分为两种类型，一种类型是给定一个约束函数，需要求所有满足约束条件的解，称为求所有解类型。例如鸡兔同笼问题中，所有鸡兔头数为a、腿数为b，求其中的鸡兔各有多少只？设鸡兔数分别为x和y，则约束函数是x+y=a，2x+4y=b，该问题需求的有解类型。另外一种类型是除了约束条件外还包含目标函数，最后是求使目标函数最大或者最小的最优解，称为求最优解类型。例如鸡兔同笼问题中，求所有鸡兔头数为a、腿数为b并且鸡最少的解，这就是一个求最优解问题，除了前面的约束函数外还包含目标函数min(x)。
这两类问题都可以采用回溯法求解，实际上它们本质上相同，因为只有求出所有解，再按目标函数进行比较才能求出最优解。
回溯法是在解空间树中按照深度优先搜索方法从根结点出发搜索解，与树的先根遍历类似，当搜索到某个叶子结点时对应一个可能解，如果同时又满足约束条件，则该可能解是一个可行解。所以一个可行解就是从根结点到对应叶子结点的路径上所有分支的取值，例如一个可行解为(a0，a1，…，an-1)，如图5.2所示，在解空间中搜索到可行解的部分称为搜索空间。简单地说，回溯法采用深度优先搜索方法寻找根结点到每个叶子结点的路径，判断对应的叶子结点是否满足约束条件，如果满足该路径就构成一个解(可行解)。
回溯法在搜索解时首先让根结点成为活结点，所谓活结点是指自身已生成但其孩子结点没有全部生成的结点，同时也成为当前的扩展结点，所谓扩展结点是指正在产生孩子结点的结点。在当前扩展结点处沿着纵深方向移至一个新结点，这个新结点又成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点，所谓死结点是指其所有子结点均已产生的结点，此时应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。也就是说在回溯法中从根结点开始沿着某个分支一直搜索下去，到达叶子结点后再退回搜索，直到没有活结点为止。
如图5.3所示，当从状态si搜索到状态si+1后，如果si+1变为死结点，则从状态si+1回退到si，再从si找其他可能的路径，所以回溯法体现出走不通就退回再走的思路。若用回溯法求问题的所有解，需要回溯到根结点，且根结点的所有可行的子树都已被搜索完才结束。若使用回溯法求任意一个解，只要搜索到问题的一个解就可以结束。
图5.2求解的搜索空间
图5.3回溯过程
从上看出，寻找问题解的过程就是在解空间中搜索满足约束条件和目标函数的解，所以搜索算法设计的关键点有以下3个：
① 根据问题的特性确定结点是如何扩展的，不同的问题扩展方式是不同的。例如，在有向图中搜索从顶点s到顶点t的一条路径，其扩展十分简单，就是从一个顶点找所有相邻顶点。
② 在解空间中按什么方式搜索解，实际上树的遍历主要有先根遍历和层次遍历，前者就是深度优先搜索(DFS)，后者就是广度优先搜索(BFS)。回溯法就是采用深度优先搜索解，第6章介绍的分支限界法则是采用广度优先搜索解。
③ 解空间通常十分庞大，如果要高效地找到问题的解，通常采用一些剪支的方法实现。
所谓剪支就是在解空间中搜索时提早终止某些分支的无效搜索，减少搜索的结点个数，但不影响最终结果，从而提高了算法的时间性能。常用的剪支策略如下。
① 可行性剪支： 在扩展结点处剪去不满足约束条件的分支。例如，在鸡兔同笼问题中，若a=3，b=8，兔数的取值范围只能是0～2，因为3只或者更多只兔子时腿数就超过8了，不再满足约束条件。
② 最优性剪支： 用限界函数剪去得不到最优解的分支。例如，在求鸡最少的鸡兔同笼问题中，若已经求出一个可行解的鸡数为3，后面就不必搜索鸡数大于3的结点。
③ 交换搜索顺序： 在搜索中改变搜索的顺序，比如原先是递减顺序，可以改为递增顺序，或者原先是无序，可以改为有序，这样可能减少搜索的总结点。
严格来说交换搜索顺序并不是一种剪支策略，而是一种对搜索方式的优化。前两种剪支策略采用的约束函数和限界函数统称为剪支函数。归纳起来，回溯法可以简单地理解为深度优先搜索加上剪支。因此用回溯法求解的一般步骤如下：
① 针对给定的问题确定其解空间，其中一定包含所求问题的解。
② 确定结点的扩展规则。
③ 采用深度优先搜索方法搜索解空间，并在搜索过程中尽可能采用剪支函数避免无效搜索。
【例51】农夫(人)过河问题是这样的，在河东岸有一个农夫、一只狼、一只鸡和一袋谷子，只有当农夫在现场时狼不会吃鸡，鸡也不会吃谷子，否则会出现狼吃鸡或者鸡吃谷子的冲突。另有一条小船，该船只能由农夫操作，且最多只能载下农夫和另一样东西。设计一种将农夫、狼、鸡和谷子借助小船运到河西岸的过河方案。
解在该问题中用东、西两岸的人或物品表示状态，开始状态为人和物品在东岸，西岸是空的，此时人可以带任何一个物品驾船到西岸去，这样扩展出3个状态，对于每种状态，又根据题目规则扩展出一个或多个状态，所有状态及其关系构成了本问题的解空间。
该问题的部分搜索空间如图5.4所示，图中每个方框表示一种状态，带阴影的框表示终点，带的框表示有冲突，即出现狼吃鸡或鸡吃谷子的情况，带×的框表示与以前的状态重复。在解空间中采用深度优先搜索找到的一种可行的方案(可行解)如下：
图5.4农夫过河的部分搜索空间
① 农夫驾船带鸡从河东岸到西岸。
② 农夫驾船不带任何东西从河西岸到东岸。
③ 农夫驾船带狼从河东岸到西岸。
④ 农夫驾船带鸡从河西岸到东岸。
⑤ 农夫驾船带谷子从河东岸到西岸。
⑥ 农夫驾船不带任何东西从河西岸到东岸。
⑦ 农夫驾船带鸡从河东岸到西岸。
5.1.3回溯法算法的框架
通常解空间有两种类型。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树，在子集树中每个结点的扩展方式是相同的，也就是说每个结点的子结点个数相同。例如在整数数组a中求和为目标值target的所有解，每个元素a［i］只有选择和不选择两种方式，对应的解空间就是子集树。当所给的问题是确定n个元素满足某种性质的排列时相应的解空间树称为排列树，例如求全排列问题的解空间就是典型的排列树。
由于回溯法基于深度优先搜索，而深度优先搜索特别适合采用递归实现，在递归算法中参数(非引用参数)具有自动回退(回溯)的能力，所以大多数回溯算法都采用递归实现(回溯算法也可以采用迭代实现，但递归回溯算法比对应的迭代算法设计起来更加简便)。
设问题的解是一个n维向量(x1，x2，…，xn)，约束函数为constraint(i，j)，限界函数为bound(i，j)。根据解空间类型将递归框架分为子集树和排列树两种类型。
1. 解空间为子集树
一般地，解空间为子集树的递归回溯框架如下：
int x［n］; //x存放解向量，这里作为全局变量
void dfs(int i) //求解子集树的递归框架
{if(i>n)//搜索到叶子结点,输出一个可行解
输出一个解;
else
{for (j=下界;j<=上界;j++) //用j表示x［i］的所有可能候选值
{x［i］=j; //产生一个可能的解分量
…//其他操作
if (constraint(i,j) && bound(i,j))
dfs(i+1); //满足约束条件和限界函数,继续下一层
回溯x［i］;
…
}
}
}
在采用上述算法框架时有以下几点注意事项：
① 如果i从1开始调用上述递归框架，此时根结点为第1层，叶子结点为第n+1层。当然i也可以从0开始，这样根结点为第0层，叶子结点为第n层，所以需要将上述代码中的“if (i>n)”改为“if(i>=n)”。
② 在上述递归框架中通过for循环用j枚举xi的所有可能候选值，如果扩展路径只有两条，可以改为两次递归调用(例如求解0/1背包问题、子集和问题等都是如此)。
③ 这里递归框架只有i一个参数，在实际应用中可以根据具体情况设置多个参数。
扫一扫
视频讲解
【例52】有一个含n个整数的数组a，所有元素均不相同，设计一个算法求其所有子集(幂集)。例如，a={1，2，3}，所有子集是{}，{3}，{2}，{2，3}，{1}，{1，3}，{1，2}，{1，2，3}(输出顺序无关)。
解本问题的解空间是典型的子集树，集合a中的每个元素只有两种选择，要么选取，要么不选取。设解向量为x，x［i］=1表示选取a［i］，x［i］=0表示不选取a［i］。用i遍历数组a，i从0开始(与解空间中根结点层次为0相对应)，根结点为初始状态(i=0，x的元素均为0)，叶子结点为目标状态(i=n，x为一个可行解，即一个子集)。从状态(i，x)可以扩展出两个状态：
① 选择a［i］元素下一个状态为(i+1，x［i］=1)。
② 不选择a［i］元素下一个状态为(i+1，x［i］=0)。
这里i总是递增的，所以不会出现状态重复的情况。如图5.5所示为求{1，2，3}幂集的解空间，每个叶子结点对应一个子集，所有子集构成幂集。
对应的递归回溯算法如下：
vector<int> x;//解向量,全局变量
void disp(vector<int>&a)//输出一个解
{printf(" {");
for (int i=0;i<x.size();i++)
if (x［i］==1)
printf("%d",a［i］);
printf("}");
}
void dfs(vector<int>&a,int i) //递归回溯算法
{if (i>=a.size()) //到达一个叶子结点
disp(a);
else //没有到达叶子结点
{x［i］=1;
dfs(a,i+1); //选择a［i］
x［i］=0;
dfs(a,i+1); //不选择a［i］
}
}
void subsets(vector<int>&a) //求a的幂集
{int n=a.size();
x.resize(n);//初始化x的长度为n
dfs(a,0);
}
图5.5求a={1，2，3}幂集的解空间
扫一扫
视频讲解
【例53】设计一个算法在1，2，3，4，5(顺序不能变)任意两个数字之间插入'+'或者'-'运算符，使得表达式的计算结果为5，并输出所有可能的表达式。
解用数组a［0..N-1］(N=5)存放1～5的整数，用字符数组x存放插入的运算符(解向量)，其中x［i］表示在a［i］前面插入的运算符(i从1开始)，x［i］只能取值'+'或者'-'(两选一)。采用回溯法产生和为5的表达式，解空间的高度是N+1，根结点的层次为0。
设计函数dfs(a，sum，x，i)，其中sum表示到达整数a［i］时计算出的表达式和(初始时置sum=a［0］)，i从1(因为a［0］之前没有运算符)开始，当到达叶子结点(i=N)时，如果sum=5，得到一个解。对应的递归算法如下：
#define N 5
void dfs(vector<int>&a,int sum,vector<char> &x,int i)
{if (i==N)//到达一个叶子结点(可能解)
{if (sum==5) //找到一个可行解
{printf(" %d",a［0］); //输出一个解
for (int j=1;j<N;j++)
{printf("%c",x［j］);
printf("%d",a［j］);
}
printf("=5＼n");
}
}
else
{x［i］='+';//在位置i插入'+'
sum+=a［i］; //计算结果
dfs(a,sum,x,i+1); //继续搜索
sum-=a［i］; //回溯
x［i］='-';//在位置i插入'-'
sum-=a［i］; //计算结果
dfs(a,sum,x,i+1); //继续搜索
sum+=a［i］; //回溯
}
}
void solve(vector<int>&a)//求解算法
{vector<char> x(a.size());//定义解向量
dfs(a,a［0］,x,1);
}
上述算法的求解结果如下：
1+2+3+4-5=5
1-2-3+4+5=5
说明： 上述算法与例52的算法相比，将解向量设计为dfs的引用参数而不是全局变量，实际上由于算法中包含x的回溯，所以设计为引用参数或者全局变量都是正确的。
2. 解空间为排列树
解空间为排列树的递归框架是以求全排列为基础的，下面先通过一个示例讨论一种不同于第3章求全排列的递归算法。
扫一扫
视频讲解
【例54】有一个含n个整数的数组a，所有元素均不相同，求其所有元素的全排列。例如，a={1，2，3}，得到的结果是(1，2，3)，(1，3，2)，(2，3，1)，(2，1，3)，(3，1，2)，(3，2，1)。
解用数组a存放初始数组a的一个排列，采用递归法求解。设f(a，n，i)表示求a［i..n-1］(共n-i个元素)的全排列，为大问题，f(a，n，i+1)表示求a［i+1..n-1］(共n-i-1个元素)的全排列，为小问题，如图5.6所示。
显然i越小求全排列的元素个数越多，当i=0时求a［0..n-1］的全排列。当i=n-1时求a［n-1..n-1］的全排列，此时序列只有一个元素(单个元素的全排序就是该元素)，再合并a［0..n-2］(n-1个元素的排列)就得到n个元素的一个排列。当i=n时求a［n..n-1］的全排列，此时序列为空，说明a［0..n-1］是一个排列，后面两种情况均可以作为递归出口。所以求a中全排列的过程是f(a，n，0)→f(a，n，1)→f(a，n，2)→…→f(a，n，n-1)。
那么如何由小问题f(a，n，i+1)求大问题f(a，n，i)呢？假设f(a，n，i+1)求出了a［i+1..n-1］的全排列，考虑ai位置，该位置可以取a［i..n-1］中的任何一个元素，但是排列中元素不能重复，为此采用交换方式，即j=i到n-1循环，每次循环将a［i］与a［j］交换，合并子问题解得到一个大问题的排列，再恢复成循环之前的顺序，即将a［i］与a［j］再次交换，然后进入下一次求其他大问题的排列。注意，如果不做再次交换会出现重复的排列情况，例如a={1，2，3}，结果为(1，2，3)，(1，3，2)，(3，1，2)，(3，2，1)，(1，2，3)，(1，3，2)，显然是错误的。
归纳起来，求a的全排列的递归模型f(a，n，i)如下：
f(a，n，i) ≡ 输出产生的解 当i=n-1时
f(a，n，i) ≡ 对于j=i～n-1： 其他
a［i］与a［j］交换位置;
f(a，n，i+1);
将a［i］与a［j］交换位置(回溯)
图5.6求f(a，n，i)的过程
例如a={1，2，3}时，求全排列的解空间如图5.7所示，数组a的下标从0开始，所以根结点“a={1，2，3}”的层次为0，它的子树分别对应a［0］位置选择a［0］、a［1］和a［2］元素。实际上对于第i层的结点，其子树分别对应a［i］位置选择a［i］、a［i+1］、……、a［n-1］元素。树的高度为n+1，叶子结点的层次是n。
图5.7求a={1，2，3}全排列的解空间(1)
解空间树更清晰的描述如图5.8所示，对于第i层的结点，其扩展仅考虑a［i］及后面的元素，而不必考虑前面已经选择的元素。例如第2层的“1，3，2”结点，前面的“1，3”不必考虑，仅扩展a［2］，此时a［2］只能取从根结点到该结点的路径上没有取过的值2，从而得到“1，3，2”的一个排序。
对应的递归算法如下：
int cnt=0; //累计排列的个数
void disp(vector<int>&a) //输出一个解
{printf(" %2d: (",++cnt);
for (int i=0;i<a.size()-1;i++)
printf("%d,",a［i］);
printf("%d)",a.back());
printf("＼n");
}
void dfs(vector<int>& a,int i)//递归算法
{int n=a.size();
if (i>=n-1) //递归出口
disp(a);
else
{for (int j=i;j<n;j++)
{swap(a［i］,a［j］); //交换a［i］与a［j］
dfs(a,i+1);
swap(a［i］,a［j］); //交换a［i］与a［j］：恢复
}
}
}
void perm(vector<int>& a) //求a的全排列
{
dfs(a,0);
}
图5.8求a={1，2，3}全排列的解空间(2)
现在证明算法的正确性。实际上在递归算法中求值顺序与递推顺序相反，求a的全排列是从f(a，n，0)开始的，求值顺序是f(a，n，n-1)→f(a，n，n-2)→…→f(a，n，1)→f(a，n，0)。循环不变量是f(a，n，i)用于求a［i..n-1］的全排列，证明如下。
初始化： 在循环的第一轮迭代开始之前，即i=n-1表示求a［n-1..n-1］的全排列，而一个元素的全排列就是该元素，显然是正确的。
保持： 若前面f(a，n，i+1)正确，表示求出了a［i+1..n-1］的全排列，将a［i］与a［i..n-1］中的每个元素交换，合并a［i+1..n-1］的一个排列得到f(a，n，i)的一个排列，再恢复后继续做完，从而得到f(a，n，i)的全排列。
终止： 当求值结束时i=0，得到f(a，n，0)即a的全排列。
从上述求a的全排列的示例可以归纳出解空间为排列树的递归回溯框架如下：
int x［n］; //x存放解向量，并初始化
void dfs(int i) //求解排列树的递归框架
{if(i>n)//搜索到叶子结点,输出一个可行解
输出结果;
else
{for (j=i;j<=n;j++)//用j枚举x［i］的所有可能候选值
{…//第i层的结点选择x［j］的操作
swap(x［i］,x［j］);//为保证排列中每个元素不同,通过交换来实现
if (constraint(i,j) && bound(i,j))
dfs(i+1); //满足约束条件和限界函数，进入下一层
swap(x［i］,x［j］);//恢复状态： 回溯
…//第i层的结点选择x［j］的恢复操作
}
}
}
如何进一步理解上述算法呢？假设解向量为(x0，x1，…，xi，…，xj，…，xn-1)，当从解空间的根结点出发搜索到达第i层的某个结点时，对应的部分解向量为(x0，x1，…，xi-1)，其中每个分量已经取好值了，现在为该结点的分支选择一个xi值(每个不同的取值对应一个分支，xi有n-i个分支)，前一个swap(x［i］,x［j］)表示为xi取xj值，后一个swap(x［i］,x［j］)用于状态恢复，这一点是利用排列树的递归回溯框架求解实际问题的关键。另外几点需要注意的说明事项与解空间为子集树的递归回溯框架相同。
5.1.4回溯法算法的时间分析
通常以回溯法的解空间中的结点个数作为算法的时间分析依据。假设解空间树共有n+1层(根结点为第0层，叶子结点为第n层)，第1层有m0个结点，每个结点有m1个子结点，则第2层有m0m1个结点，同理，第3层有m0m1m2个结点，以此类推，第n层有m0m1…mn-1个结点，则采用回溯法求所有解的算法的执行时间为T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。例如，在子集树中有m0=m1=…=mn-1=c，对应算法的时间复杂度为O(cn)，在排列树中有m0=n，m1=n-1，…，mn-1=1，对应算法的时间复杂度为O(n!)。
这是一种最坏情况下的时间分析方法，在实际中可以通过剪支提高性能。为了估算得更精确，可以选取若干条不同的随机路径，分别对各随机路径估算结点总数，然后再取这些结点总数的平均值。在通常情况下，回溯法的效率高于穷举法。
5.2基于子集树框架的问题求解
扫一扫
视频讲解
5.2.1子集和问题
1. 问题描述
给定n个不同的正整数集合a=(a0，a1，…，an-1)和一个正整数t，要求找出a的子集s，使该子集中所有元素的和为t。例如，当n=4时，a=(3，1，5，2)，t=8，则满足要求的子集s为(3，5)和(1，5，2)。
2. 问题求解
与求幂集问题一样，该问题的解空间是一棵子集树(因为每个整数要么选择要么不选择)，并且是求满足约束函数的所有解。
1) 无剪支
设解向量x=(x0，x1，…，xn-1)，xi=1表示选择ai元素，xi=1表示不选择ai元素。在解空间中按深度优先方式搜索所有结点，并用cs累计当前结点之前已经选择的所有整数和，一旦到达叶子结点(即i≥n)，表示a的所有元素处理完毕，如果相应的子集和为t(即约束函数cs=t成立)，则根据解向量x输出一个解。当解空间搜索完后便得到所有解。
例如a=(3，1，5，2)，t=8，其解空间如图5.9所示，图中结点上的数字表示cs，利用深度优先搜索得到两个解，解向量分别是(1，0，1，0)和(0，1，1，1)，对应图中两个带阴影的叶子结点，图中共有31个结点，每个结点都要搜索。实际上，解空间是一棵高度为5的满二叉树，从根结点到每个叶子结点都有一条路径，每条路径就是一个决策向量，满足约束函数的决策向量就是一个解向量。
图5.9求a=(3，1，5，2)，t=8的子集和的解空间
对应的递归算法如下：
int n=4,t=8; //一个测试实例
vector<int> a={3,1,5,2}; //存放所有整数
int cnt=0; //累计解个数
void disp(vector<int>&x) //输出一个解
{printf(" 第%d个解 ",++cnt);
printf("选取的数为");
for (int i=0;i<n;i++)
if (x［i］==1)
printf("%d ",a［i］);
printf("＼n");
}
void dfs(int cs,vector<int>&x,int i) //递归算法
{if (i>=n) //到达一个叶子结点
{if (cs==t) //找到一个满足条件的解,输出
disp(x);
}
else //没有到达叶子结点
{x［i］=1; //选取整数a［i］
dfs(cs+a［i］,x,i+1);
x［i］=0; //不选取整数a［i］
dfs(cs,x,i+1);
}
}
void subs1() //求解子集和问题
{vector<int> x(n); //定义解向量
dfs(0,x,0); //i从0开始
}
上述算法的求解结果如下：
第1个解选取的数为3 5
第2个解选取的数为1 5 2
【算法分析】上述算法的解空间是一棵高度为n+1的满二叉树，共有2n+1-1个结点，递归调用2n+1-1次，每找到一个满足条件的解就调用disp()输出，执行disp()的时间为O(n)，所以算法的时间复杂度为O(n×2n)。
2) 左剪支
由于a中所有元素是正整数，每次选择一个元素时cs都会变大，当cs＞t时沿着该路径继续找下去一定不可能得到解。利用这个特点减少搜索的结点个数。当搜索到第i(0≤i＜n)层的某个结点时，cs表示当前已经选取的整数和(其中不包含a［i］)，判断选择a［i］是否合适：
① 若cs+a［i］＞t，表示选择a［i］后子集和超过t，不必继续沿着该路径求解，终止该路径的搜索，也就是左剪支。
② 若cs+a［i］≤t，沿着该路径继续下去可能会找到解，不能终止。
简单地说，仅扩展满足cs+a［i］≤t的左孩子结点。
例如a=(3，1，5，2)，t=8，其搜索空间如图5.10所示，图5.10中共有29个结点，除去两个被剪支的结点(用虚框结点表示)，剩下27个结点，也就是说递归调用27次，性能得到了提高。
图5.10求a=(3，1，5，2)，t=8的子集和的搜索空间(1)
对应的递归算法如下：
void dfs(int cs,vector<int>&x,int i) //递归算法
{if (i>=n) //找到一个叶子结点
{if (cs==t) //找到一个满足条件的解,输出
disp(x);
}
else //没有到达叶子结点
{if (cs+a［i］<=t) //左孩子结点剪支
{x［i］=1; //选取整数a［i］
dfs(cs+a［i］,x,i+1);
}
x［i］=0; //不选取整数a［i］
dfs(cs,x,i+1);
}
}
void subs2() //求解子集和问题
{vector<int> x(n); //定义解向量
dfs(0,x,0); //i从0开始
}
3) 右剪支
左剪支仅考虑是否扩展左孩子结点，可以进一步考虑是否扩展右孩子结点。当搜索到第i(0≤i＜n)层的某个结点时，用rs表示余下的整数和，即rs=a［i］+…+a［n-1］(其中包含a［i］)，因为右孩子结点对应不选择整数a［i］的情况，如果不选择a［i］，此时剩余的所有整数和为rs=rs-a［i］(a［i+1］+…+a［n-1］)，若cs+rs＜t成立，说明即便选择所有剩余整数，其和都不可能达到t，所以右剪支就是仅扩展满足cs+rs≥t的右孩子结点，注意在左、右分支处理完后需要恢复rs，即执行rs=+a［i］。
例如a=(3，1，5，2)，t=8，其搜索过程如图5.11所示，图中共有17个结点，除去7个被剪支的结点(用虚框结点表示)，剩下10个结点，也就是说递归调用10次，性能得到更有效的提高。
说明： 本例给定a中所有整数为正整数，如果a中有负整数，这样的左、右剪支是不成立的，因此无法剪支，算法退化为基本深度优先搜索。
图5.11求a=(3，1，5，2)，t=8的子集和的搜索空间(2)
求解子集和问题的递归算法如下：
void dfs(int cs,int rs,vector<int>&x,int i)//递归算法
{//cs为考虑整数a［i］时选取的整数和，rs为剩余整数和
if (i>=n) //找到一个叶子结点
{if (cs==t) //找到一个满足条件的解，输出
disp(x);
}
else //没有到达叶子结点
{rs-=a［i］; //求剩余的整数和
if (cs+a［i］<=t) //左孩子结点剪支
{x［i］=1; //选取第i个整数a［i］
dfs(cs+a［i］,rs,x,i+1);
}
if (cs+rs>=t) //右孩子结点剪支
{x［i］=0; //不选取第i个整数a［i］
dfs(cs,rs,x,i+1);
}
rs+=a［i］; //恢复剩余整数和(回溯)
}
}
void subs3() //求解子集和问题
{vector<int> x(n); //解向量
int rs=0; //表示所有整数和
for (int j=0;j<n;j++)//求rs
rs+=a［j］;
dfs(0,rs,x,0); //i从0开始
}
【算法分析】尽管通过剪支提高了算法的性能，但究竟剪去了多少结点与具体的实例数据相关，所以说上述算法最坏情况下的时间复杂度仍然为O(n×2n)。从上述实例中可以看出剪支在回溯算法中的重要性。
5.2.2简单装载问题
1. 问题描述
扫一扫
视频讲解
有n个集装箱要装上一艘载重量为t的轮船，其中集装箱i(0≤i≤n-1)的重量为wi。不考虑集装箱的体积限制，现要选出重量和小于或等于t并且尽可能重的若干集装箱装上轮船。例如，n=5，t=10，w={5，2，6，4，3}时，其最佳装载方案有两种，即(1，1，0，0，1)和(0，0，1，1，0)，对应集装箱重量和达到最大值t。
2. 问题求解
同样与求幂集问题一样，该问题的解空间树是一棵子集树(因为每个集装箱要么选择要么不选择)，但要求最佳装载方案，属于求最优解类型。设当前解向量x=(x0，x1，…，xn-1)，xi=1表示选择集装箱i，xi=1表示不选择集装箱i，最优解向量用bestx表示，最优重量和用bestw表示(初始为0)，为了简洁，将bestx和bestw设计为全局变量。
当搜索到第i(0≤i＜n)层的某个结点时，cw表示当前选择的集装箱的重量和(其中不包含w［i］)，rw表示余下集装箱的重量和，即rw=w［i］+…+w［n-1］(其中包含w［i］)，此时处理集装箱i，先从rw中减去w［i］，即置rw-=w［i］，采用的剪支函数如下。
① 左剪支： 判断选择集装箱i是否合适。检查当前集装箱被选中后总重量是否超过t，若是则剪支，即仅扩展满足cw+w［i］≤t的左孩子结点。
② 右剪支： 判断不选择集装箱i是否合适。如果不选择集装箱i，此时剩余的所有整数和为rw，若cw+rw≤bestw成立(bestw是当前找到的最优解的重量和)，说明即便选择所有剩余集装箱，其重量和都不可能达到bestw，所以仅扩展满足cw+rw＞bestw的右孩子结点。
说明： 由于深度优先搜索是纵向搜索的，可以比广度优先搜索更快地找到一个解，以此作为bestw进行右剪支是非常合适的。
当第i层的这个结点扩展完成后需要恢复rs，即置rs+=a［i］(回溯)。如果搜索到某个叶子结点(即i≥n)，得到一个可行解，其选择的集装箱重量和为cw(由于左剪支的原因，cw一定小于或等于t)，若cw＞bestw，说明找到一个满足条件的更优解，置bestw=cw，bestx=x。全部搜索完毕后，bestx就是最优解向量。
对应的递归算法如下：
int n=5,t=10; //一个测试用例
int w［］={5,2,6,4,3}; //各集装箱重量，不用下标为0的元素
vector<int> bestx; //存放最优解向量
int bestw=0; //存放最优解的总重量，初始化为0
void dfs(int cw,int rw,vector<int>&x,int i) //递归算法
{if (i>=n) //找到一个叶子结点
{if (cw>bestw) //找到一个满足条件的更优解
{bestw=cw; //保存更优解
bestx=x;
}
}
else //没有到达叶子结点
{rw-=w［i］; //求剩余集装箱的重量和
if (cw+w［i］<=t)//左孩子结点剪支
{x［i］=1; //选取集装箱i
cw+=w［i］; //累计当前所选集装箱的重量和
dfs(cw,rw,x,i+1);
cw-=w［i］; //恢复当前所选集装箱的重量和(回溯)
}
if (cw+rw>bestw) //右孩子结点剪支
{x［i］=0; //不选择集装箱i
dfs(cw,rw,x,i+1);
}
rw+=w［i］; //恢复剩余集装箱的重量和(回溯)
}
}
void disp() //输出最优解
{for (int i=0;i<n;i++)
if (bestx［i］==1)
printf(" 选取第%d个集装箱＼n",i);
printf(" 总重量=%d＼n",bestw);
}
void loading() //求解简单装载问题
{bestx.resize(n);
vector<int> x(n);
int rw=0;
for (int i=0;i<n;i++)
rw+=w［i］;
dfs(0,rw,x,0);
}
上述算法的求解结果如下。实际上还有另外一个最优解，即选择第2个和第3个集装箱，它们的重量和是相同的。
选取第0个集装箱
选取第1个集装箱
选取第4个集装箱
总重量=10
说明： 在上述dfs算法的左结点扩展中，cw+=w［i］、dfs(cw,rw,x,i+1)和cw-=w［i］3条语句可以用一条语句(即dfs(cw+w［i］,rw,x,i+1))等价地替换。
【算法分析】该算法的解空间树中有2n+1-1个结点，每找到一个更优解时复制到bestx的时间为O(n)，所以最坏情况下算法的时间复杂度为O(n×2n)。前面的实例中，n=5，解空间树中结点个数应为63，采用剪支后结点个数为16（不计带×的被剪支的结点），如图5.12所示。
图5.12装载实例的搜索空间
扫一扫
视频讲解
5.2.30/1背包问题
1. 问题描述
有n个编号为0～n-1的物品，重量为w={w0，w1，…，wn-1}，价值为v={v0，v1，…，vn-1}，给定一个容量为W的背包。从这些物品中选取全部或者部分物品装入该背包中，每个物品要么选中要么不选中，即物品不能被分割，找到选中物品不仅能够放到背包中而且价值最大的方案，并对表5.1所示的4个物品求出W=6时的一个最优解。
表5.14个物品的信息
物品编号重量价值物品编号重量价值
054223
134311
2. 问题求解
该问题的解空间树是一棵子集树(因为每个物品要么选择要么不选择)，要求求价值最大的装入方案，属于求最优解类型。
1) 存储结构设计
每个物品包含编号、重量和价值，为此采用结构体数组存放所有物品，后面涉及按单位重量价值递减排序，所以设计物品结构体类型如下：
struct Goods //物品结构体类型
{int no; //物品的编号
int w; //物品的重量
int v; //物品的价值
Goods(int no1,int w1,int v1) //构造函数
{no=no1;
w=w1;
v=v1;
}
bool operator<(const Goods&s) const//用于按v/w递减排序
{
return (double)v/w>(double)s.v/s.w;
}
};
例如，表5.1所示的4个物品采用向量g存放：
vector<Goods> g={Goods(0,5,4),Goods(1,3,4),Goods(2,2,3),Goods(3,1,1)};//一个测试实例
设当前解向量x=(x0，x1，…，xn-1)，xi=1表示选择物品i，xi=1表示不选择物品i，最优解向量用bestx表示，最大价值用bestv表示(初始为0)，为了简洁，将n、W、bestx和bestv均设计为全局变量。
2) 左剪支
由于所有物品重量为正数，采用与子集和问题类似的左剪支。当搜索到第i(0≤i＜n)层的某个结点时，cw表示当前选择的物品重量和(其中不包含w［i］)。检查当前物品被选中后总重量是否超过W，若超过则剪支，即仅扩展满足cw+w［i］≤W的左孩子结点。
3) 右剪支
这里右剪支相对复杂一些，题目求的是价值最大的装入方案，显然优先选择单位重量价值大的物品，为此将g中所有物品按单位重量价值递减排序，例如表5.1中物品排序后的结果如表5.2所示，序号i发生了改变，后面改为按i而不是按物品编号no的顺序依次搜索。
表5.24个物品按v/w递减排序后的结果
序号i物品编号no重量w价值vv/w
02231.5
11341.3
23111
30540.8
先看这样的问题，对于第i层的某个结点，cw表示当前选择的物品重量和(其中不包含w［i］)，cv表示当前选择的物品价值和(其中不包含v［i］)，那么继续搜索下去能够得到的最大价值是多少？由于所有物品已按单位重量价值递减排序，显然在背包容量允许的前提下应该依次连续地选择物品i、物品i+1、……，这样做直到物品k装不进背包，假设再将物品k的一部分装进背包直到背包装满，此时一定会得到最大价值。从中看出从物品i开始选择的物品价值和的最大值为r(i)，其中有：
r(i)=∑k-1j=ivj+rw-∑k-1j=iwj(vk/wk)
再回过来讨论右剪支，右剪支是判断不选择物品i时是否能够找到更优解。如果不选择物品i，按上述讨论可知在背包容量允许的前提下依次选择物品i+1、物品i+2、……可以得到最大价值，且从物品i+1开始选择的物品价值和的最大值为r(i+1)。如果之前已经求出一个最优解bestv，当cv+r(i+1)≤bestv时说明不选择物品i时后面无论如何也不能够找到更优解。设计如下限界函数bound(cw,cv,i)：
double bound(int cw,int cv,int i) //计算第i层结点的上界函数值
{int rw=W-cw; //背包的剩余容量
double b=cv; //表示物品价值的上界值
int j=i;
while (j<n && g［j］.w<=rw)
{rw-=g［j］.w; //选择物品j
b+=g［j］.v; //累计价值
j++;
}
if (j<n) //最后物品(此时的j就是r(i)公式中的k)只能部分装入
b+=(double)g［j］.v/g［j］.w*rw;
return b;
}
这样当搜索到第i层的某个结点时，右剪支就是仅扩展满足bound(cw,cv,i+1)＞bestv的右孩子结点。
图5.130/1背包问题实例的搜索空间
例如，对于根结点，cw=0，cv=0，若不选择物品0(对应根结点的右孩子结点)，剩余背包容量rw=W=6，b=cv=0，考虑物品1，g［1］.w＜rw，可以装入，b=b+g［1］.v=4，rw=rw-g［1］.w=3； 考虑物品2，g［2］.w＜rw，可以装入，b=b+g［2］.v=5，rw=rw-g［2］.w=2； 考虑物品3，g［3］.w＞rw，只能部分装入，b=b+rw×(g［3］.v/g［3］.w)=6.6。
右剪支是求出第i层的结点的b=bound(cw,cv,i)，若b≤bestv，则停止右分支的搜索，也就是说仅扩展满足b＞bestv的右孩子结点。
对于表5.1所示的实例，n=4，按v/w递减排序后为表5.2，初始时bestv=0，求解过程如图5.13所示，图5.13中两个数字的结点为(cw,cv)，只有右结点标记为(cw,cv,ub)，为“×”的虚结点表示被剪支的结点，带阴影的结点是最优解结点，其求解结果与回溯法的完全相同，图中结点的数字为(cw，cv)，求解步骤如下：
① i=0，根结点为(0，0)，cw=0，cv=0，cw+w［0］≤W成立，扩展左孩子结点，cw=cw+w［0］=2，cv=cv+v［0］=3，对应结点(2，3)。
② i=1，当前结点为(2，3)，cw+w［1］(5)≤W成立，扩展左孩子结点，cw=cw+w［1］=5，cv=cv+v［1］=7，对应结点(5，7)。
③ i=2，当前结点为(5，7)，cw+w［2］(6)≤W成立，扩展左孩子结点，cw=cw+w［2］=6，cv=cv+v［1］=7，对应结点(6，8)。
④ i=3，当前结点为(6，8)，cw+w［2］(6)≤W不成立，不扩展左孩子结点。
⑤ i=3，当前结点为(6，8)，不选择物品3时计算出b=cv+0=8，而b＞bestv(0)成立，扩展右孩子结点。
⑥ i=4，当前结点为(6，8)，由于i≥n成立，它是一个叶子结点，对应一个解bestv=8。
⑦ 回溯到i=2层次，当前结点为(5，7)，不选择物品2时计算出b=7.8，b＞bestv不成立，不扩展右孩子结点。
⑧ 回溯到i=1层次，当前结点为(2，3)，不选择物品1时计算出b=6.4，b＞bestv不成立，不扩展右孩子结点。
⑨ 回溯到i=0层次，当前结点为(0，0)，不选择物品0时计算出b=6.6，b＞bestv不成立，不扩展右孩子结点。
解空间搜索完，最优解为bestv=8，装入方案是选择编号为2、1、3的3个物品。从中看出如果不剪支搜索的结点个数为31，剪支后搜索的结点个数为5。
对应的递归算法如下：
void dfs(int cw,int cv,vector<int>&x,int i) //回溯算法
{if (i>=n) //找到一个叶子结点
{if (cw<=W && cv>bestv) //找到一个满足条件的更优解,保存它
{bestv=cv;
bestx=x;
}
}
else //没有到达叶子结点
{if(cw+g［i］.w<=W) //左剪支
{x［i］=1; //选取物品i
dfs(cw+g［i］.w,cv+g［i］.v,x,i+1);
}
double b=bound(cw,cv,i+1); //计算上界时从物品i+1开始
if(b>bestv) //右剪支
{x［i］=0; //不选取物品i
dfs(cw,cv,x,i+1);
}
}
}
void knap() //求0/1背包问题
{bestx.resize(n);
vector<int> x(n);
sort(g.begin(),g.end()); //按v/w递减排序
dfs(0,0,x,0); //i从0开始
}
扫一扫
视频讲解
【算法分析】上述算法在不考虑剪支时解空间树中有2n+1-1个结点，求上界函数值和保存最优解的时间为O(n)，所以最坏情况下算法的时间复杂度为O(n×2n)。
5.2.4n皇后问题
1. 问题描述
在n×n(n≥4)的方格棋盘上放置n个皇后，并且每个皇后不同行、不同列、不同左右对角线(否则称为有冲突)。如图5.14所示为6皇后问题的一个解。要求给出n个皇后的全部解。
2. 问题求解
本问题的解空间是一棵子集树(每个皇后在1～n列中找到一个适合的列号，即n选一)，并且要求所有解。
图5.146皇后问题的一个解
采用整数数组q［N］存放n皇后问题的求解结果，因为每行只能放一个皇后，q［i］(1≤i≤n)的值表示第i个皇后所在的列号，即第i个皇后放在(i，q［i］)的位置上。对于图5.14的解，q［1..6］={2，4，6，1，3，5}(为了简便，不使用q［0］元素)。
若在(i，j)位置上放第i个皇后，是否与已放好的i-1个皇后(k，q［k］)(1≤k≤i-1)有冲突？显然它们是不同行的(因为皇后的行号i总是递增的)，所以不必考虑行冲突，是否存在列冲突和对角线冲突的判断如下：
① 如果(i，j)位置与前面的某个皇后同列，则有q［k］==j成立。
② 如果(i，j)位置与前面的某个皇后同对角线，如图5.15所示，则恰好构成一个等腰直角三角形，即有|q［k］-j|==|i-k|成立。
图5.15两个皇后构成对角线的情况
归纳起来只要(i，j)位置满足以下条件就存在冲突，否则不冲突：
(q［k］==j) ‖ (abs(q［k］-j)==abs(i-k))1≤k≤i-1
由此得到测试(i，j)位置能否放置第i个皇后的算法如下：
bool place(int i,int j) //测试(i,j)位置能否放置皇后
{if (i==1) return true; //第一个皇后总是可以放置
int k=1;
while (k<i) //k=1～i-1是已放置了皇后的行
{if ((q［k］==j) || (abs(q［k］-j)==abs(i-k)))
return false;
k++;
}
return true;
}
现在采用递归回溯框架求解。设queen(i，n)是在1～i-1行上已经放好了i-1个皇后，用于在i～n行放置剩下的n-i+1个皇后，为大问题； queen(i+1，n)表示在1～i行上已经放好了i个皇后，用于在i+1～n行放置n-i个皇后，为小问题，则求解皇后问题所有解的递归模型如下：
queen(i，n) ≡ n个皇后放置完毕，输出一个解若i>n
queen(i，n) ≡ 在第i行找到一个合适的位置(i，j)，放置一个皇后;其他
queen(i+1，n);
对应的递归回溯算法如下：
int q［MAXN］; //存放各皇后所在的列号，为全局变量
int cnt=0; //累计解的个数
void disp(int n) //输出一个解
{printf(" 第%d个解:",++cnt);
for (int i=1;i<=n;i++)
printf("(%d,%d) ",i,q［i］);
printf("＼n");
}
void queen11(int n,int i) //回溯算法
{if (i>n)
disp(n); //所有皇后放置结束
else
{for (int j=1;j<=n;j++) //在第i行上试探每一个列j
{if (place(i,j)) //在第i行上找到一个合适位置(i,j)
{q［i］=j;
queen11(n,i+1);
q［i］=0; //回溯
}
}
}
}
void queen1(int n) //用递归法求解n皇后问题
{
queen11(n,1);
}
利用上述算法求出6皇后问题的4个解如下：
第1个解： (1,2) (2,4) (3,6) (4,1) (5,3) (6,5)
第2个解： (1,3) (2,6) (3,2) (4,5) (5,1) (6,4)
第3个解： (1,4) (2,1) (3,5) (4,2) (5,6) (6,3)
第4个解： (1,5) (2,3) (3,1) (4,6) (5,4) (6,2)
另外也可以采用迭代方式求解n皇后问题。同样用数组q存放皇后的列位置，(i，q［i］)表示第i个皇后放置的位置，n皇后问题的一个解是(1，q［1］)，(2，q［2］)，…，(n，q［n］)，数组q的下标为0的元素不用。
由于在第i行中找第i个皇后的列号时总是先执行q［i］++再判断(i，q［i］)位置是否合适，所以q［i］的初始值必须置为0。
先放置第1个皇后，然后以2、3、……、n的次序放置其他皇后，当第n个皇后放置好后产生一个解。为了找到所有解，此时算法还不能结束，继续试探第n个皇后的下一个位置。
第i(i＜n)个皇后放置后，接着放置第i+1个皇后，在试探第i+1个皇后的位置时都是从第1列开始的。当第i个皇后试探了所有列都不能放置时，回溯到第i-1个皇后，此时与第i-1个皇后的位置(i-1，q［i-1］)有关，如果第i-1个皇后的列号小于n，即q［i-1］＜n，则将其移到下一列，继续试探； 否则再回溯到第i-2个皇后，以此类推。
对应的迭代回溯算法如下：
void queen2(int n)//用迭代法求解n皇后问题
{int i=1; //i表示当前行，i=1表示从第1个皇后开始
q［i］=0; //q［i］是当前列，在试探之前q［i］置为0
while (i>=1) //重复试探
{q［i］++; //总是先将列号增1
while (q［i］<=n && !place(i,q［i］)) //试探一个位置(i,q［i］)是否合适
q［i］++;
if (q［i］<=n) //为第i个皇后找到了一个合适位置(i,q［i］)
{if (i==n) //若放置了所有皇后,输出一个解
disp(n);
else //皇后没有放置完
{i++; //转向下一个皇后的放置
q［i］=0;//每次试探一个新皇后,q［i］总是从0开始
}
}
else i--; //若第i个皇后找不到合适位置,则回溯到前一个皇后
}
}
从上看出迭代回溯算法远不如递归回溯算法清晰，这就是为什么在一般情况下回溯算法都是采用递归回溯算法的原因。
【算法分析】该算法中每个皇后都要试探n列，共n个皇后，其解空间是一棵子集树，每个结点可能有n棵子树，而每个皇后试探一个合适位置的时间为O(n)，所以最坏情况下算法时间复杂度为O(n×nn)。
扫一扫
视频讲解
5.2.5任务分配问题
1. 问题描述
有n(n≥1)个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务。第i个人执行第j个任务的成本是c［i］［j］(0≤i，j≤n-1)。求出总成本最小的一种分配方案。如表5.3所示为4个人员、4个任务的信息。
表5.34个人员、4个任务的信息
人员任务0任务1任务2任务3
0
9
2
7
8
1
6
4
3
7
2
5
8
1
8
3
7
6
9
4
2. 问题求解
n个人和n个任务的编号均用0～n-1表示。所谓一种分配方案就是由第i个人执行第j个任务，也就是说每个人从n个任务中选择一个任务，即n选一，所以本问题的解空间树可以看成一棵子集树，并且要求总成本最小的解(最优解是最小值)，属于求最优解类型。
设计解向量x=(x0，x1，…，xn-1)，这里以人为主，即人找任务(也可以以任务为主，即任务找人)，也就是第i个人执行第xi个任务(0≤xi≤n-1)。bestx表示最优解向量，bestc表示最优解的成本(初始值为∞)，x表示当前解向量，cost表示当前解的总成本(初始为0)，另外设计一个used数组，其中used［j］表示任务j是否已经分配(初始时所有元素均为false)，为了简单，将这些变量均设计为全局变量。
解空间中根结点的层次i为0，当搜索到第i层的每个结点时，表示为第i个人分配一个没有分配的任务，即选择满足used［j］=0(0≤j≤n-1)的任务j。对应的递归回溯算法如下：
int n=4; //一个测试实例
int c［MAXN］［MAXN］={{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};
vector<int> bestx;//最优解向量
int bestc=INF; //最优解的成本,初始值为∞
bool used［MAXN］;//used［j］表示任务j是否已经分配
void dfs(vector<int>&x,int cost,int i) //为第i个人员分配任务
{if (i>=n) //到达叶子结点
{if (cost<bestc)//比较求最优解
{bestc=cost;
bestx=x;
}
}
else //没有到达叶子结点
{for (int j=0;j<n;j++) //为人员i试探分配任务
{if (used［j］==0) //若任务j还没有被分配
{x［i］=j;//将任务j分配给人员i
used［j］=true; //表示任务j已经被分配
cost+=c［i］［j］; //累计成本
dfs(x,cost,i+1); //继续为人员i+1分配任务
used［j］=false; //used［j］回溯
x［i］=-1;//x［i］回溯
cost-=c［i］［j］; //cost回溯
}
}
}
}
void alloction() //求解算法
{memset(used,false,sizeof(task));
vector<int> x(n,0); //当前解向量，n个元素初始化为0
int cost=0; //当前解的成本
dfs(x,cost,0); //从人员0开始分配任务
}
上述算法的执行结果如下：
第0个人安排任务1
第1个人安排任务0
第2个人安排任务2
第3个人安排任务3
总成本=13
【算法分析】算法的解空间是一棵n叉树（子集树），再考虑叶子结点处复制更优解的时间为O(n)，所以最坏的时间复杂度为O(n×nn)。例如，表5.3的实例中n=4，经测试搜索的结点个数为65。
现在考虑采用剪支提高性能，该问题是求最小值，所以设计下界函数。当搜索到第i层的某个结点时，如果选择了任务j(即执行x［i］=j，cost+=c［i］［j］)，此时部分解向量P=(x0，x1，…，xi)，那么后面如何分配才能使得该路径(一条从根到叶子结点的路径对应一个分配方案)的cost尽可能小呢？如果后面编号为i+1～n-1的每个人都分配一个尚未分配的最小成本的任务，其累计成本为
图5.16人员i安排任务j的情况
minsum=∑n-1i1=i+1minj1Pci1,j1
则b=cost+minsum一定是该路径的最小成本，如图5.16所示。如果b≥bestc(bestc是当前已经求出的一个最优成本)，说明x［i］=j这条路径走下去一定不可能找到更优解，所以停止该分支的搜索。这里的剪支就是仅扩展b＜bestc的孩子结点。
带剪支的递归回溯算法如下：
int bound(int cost,int i) //求下界算法
{int minsum=0;
for (int i1=i;i1<n;i1++) //求c［i..n-1］行中未分配任务的最小成本和
{int minc=INF; //置为∞
for (int j1=0;j1<n;j1++)
if (used［j1］==false && c［i1］［j1］<minc)
minc=c［i1］［j1］;
minsum+=minc;
}
return cost+minsum;
}
void dfs(vector<int>&x,int cost,int i) //为第i个人员分配任务
{if (i>=n) //到达叶子结点
{if (cost<bestc) //比较求最优解
{bestc=cost;
bestx=x;
}
}
else //没有到达叶子结点
{for (int j=0;j<n;j++) //为人员i试探任务j
{if (used［j］==0) //若任务j还没有被分配
{used［j］=true;
x［i］=j; //任务j分配给人员i
cost+=c［i］［j］;
if(bound(cost,i+1)<bestc)//剪支(考虑c［i+1..n-1］行中的最小成本)
dfs(x,cost,i+1); //继续为人员i+1分配任务
used［j］=false; //回溯
x［i］=-1;
cost-=c［i］［j］;
}
}
}
}
对于表5.3的实例，经测试搜索的结点个数为9，算法的时间性能得到明显提高。但求下界的时间为O(n2)，带剪支的回溯算法的最坏时间复杂度为O(n2×nn)。
扫一扫
视频讲解
5.2.6出栈序列
1. 问题描述
有一个含n个不同元素的进栈序列a，求通过一个栈得到的所有合法的出栈序列。例如a={1，2，3}时产生的5个合法的出栈序列是{3，2，1}、{2，3，1}、{2，1，3}、{1，3，2}、{1，2，3}。
2. 问题求解
设计一个栈st，用i遍历a的元素(初始时i=0)，解向量为x=(x0，x1，…，xn-1)，每个解向量对应一个合法的出栈序列，j表示产生的出栈序列中的元素个数。显然一种状态是由(a，st，x)确定的，实际上由a和x可以确定st的状态，所以可以简化为用(a，x)表示状态，而a的状态可以用其遍历变量i表示，x的状态可以用j表示，这样实际状态用(i，j)表示。如图5.17所示，在(i，j)状态下可以选择以下两种操作：
① ai进栈(i＜n)，状态变为(i+1，j)。
② 出栈一个元素tmp(栈st非空)并且添加到x中，状态变为(i，j+1)。注意i=j时表示栈空，此时不能做出栈操作。
由此看出该问题类似于子集和问题，每次在两种操作中选择一个操作执行，所以可以采用基于子集树的回溯算法求解。
图5.17在(i，j)状态下的两种操作
显然解空间中的叶子结点的状态是(n，n)，表示a中所有元素遍历完成，并且产生的出栈序列包含n个元素，此时的x就是一个合法的出栈序列。例如，a={1，2，3}的求解过程如图5.18所示。
对应的算法如下：
int sum=0; //累计出栈序列的个数
vector<int> a={1,2,3}; //进栈序列
int n=a.size(); //进栈序列的元素个数
stack<int> st;
void disp(vector<int>& x) //输出一个解
{printf(" 出栈序列%2d: ",++sum);
for (int i=0;i<n;i++)
printf("%d ",x［i］);
printf("＼n");
}
void dfs(vector<int>& x,int i,int j) //递归算法
{if (i==n && j==n) //输出一种可能的方案
disp(x);
else
{if (i<n) //剪支： in时a［i］进栈
{st.push(a［i］); //a［i］进栈
dfs(x,i+1,j);
st.pop();//回溯： 出栈
}
if (!st.empty()) //剪支： 栈不空时出栈tmp
{int tmp=st.top(); st.pop(); //出栈tmp
x［j］=tmp; //将tmp添加到x中
j++; //j增加1
dfs(x,i,j);
j--; //回溯： j减少1
st.push(tmp); //回溯： x进栈以恢复环境
}
}
}
void solve() //求a的所有合法的出栈序列
{vector<int> x(n);
dfs(x,0,0); //i、j均从0开始
}
图5.18求a={1,2,3}的所有出栈序列的过程
【算法分析】类似子集和问题，但解空间的高度大约为i+j=2n，输出一个解的时间为O(n)，所以最坏情况下的时间复杂度为O(n×22n)即O(n×4n)，由于存在剪支操作（保证i≥j，即出栈序列中的元素个数一定不大于进栈的元素个数），所以实际时间性能远好于O(n×4n)。
扫一扫
视频讲解
5.2.7图的m着色
1. 问题描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色方案的数目。
2. 问题求解
对于含n个顶点的无向连通图G，顶点的编号是0～n-1，采用vector<int>数组的邻接表A存储，其中A［i］向量为顶点i的所有相邻顶点。例如如图5.19所示的无向连通图，对应的邻接表如下：
图5.19一个无向连通图
A［0..3］={{1,2,3},{0},{0,3},{0,2}}
m种颜色的编号为0～m-1，这里实际上就是为每个顶点i选择m种颜色中的一种(m选一)，使得任意两个相邻顶点的着色不同，所以解空间树看成一棵子集树，并且求解个数，属于求所有解类型。
设计解向量为x=(x0，x1，…，xn-1)，其中xi表示顶点i的着色(0≤xi≤m-1)，初始时置x的所有元素为-1，表示所有顶点均没有着色，用cnt累计解个数(初始为0)。采用递归回溯方法从顶点0开始试探(i=0对应根结点)，当i≥n时表示找到一种着色方案(对应解空间中的一个叶子结点)。
对于顶点i，所有可能的着色j为0~m-1中的一种，如果顶点i的所有相邻顶点的颜色均不等于j，说明顶点i着色j是合适的，只要有一个相邻顶点的颜色等于j，则顶点i着色j是不合适的，需要回溯。对应的算法如下：
#define MAXN 30//最多顶点个数
int n;
vector<int> A［MAXN］; //邻接表
int cnt; //全局变量，累计解个数
int x［MAXN］; //全局变量，x［i］表示顶点i的着色
bool judge(int i,int j) //判断顶点i是否可以着颜色j
{for(int k=0;k<A［i］.size();k++)
{if(x［A［i］［k］］==j) //存在相同颜色的顶点
return false;
}
return true;
}
void dfs(int m,int i) //递归回溯算法
{if(i>=n) //达到一个叶子结点
cnt++;
else
{for(int j=0;j<m;j++)
{x［i］=j; //置顶点i为颜色j
if(judge(i,j)) //若顶点i可以着颜色j
dfs(m,i+1);
x［i］=-1; //回溯
}
}
}
int Colors(int m)//求图的m着色问题
{cnt=0;
memset(x,0xff,sizeof(x)); //所有元素初始化为-1
dfs(m,0); //从顶点0开始搜索
return cnt;
}
例如，对于图5.19，若m=3，求出有12种不同的着色方案。
【算法分析】在该算法中每个顶点都试探编号为0～m-1的颜色，共n个顶点，对应解空间树是一棵m叉树（子集树），每个结点调用judge()的时间为O(n)，所有算法的最坏时间复杂度为O(n×mn)。
5.2.8实战——救援问题(HDU1242)
1. 问题描述
扫一扫
视频讲解
A被抓进了监狱，监狱被描述为一个有N×M(N，M≤200)个方格的网格，监狱里有围墙、道路和守卫。A的朋友们想要救他(可能有多个朋友)，只要有一个朋友找到A(就是到达A所在的位置)那么A将被救了。在找A的过程中只能向上、向下、向左和向右移动，若遇到有守卫的方格必须杀死守卫才能进入该方格。假设每次向上、向下、向右、向左移动需要一个单位时间，而杀死一个守卫也需要一个单位时间。请帮助A的朋友们计算救援A的最短时间。
输入格式： 第一行包含两个整数，分别代表N和M。然后是N行，每行有M个字符，其中'#'代表墙，'.'代表道路，'a'代表A，'r'代表A的朋友，'x'代表守卫。处理到文件末尾。
输出格式： 对于每个测试用例，输出一个表示所需最短时间的整数。如果这样的整数不存在，输出一行包含"Poor ANGEL has to stay in the prison all his life"的字符串。
输入样例：
78
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
输出样例：
13
2. 问题求解
本题与迷宫问题类似，假设距离A最近的是朋友B，显然B到A的最短路径和B到A的最短路径是相同的，由于A只有一个人，而他的朋友可能有多个，所以这里从A出发搜他的最近的朋友。A的位置用(sx，sy)表示(对应解空间的根结点)，从该位置搜索路径，len表示当前路径的长度，bestlen表示最优解，即最短路径长度(初始置为∞)，每次找到一个朋友(对应解空间的叶子结点)比较路径长度，将最短路径长度保存在bestlen中。与普通迷宫问题相比，每次路径搜索也是4个方位选一，但改为遇到道路'.'走一步，路径长度len增加1，当遇到守卫'x'时除了走一步还需要杀死守卫，所以路径长度len增加2。解空间搜索完毕，若bestlen为∞，说明没有找到任何朋友，按题目要求输出一个字符串，否则说明最少找到一个朋友，输出bestlen即可。对应的程序如下：
#include<iostream>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 202
int dx［］={0,0,1,-1}; //水平方向偏移量
int dy［］={1,-1,0,0}; //垂直方向偏移量
char grid［MAXN］［MAXN］; //存放网格
int visited［MAXN］［MAXN］; //访问标记数组
int n,m;
int bestlen;
void dfs(int x,int y,int len)
{if(grid［x］［y］=='r')//找到朋友
{if(len<bestlen)//比较求最短路径长度
bestlen=len;
}
else
{for(int di=0;di<4;di++) //枚举4个方位
{int nx=x+dx［di］;
int ny=y+dy［di］;
if(nx<0 || nx>=n || ny<0 || ny>=m) //(nx,ny)超界时跳过
continue;
if(visited［nx］［ny］==1) //(nx,ny)已访问时跳过
continue;
if(grid［x］［y］=='#') //(nx,ny)为墙时跳过
continue;
if(grid［nx］［ny］=='x') //(nx,ny)为守卫的情况
{visited［nx］［ny］=1; //标记(nx,ny)已经访问
dfs(nx,ny,len+2); //走一步+杀死守卫
visited［nx］［ny］=0; //路径回溯
}
else //(nx,ny)为道路的情况
{visited［nx］［ny］=1;
dfs(nx,ny,len+1); //走一步
visited［nx］［ny］=0;
}
}
}
}
int main()
{int sx,sy; //标记A的位置
while(cin >> n >> m)
{for(int i=0;i<n;i++) //输入矩阵
{for(int j=0;j<m;j++)
{cin >> grid［i］［j］;
if(grid［i］［j］=='a')
{sx=i;
sy=j;
}
}
}
bestlen=INF;
memset(visited,0,sizeof(visited));
dfs(sx,sy,0);
if(bestlen==INF)//如果bestlen为INF说明没找到路径
cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else
cout << bestlen << endl;
}
return 0;
}
上述程序提交的结果为通过，执行时间为187ms，内存消耗为1596KB，满足题目的时空要求。
5.3基于排列树框架的问题求解
扫一扫
视频讲解
5.3.1任务分配问题
1. 问题描述
见5.2.5节任务分配问题的描述。
2. 问题求解
n个人和n个任务的编号均用0～n-1表示，设计解向量x=(x0，x1，…，xn-1)，同样以人为主，也就是第i个人执行第xi个任务(0≤xi≤n-1)，显然每个合适的分配方案x一定是0～n-1的一个排列，可以求出0～n-1的全排列，每个排列作为一个分配方案，求出其成本，比较找到一个最小成本bestc即可。
用bestx表示最优解向量，bestc表示最优解的成本，x表示当前解向量，cost表示当前解的总成本(初始为0)，另外设计一个used数组，其中used［j］表示任务j是否已经分配(初始时所有元素均为false)，为了简单，将这些变量均设计为全局变量。根据排列树的递归算法框架，当搜索到第i层的某个结点时，第一个swap(x［i］,x［j］)表示为人员i分配任务x［j］(注意不是任务j)，成本是c［i］［x［i］］(因为x［i］就是交换前的x［j］)，所以执行used［x［i］］=true，cost+=c［i］［x［i］］，
图5.20为人员i安排任务x［j］的情况
调用dfs(x,cost,i+1)继续为人员i+1分配任务，回溯操作是cost-=c［i］［x［i］］、used［x［i］］=false和swap(x［i］,x［j］)(正好与调用dfs(x,cost,i+1)之前的语句的顺序相反)。
考虑采用剪支提高性能，设计下界函数，与5.2.5节的bound算法相同，仅需要将j(指任务编号)改为x［j］即可，如图5.20所示。
带剪支的排列树递归回溯算法如下：
int n=4; //一个测试实例
int c［MAXN］［MAXN］={{9,2,7,8},{6,4,3,7},{5,8,1,8},{7,6,9,4}};
vector<int> bestx; //最优解向量
int bestc=INF; //最优解的成本，初始置为∞
bool used［MAXN］; //used［j］表示任务j是否已经分配人员
int bound(vector<int>&x,int cost,int i) //求下界算法
{int minsum=0;
for (int i1=i;i1<n;i1++) //求c［i..n-1］行中未分配的最小成本和
{int minc=INF;
for (int j1=0;j1<n;j1++)
if (used［x［j1］］==false && c［i1］［x［j1］］<minc)
minc=c［i1］［x［j1］］;
minsum+=minc;
}
return cost+minsum;
}
void dfs(vector<int>&x,int cost,int i) //递归回溯(排列树)算法
{if (i>=n) //到达叶子结点
{if (cost<bestc) //比较求最优解
{bestc=cost;
bestx=x;
}
}
else //没有到达叶子结点
{for (int j=i;j<n;j++) //为人员i试探任务x［j］
{if (used［x［j］］) continue; //若任务x［j］已经被分配，则跳过
swap(x［i］,x［j］); //为人员i分配任务x［j］
used［x［i］］=true;
cost+=c［i］［x［i］］;
if(bound(x,cost,i+1)<bestc)//剪支
dfs(x,cost,i+1); //继续为人员i+1分配任务
cost-=c［i］［x［i］］; //cost回溯
used［x［i］］=false; //used回溯
swap(x［i］,x［j］);
}
}
}
void alloction() //基于排列树的递归回溯算法
{memset(used,false,sizeof(used));
vector<int> x; //当前解向量
for(int i=0;i<n;i++)//将x［0..n-1］分别设置为0到n-1的值
x.push_back(i);
int cost=0; //当前解的成本
dfs(x,cost,0); //从人员1开始
}
【算法分析】算法的解空间是一棵排列树，求下界的时间为O(n2)，所以最坏的时间复杂度为O(n2×n!)。例如，上述实例中n=4，经测试不剪支（除去dfs中的if(bound(x,cost,i)<bestc)）时搜索的结点个数为65，而剪支后搜索的结点个数为9。
说明： 任务分配问题在5.2.5节采用基于子集树框架时最坏时间复杂度为O(n2×nn)，这里采用基于排列树框架的最坏时间复杂度为O(n2×n!)，显然n＞2时O(n!)优于O(nn)，实际上由于前者通过used判重，剪去了重复的分支，其解空间本质上也是一棵排列树，两种算法的最坏时间复杂度都是O(n2×n!)，类似地有5.2.4节的n皇后问题等。
扫一扫
视频讲解
5.3.2货郎担问题
1. 问题描述
货郎担问题又译为旅行商问题(TSP)，是数学领域中的著名问题之一。假设有一个货郎担要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，要求路径长度最短的路径。
图5.21一个4城市的图
以图5.21所示的一个4城市图为例，假设起点s为0，所有从顶点0回到顶点0并通过所有顶点的路径如下：
路径1： 0→1→2→3→0： 28
路径2： 0→1→3→2→0： 29
路径3： 0→2→1→3→0： 26
路径4： 0→2→3→1→0： 23
路径5： 0→3→2→1→0： 59
路径6： 0→3→1→2→0： 59
最后求得的最短路径长度为23，最短路径为0→2→3→1→0。
2. 问题求解
本问题是求路径长度最短的路径，属于求最优解类型。假设图中有n个顶点，顶点编号为0～n-1，采用邻接矩阵A存储。显然TSP路径是简单回路(除了起始点和终点相同，其他顶点不重复)，可以采用穷举法，以全排列的方式求出所有路径及其长度，再加上回边，在其中找出长度最短的回路即为TSP路径，但这样做难以剪支，时间性能较低。
现在采用基于排列树的递归回溯算法，设计当前解向量x=(x0，x1，…，xn-1)，每个xi表示一个图中顶点，实际上每个x表示一条路径，初始时x0置为起点s，x1～xn-1为其他n-1个顶点编号，d表示当前路径的长度，用bestx保存最短路径，bestd表示最短路径长度，其初始值置为∞。设计算法dfs(x，d，s，i)的几个重点如下：
图5.22x1的各种取值情况
① x0固定作为起点s，不能取其他值，所以不能从i=0开始调用dfs，应改为从i=1(此时d=0)开始调用dfs。为了简单，假设s=0，x初始时为(0，1，…，n-1)，i=1时x1会取x［1..n-1］的每一个值(共n-1种取值)，如图5.22所示，当x1=x1(1)时，对应路径长度为d+A［0］［1］，当x1=x2(2)时，对应路径长度为d+A［0］［2］，以此类推。归纳起来，当搜索到解空间的第i层的某个结点时，xi取x［i..n-1］中的某个值后当前路径长度为d+A［x［i-1］］［x［i］］。
② 当搜索到达某个叶子结点时(i≥n)，对应的TSP路径长度应该是d+A［x［n-1］］［s］(因为TSP路径是闭合的回路)，对应的路径是x∪{s}。通过比较所有回路的长度求最优解。
③ 如何剪支呢？若当前已经求出最短路径长度bestd，如果xi取xj值，对应的路径长度为d+A［x［i-1］］［x［j］］，若d+A［x［i-1］］［x［j］］≥bestd，说明该路径走下去不可能找到更短路径，终止该路径的搜索，也就是说仅扩展满足d+A［x［i-1］］［x［j］］＜bestd的路径。
对应的用回溯法求TSP问题的算法如下：
vector<vector<int>> A={{0,8,5,36},{6,0,8,5},{8,9,0,5},{7,7,8,0}};
int n=4;
int cnt=0; //路径条数累计
vector<int> bestx; //保存最短路径
int bestd=INF; //保存最短路径长度，初始为∞
void disp(vector<int>&x,int d,int s) //输出一个解
{printf(" 第%d条路径: ",++cnt);
for (int j=0;j<x.size();j++)
printf("%d>",x［j］);
printf("%d",s); //末尾加上起点s
printf(", 路径长度: %d＼n",d+A［x［n-1］］［s］);
}
void dfs(vector<int>&x,int d,int s,int i) //回溯法算法
{if(i>=n) //到达一个叶子结点
{disp(x,d,s); //输出一个解
if(d+A［x［n-1］］［s］<bestd) //同时比较求最优解
{bestd=d+A［x［n-1］］［s］; //求TSP长度
bestx=x; //更新bestx
bestx.push_back(s); //末尾添加起始点
}
}
else //没有到达叶子结点
{for(int j=i;j<n;j++) //试探x［i］走到x［j］的分支
{if (A［x［i-1］］［x［j］］!=0 && A［x［i-1］］［x［j］］!=INF)//若x［i-1］到x［j］有边
{if(d+A［x［i-1］］［x［j］］<bestd) //剪支
{swap(x［i］,x［j］);
dfs(x,d+A［x［i-1］］［x［i］］,s,i+1);
swap(x［i］,x［j］);
}
}
}
}
}
void TSP1(int s) //用回溯法求解TSP(起始点为s)
{vector<int> x; //定义解向量
x.push_back(s);
for(int i=1;i<n;i++) //将非s的顶点添加到x中
if(i!=s)
x.push_back(i);
int d=0;
dfs(x,d,s,1); //从x［1］顶点开始扩展
}
上述算法当s=1时的求解结果如下。实际上共有6条路径，通过剪支终止了两条路径的搜索。
第1条路径: 1→0→2→3→1,路径长度: 23
第2条路径: 1→2→3→0→1,路径长度: 28
第3条路径: 1→3→2→0→1,路径长度: 29
第4条路径: 1→3→0→2→1,路径长度: 26
最短路径:1→0→2→3→1,路径长度: 23
【算法分析】算法的解空间是一棵排列树，由于是从第一层开始搜索的，排列树的高度为n（含叶子结点层），考虑输出一个解的时间为O(n)，所以最坏的时间复杂度为O(n×(n-1)!)即O(n!)。
思考题： TSP问题是在一个图中查找从起点s经过其他所有顶点又回到顶点s的最短路径，在上述算法中为什么不考虑路径中出现重复顶点的情况？
扫一扫
视频讲解
5.3.3实战——含重复元素的全排列Ⅱ(LeetCode47)
1. 问题描述
给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。例如， nums=［1，1，2］，输出结果是［［1，1，2］， ［1，2，1］， ［2，1，1］］。要求设计如下函数：
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) { }
};
2. 问题求解
该问题与求非重复元素的全排列问题类似，解空间是排列树，并且属于求所有解类型。先按求非重复元素全排列的一般过程求含重复元素的全排列，假设a={1，1，2}，其中包含两个1，为了区分，后面一个1加上一个框，求其全排列的过程如图5.23所示。从中看出，11的分支和11的分支产生的所有排列是相同的，属于重复的排列，应该剪去后者，再看第1层的“{2,1,1}”结点，同样它扩展的两个分支分别是11和11，也是相同的，也应该剪去后者。这样剪去后得到的结果是{1，1，2}，{1，2，1}和{2，1，1}，也就是不重复的全排列。
图5.23求a={1，1，2}的全排列的过程
图5.24xi的各种取值
同样设解向量为x=(x0，x1，…，xn)，每个x表示一个排列，xi表示该排列中i位置所取的元素，初始时x=nums。在解空间中搜索到第i层的某个结点C时，如图5.24所示，C结点的每个分支对应xi的一个取值，理论上讲xi可以取xi～xn-1的每个值，也就是说从根结点经过结点C到达第i+1层的结点有n-1-i+1=n-i条路径，在这些路径中从根结点到C结点都是相同的。当xi取值xj时(对应图中粗分支)走到B结点，如果xj与前面xi～xj-1中的某个值xk相同，当xi取值xk时走到A结点，显然根结点到A和B结点的路径完全相同，而且它们的层次相同，后面的操作也相同，则所有到达叶子结点产生的解必然相同，属于重复的排列，需要剪去。
剪去重复解的方法是，当j从i到n-1循环时，每次循环执行swap(x［i］，x［j］)为i位置选取元素x［j］，如果x［j］与x［i..j-1］中的某个元素相同，则会出现重复的排列，跳过，也就是说在执行swap(x［i］，x［j］)之前先判断x［j］是否在前面的元素x［i..j-1］中出现过，如果没有出现过就继续做下去，否则跳过x［j］的操作。对应的程序如下：
class Solution {
vector<vector<int>> ps; //存放nums的全排列
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{int n=nums.size();
dfs(nums,n,0);
return ps;
}
void dfs(vector<int>&x,int n,int i) //递归算法
{if (i>=n) //到达叶子结点
ps.push_back(x);
else //没有到达叶子结点
{for (int j=i;j<n;j++) //遍历x［i..n-1］
{if(judge(x,i,j)) //检测x［j］
{swap(x［i］,x［j］); //为i位置选取元素x［j］
dfs(x,n,i+1); //继续
swap(x［i］,x［j］); //回溯
}
}
}
}
bool judge(vector<int>& x,int i,int j)
//判断x［j］是否在x［i..j-1］中出现过，若出现过，返回false； 没有出现过，返回true
{if(j>i)
{for(int k=i;k<j;k++) //x［j］是否与x［i..j-1］的元素相同
if(x［k］==x［j］) //若相同返回false
return false;
}
return true; //全部不相同返回true
}
};
上述程序提交时通过，执行时间为4ms，内存消耗为8.7MB。
5.4练习题
5.4.1单项选择题
1. 回溯法是在问题的解空间中按策略从根结点出发搜索的。
A. 广度优先B. 活结点优先C. 扩展结点优先D. 深度优先
2. 下列算法中通常以深度优先方式搜索问题的解。
A. 回溯法B. 动态规划C. 贪心法D. 分支限界法
3. 关于回溯法以下叙述中不正确的是。
A. 回溯法有通用解题法之称，可以系统地搜索一个问题的所有解或任意解
B. 回溯法是一种既带系统性又带跳跃性的搜索算法
C. 回溯法算法需要借助队列来保存从根结点到当前扩展结点的路径
D. 回溯法算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向祖先结点回溯
4. 回溯法的效率不依赖于下列因素。
A. 确定解空间的时间B. 满足显式约束的值的个数
C. 计算约束函数的时间D. 计算限界函数的时间
5. 下面是回溯法中为避免无效搜索采取的策略。
A. 递归函数B. 剪支函数C. 随机数函数D. 搜索函数
6. 对于含n个元素的子集树问题(每个元素二选一)，最坏情况下解空间树的叶子结点个数是。
A. n!B. 2nC. 2n+1-1D. 2n-1
7. 用回溯法求解0/1背包问题时的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
8. 用回溯法求解0/1背包问题时最坏时间复杂度是。
A. O(n)B. O(nlog2n)C. O(n×2n)D. O(n2)
9. 用回溯法求解旅行商问题时的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
10. n个学生每个人有一个分数，求最高分的学生的姓名，最简单的方法是。
A. 回溯法B. 归纳法C. 迭代法D. 以上都不对
11. 求中国象棋中马从一个位置到另外一个位置的所有走法，采用回溯法求解时对应的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
12. n个人排队在一台机器上做某个任务，每个人的等待时间不同，完成他的任务的时间是不同的，求完成这n个任务的最小时间，采用回溯法求解时对应的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
5.4.2问答题
1. 回溯法的搜索特点是什么？
2. 有这样一个数学问题，x和y是两个正实数，求x+y=3的所有解，请问能否采用回溯法求解，如果改为x和y是两个均小于或等于10的正整数，又能否采用回溯法求解，如果能，请采用解空间画出求解结果。
3. 对于n=4，a=(11，13，24，7)，t=31的子集和问题，利用左、右剪支的回溯法算法求解，给出求出的所有解，并且画出在解空间中的搜索过程。
4. 对于n皇后问题，通过解空间说明n=3时是无解的。
5. 对于n皇后问题，有人认为当n为偶数时其解具有对称性，即n皇后问题的解个数恰好为n/2皇后问题的解个数的两倍，这个结论正确吗？
6. 本书5.2.4节采用解空间为子集树求解n皇后问题，请问能否采用解空间为排列树的回溯框架求解？如果能，请给出剪支操作，说明最坏情况下的时间复杂度，按照最坏情况下的时间复杂度比较哪个算法更好？
图5.25一个无向连通图
7. 对应如图5.25所示的无向连通图，假设颜色数m=2，给出m着色的所有着色方案，并且画出对应的解空间。
8. 有一个0/1背包问题，物品个数n=4，物品编号为0～3，它们的重量分别是3、1、2和2，价值分别是9、2、8和6，背包容量W=3。利用左、右剪支的回溯法算法求解，并且画出在解空间中的搜索过程。
9. 以下算法用于求n个不同元素a的全排序，当a=(1，2，3)时，请给出算法输出的全排序的顺序。
int cnt=0;//累计排列的个数
void disp(vector<int>&a)//输出一个解
{printf(" 排列%2d: (",++cnt);
for (int i=0;i<a.size()-1;i++)
printf("%d,",a［i］);
printf("%d)",a.back());
printf("＼n");
}
void dfs(vector<int>& a,int i) //使用递归算法
{int n=a.size();
if (i>=n-1)//递归出口
disp(a);
else
{for (int j=n-1;j>=i;j--)
{swap(a［i］,a［j］); //交换a［i］与a［j］
dfs(a,i+1);
swap(a［i］,a［j］); //交换a［i］与a［j］： 恢复
}
}
}
void perm(vector<int>& a)//求a的全排列
{
dfs(a,0);
}
10. 假设问题的解空间为(x0，x1，…，xn-1)，每个xi有m种不同的取值，所有xi取不同的值，该问题既可以采用子集树递归回溯框架求解，也可以采用排列树递归回溯框架求解，考虑最坏时间性能应该选择哪种方法？
11. 以下两个算法都是采用排列树递归回溯框架求解任务分配问题，判断其正确性，如果不正确，请指出其中的错误。
(1) 算法1：
void dfs(vector<int>&x,int cost,int i) //使用递归算法
{if (i>n) //到达叶子结点
{if (cost<bestc)//比较求最优解
{bestc=cost;
bestx=x;
}
}
else //没有到达叶子结点
{for (int j=1;j<=n;j++) //为人员i试探任务x［j］
{if (task［x［j］］) continue; //若任务x［j］已经被分配，则跳过
task［x［j］］=true;
cost+=c［i］［x［j］］;
swap(x［i］,x［j］); //为人员i分配任务x［j］
if(bound(x,cost,i)<bestc)//剪支
dfs(x,cost,i+1); //继续为人员i+1分配任务
swap(x［i］,x［j］);
cost-=c［i］［x［j］］; //cost回溯
task［x［j］］=false; //task回溯
}
}
}
(2) 算法2：
void dfs(vector<int>&x,int cost,int i) //使用递归算法
{if (i>n) //到达叶子结点
{if (cost<bestc)//比较求最优解
{bestc=cost;
bestx=x;
}
}
else //没有到达叶子结点
{for (int j=1;j<=n;j++) //为人员i试探任务x［j］
{if (task［x［j］］) continue; //若任务x［j］已经被分配，则跳过
swap(x［i］,x［j］); //为人员i分配任务x［j］
task［x［j］］=true;
cost+=c［i］［x［j］］;
if(bound(x,cost,i)<bestc)//剪支
dfs(x,cost,i+1); //继续为人员i+1分配任务
cost-=c［i］［x［j］］; //cost回溯
task［x［j］］=false; //task回溯
swap(x［i］,x［j］);
}
}
}
5.4.3算法设计题
1. 给定含n个整数的序列a(其中可能包含负整数)，设计一个算法从中选出若干整数，使它们的和恰好为t。例如，a=(-1，2，4，3，1)，t=5，求解结果是(2，3，1，-1)，(2，3)，(2，4，-1)和(4，1)。
2. 给定含n个正整数的序列a，设计一个算法从中选出若干整数，使它们的和恰好为t并且所选元素个数最少的一个解。
3. 给定一个含n个不同整数的数组a，设计一个算法求其中所有m(m≤n)个元素的组合。例如，a=(1,2,3)，m=2，输出结果是(1，2)，(1，3)和(2，3)。
4. 设计一个算法求1～n中m(m≤n)个元素的排列，要求每个元素最多只能取一次。例如，n=3，m=2的输出结果是(1，2)，(1，3)，(2，1)，(2，3)，(3，1)，(3，2)。
5. 在5.2.4节求n皇后问题的算法中每次放置第i个皇后时，其列号xi的试探范围是1～n，实际上前面已经放好的皇后的列号是不必试探的，请根据这个信息设计一个更高效的求解n皇后问题的算法。
6. 请采用基于排列树的回溯框架设计求解n皇后问题的算法。
7. 一棵整数二叉树采用二叉链b存储，设计一个算法求根结点到每个叶子结点的路径。
8. 一棵整数二叉树采用二叉链b存储，设计一个算法求根结点到叶子结点的路径中路径和最小的一条路径，如果这样的路径有多条，求其中的任意一条。
9. 一棵整数二叉树采用二叉链b存储，设计一个算法产生每个叶子结点的编码。假设从根结点到某个叶子结点a有一条路径，从根结点开始，路径走左分支时用0表示，走右分支时用1表示，这样的0/1序列就是a的编码。
10. 假设一个含n个顶点(顶点编号为0～n-1)的不带权图采用邻接矩阵A存储，设计一个算法判断其中顶点u到顶点v是否有路径。
11. 假设一个含n个顶点(顶点编号为0～n-1)的不带权图采用邻接矩阵A存储，设计一个算法求其中顶点u到顶点v的所有路径。
12. 假设一个含n个顶点(顶点编号为0～n-1)的带权图采用邻接矩阵A存储，设计一个算法求其中顶点u到顶点v的一条路径长度最短的路径，一条路径的长度是指路径上经过的边的权值和。如果这样的路径有多条，求其中的任意一条。
5.5上机实验题
1. 象棋算式
编写一个实验程序exp51求解如图5.26所示的算式，其中每个不同的棋子代表不同的数字，要求输出这些棋子各代表哪个数字的所有解。
图5.26象棋算式
2. 子集和
编写一个实验程序exp52，给定含n个正整数的数组a和一个整数t，如果a中存在若干个整数(至少包含一个整数)的和恰好等于t，说明有解，否则说明无解。要求采用相关数据进行测试。
3. 迷宫路径
编写一个实验程序exp53采用回溯法求解迷宫问题。给定一个m×n个方块的迷宫，每个方块值为0时表示空白，为1时表示障碍物，在行走时最多只能走到上、下、左、右相邻的方块。求指定入口s到出口t的所有迷宫路径和其中一条最短路径。
4. 哈密顿回路
编写一个实验程序exp54求哈密顿回路。给定一个无向图，由指定的起点前往指定的终点，途中经过所有其他顶点且只经过一次，称为哈密顿路径，闭合的哈密顿路径称作哈密顿回路。设计一个回溯算法求无向图的所有哈密顿回路，并用相关数据进行测试。
5.6在线编程题
1. LeetCode216——组合总和Ⅲ
2. LeetCode39——组合总和
3. LeetCode131——分割回文串
4. HDU1027——第k小的排列
5. HDU2553——n皇后问题
6. HDU2616——杀死怪物
7. POJ3187——向后数字和
8. POJ1321——棋盘问题
9. POJ2488——骑士游历
10. POJ1040——运输问题
11. POJ1129——最少频道数