第5章〓回溯法


















【案例引入】








本章学习目标： 
(1) 掌握解空间的概念、解空间的类型和回溯法的求解过程。

(2) 掌握子集树回溯算法框架以及构造表达式、图着色、子集和、0/1背包和完全背包问题等经典回溯算法设计方法。

(3) 掌握排列树回溯算法框架以及n皇后、任务分配和旅行商问题等经典回溯算法设计方法。

(4) 灵活运用回溯法算法策略解决复杂问题。




5.1回溯法概述
5．1．1问题的解空间


扫一扫



视频讲解


回溯法(backtracking)类似于穷举法，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时就“回溯”(即回退)，尝试其他路径，所以回溯法有“通用的解题法”之称。一个复杂问题的解决方案是由若干个小的决策步骤组成的决策序列，其解可以表示成解向量x={x0，x1，…，xn-1}，其中分量xi对应第i步的选择，通常可以有两个或者多个取值，表示为xi∈Si，Si为xi的取值候选集。x中各个分量xi的所有取值的组合构成问题的解向量空间，简称为解空间(solution space)，由于解空间一般是一棵树结构，所以也称为解空间树。解空间树中的每个结点确定了所求问题的一个状态(state)，因此解空间树也称为状态空间。求解问题的每一步决策对应于解空间树的一个分支结点，而一系列决策求解过程对应着解空间树的生长过程，在许多情况下问题的最终解都会呈现在这棵解空间树的叶子结点上，对应解的结点称为解结点，从根结点到解结点的路径称为解路径，解路径上所有xi分量的取值确定了问题的一个解。

例如，对于第2章中表2．1所示的0/1背包问题，状态为(cw，cv，i)，表示考虑物品i时当前选择物品的总重量和总价值分别是cw和cv，对应的解空间树如图5．1所示，根结点是(0，0)，i为结点的层次(这里层次从0开始)，为了简便，结点中没有标注i值。解结点是叶子结点(6，8)，表示最大价值是8，从根结点到解结点对应的解向量x={0，1，1，1}，表示一个装入方案是选择物品1、2和3。



图5．10/1背包问题的解空间树


归纳起来，解空间树的一般结构如图5．2所示，根结点(为第0层)的每个分支对应分量x0的一个取值(或者说x0的一个决策)，若x0的候选集为S0={v0,1，…，v0,a}，即根结点的子树个数为|S0|，例如x0=v0,0时对应第1层的结点A0，x0=v0,1时对应第1层的结点A1，…。对于第1层的每个结点Ai，Ai的每个分支对应分量x1的一个取值，若x1的取值候选集为S1={v1,0，…，v1,b}，Ai的分支数为|S1|，例如对于结点A0，当x1=v1,0时对应第2层的结点B0，…。以此类推，最底层是叶子结点层，叶子结点的层次为n，解空间树的高度为n+1。从中看出第i层的结点对应xi的各种选择，从根结点到每个叶子结点有一条路径，路径上的每个分支对应一个分量的取值，这是理解解空间树的关键。



图5．2解空间树的一般结构


从形式化角度看，解空间树是S0×S1×…×Sn-1的笛卡儿积，例如当|S0|=|S1|=…|Sn-1|=2时解空间是一棵高度为n+1的满二叉树。需要注意的是，问题的解空间是虚拟的，并不需要在算法运行中真正地构造出整棵树结构，然后在该解空间中搜索问题的解。实际上，有些问题的解空间因为过于复杂或结点过多难以画出来。

5．1．2什么是回溯法

用回溯法求解的问题通常分为两种类型，一种类型是给定一个约束函数，需要求所有满足约束条件的解，称为求所有解类型，例如求幂集问题中的每一个子集都是一个解； 另外一种类型是除了约束条件以外还包含目标函数，最后是求使目标函数值最大或最小的最优解，称为求最优解类型(或优化问题)，例如0/1背包问题属于求最优解类型。这两类问题本质上是相同的，因为只有求出所有解再按目标函数进行比较才能求出最优解。

从前面的讨论看出问题的解包含在对应的解空间树中，剩下的事情就是在解空间树中搜索满足约束条件的解。所谓回溯法就是在解空间树中采用深度优先搜索方法从根结点出发搜索解，与树的先根遍历类似，当搜索到某个叶子结点时对应一个可能解，如果同时又满足约束条件，则该可能解是一个可行解。所以一个可行解就是从根结点到对应叶子结点的路径上所有分支的取值，例如一个可行解为(a0，a1，…，an-1)，其图示如图5．3所示，在解空间中搜索到可行解的部分称为搜索空间。简单地说，回溯法采用深度优先搜索方法寻找根结点到每个叶子结点的路径，判断对应的叶子结点是否满足约束条件，如果满足该路径就构成一个解(可行解)。

回溯法在搜索解时首先让根结点成为活结点，所谓活结点是指自身已生成但其孩子结点还没有全部生成的结点，同时也成为当前的扩展结点，所谓扩展结点(E结点)是指正在产生孩子结点的结点。在当前的扩展结点处沿着纵深方向移至一个新结点，这个新结点又成为新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点，所谓死结点是指其所有孩子结点均已产生的结点，此时应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

如图5．4所示，从结点A扩展出子结点B(用实线箭头表示)，从结点B继续扩展，当结点B的所有子结点扩展完毕，结点B变为死结点，从结点B回退到结点A(即回溯，用虚线箭头表示)，通过回溯使结点A恢复为扩展结点B之前的状态，再扩展出子结点C，此时开始做结点C的扩展，结点C就是扩展结点，由于结点A可能还有尚未扩展的其他子结点，结点A仍是活结点。




图5．3求解的搜索空间





图5．4解空间树的搜索过程



简单地说，回溯法就是采用深度优先搜索方法搜索解空间树，并随时判定当前结点是否满足解题要求，满足要求时继续向下搜索，不满足要求时则回溯到树的上一层继续搜索另一棵子树，直到找到问题的解为止。采用回溯法的算法称为回溯算法。设计回溯算法的关键点有以下3个：

(1) 根据问题的特性确定结点是如何扩展的，不同的问题扩展方式是不同的。

(2) 在解空间中按什么方式搜索解，实际上树的遍历主要有先根遍历和层次遍历，前者就是深度优先搜索(DFS)，后者就是广度优先搜索(BFS)。回溯法就是采用深度优先搜索解，第6章介绍的分支限界法则是采用广度优先搜索解。

(3) 解空间通常十分庞大，如果要高效地找到问题的解，通常采用一些剪支的方法实现。

所谓剪支就是在解空间中搜索时提早终止某些分支的无效搜索，减少搜索的结点个数但不影响最终结果，从而提高了算法的时间性能。常用的剪支策略如下。

(1) 可行性剪支： 在扩展结点处剪去不满足约束条件的分支。例如，在0/1背包问题中，如果选择物品i会导致总重量超过背包容量，则终止选择物品i的分支的继续搜索。

(2) 最优性剪支： 用限界函数剪去得不到最优解的分支。例如，在0/1背包问题中，如果沿着某个分支走下去无论如何都不可能得到比当前解bestv更大的价值，则终止该分支的继续搜索。

(3) 改变搜索的顺序： 在搜索中改变搜索的顺序，比如原先是递减顺序，可以改为递增顺序，或者原先是无序，可以改为有序，这样可能会减少搜索的总结点。

严格来说改变搜索的顺序并不是一种剪支策略，而是一种对搜索方式的优化。前两种剪支策略采用的约束函数和限界函数统称为剪支函数。归纳起来，回溯法可以简单地理解为深度优先搜索加上剪支。因此用回溯法求解的一般步骤如下：

(1) 针对给定的问题确定其解空间，其中一定包含所求问题的解。

(2) 确定结点的扩展规则。

(3) 采用深度优先搜索方法搜索解空间树，并在搜索过程中尽可能采用剪支函数避免无效搜索。

5．1．3回溯算法分析

通常以回溯法的解空间树中的结点个数作为算法的时间分析依据。假设解空间树共有n+1层(根结点为第0层，叶子结点为第n层)，第1层有m0个结点，每个结点有m1个子结点，则第2层有m0m1个结点，同理，第3层有m0m1m2个结点，以此类推，第n层有m0m1…mn-1个结点，则采用回溯法求所有解的算法的执行时间为T(n)=m0+m0m1+m0m1m2+…+m0m1m2…mn-1。这是一种最坏情况下的时间分析方法，在实际中可以通过剪支提高性能。为了使估算更精确，可以选取若干条不同的随机路径，分别对各随机路径估算结点总数，然后取这些结点总数的平均值。在通常情况下回溯法的效率高于穷举法。

5.2基于子集树的回溯算法框架
5．2．1解空间树的类型

解空间树通常有两种类型。当所给的问题是从n个元素的集合S中找出满足某种条件的子集时，相应的解空间树称为子集树(subset tree)，如图5．1所示的解空间树就是一棵子集树。当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树(permutation tree)，5.10节中介绍的求全排列的解空间树就是排列树。

5．2．2求幂集

求幂集问题的解空间树是最经典的子集树，由此导出子集树的回溯算法框架。为了通用，将求幂集问题改为求含不同整数的集合的所有子集。

问题描述： 有一个含n个不同整数的数组a，设计一个算法求其所有子集(幂集)。例如，a={1，2，3}，所有子集是{{1，2，3}，{1，2}，{1，3}，{1}，{2，3}，{2}，{3}，{}}(输出顺序任意)。


扫一扫



视频讲解


解法1： 设a={a0，…，ai，…，an-1}，解向量为x={x0，…，xi，…，xn-1}，其中xi=0表示不选择a［i］，xi=1表示选择a［i］，这里x的固定长度为n。当已经生成解向量的{x0，…，xi-1}部分后，再由{ai，…，an-1}产生解向量的{xi，…，xn-1}部分。这样用(i，x)表示状态，解空间树的根结点对应状态(i=0，x的元素均为0)，目标状态是(i=n，x为一个解)。从状态(i，x)可以扩展出两个状态(即二选一)：

(1) 选择a［i］元素下一个状态为(i+1，x［i］=1)。

(2) 不选择a［i］元素下一个状态为(i+1，x［i］=0)。

在一条搜索路径上i总是递增的，所以不会出现状态重复的情况。对应的回溯算法如下：



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 pset1(vector<int> &a) {				　　//求幂集算法1

int n=a.size();

x=vector<int>(n);

dfs(a,0);

}



求解a={1，2，3}的解空间树如图5．5所示，图中方框旁边的“(数字)”表示递归调用次序，从中看出结点层次i(从0开始)与当前考虑的元素ai(选择或者不选择ai)的下标是一致的，同时每个叶子结点对应一个解，而且每个解对应的解向量的长度相同。



图5．5求解a={1，2，3}的解空间树


pset1算法分析： 在对应的解空间树中，每个层次为i(i从0开始)的分支结点对应元素a［i］的选择和不选择两种情况，所以解空间树是一棵高度为n+1的满二叉树，叶子结点共有2n个，每个叶子结点对应一个解，输出一个解的时间为O(n)，所以算法的最坏时间复杂度为O(n×2n)。

扫一扫


视频讲解




解法2： 设a={a0，…，ai，…，an-1}，解向量x={x0，…，xi，…，xm-1}改为直接存放a的一个子集(m为x的长度，0≤m≤n)，例如，n=3，a={1，2，3}，x={1}或者x={1，3}等都是该问题的解。从递归角度出发，设f(i)表示求以ai开头的子集，首先空集{}肯定是一个子集。

(1) 求以a0开头的子集，f(0)={a0}∪{a0合并f(1)的每个元素}∪{a0合并f(2)的每个元素}={{1}，{1，2}，{1，2，3}，{1，3}}。

(2) 求以a1开头的子集，f(1)={a1}∪{a1合并f(2)的每个元素}={{2}，{2，3}}。

(3) 求以a2开头的子集，f(2)={a2}={{3}}。

也就是说求f(i)的递推公式如下：
f(i)={ai}∪i<j<n{ai合并f(j)的每个元素}
则a的幂集为∪n-1i=0f(i)。例如a={1，2，3}的全部子集就是如图5．6所示的递归树中的所有结点。



图5．6求a={1，2，3}的幂集


上述递推公式直接采用递归算法实现时性能较低(其中存在重复子问题的计算)，这里采用回溯算法，用(i，j，x)表示状态(其中x为解向量)，解空间中根结点的状态为(0，0，{})，用j1遍历a［j．．n-1］： 置x［i］=a［j1］，下一层的结点状态为(i+1，j1+1，x)。例如，a={1，2，3}，求其幂集的解空间如图5．7所示。



图5．7求a={1，2，3}幂集的解空间


对应的回溯算法如下：



int x［MAXN］;//解向量

void disp(int i) {									　　//输出一个解

printf("  {");

for (int k=0;k<i;k++)

printf("%d ",x［k］);

printf("}");

}

void dfs(vector<int> &a,int i,int j) {	　　//回溯算法

disp(i);											　　//输出一个解x［0．．i-1］

for(int j1=j;j1<a.size();j1++) {





x［i］=a［j1］;

dfs(a,i+1,j1+1);

x［i］=-1;										　　//回溯

}

}

void pset2(vector<int> &a) {				　　//求幂集算法2

dfs(a,0,0);

}



解空间中第i层的结点(i，j，x)就是为xi(i≤j)选择{aj，…，an-1}中的一个元素，即n-j选一，如图5．8所示。



图5．8xi可以选择a［j．．n-1］中的任意元素


解向量x用vector向量表示，由于参数i与解空间中对应结点的层次相同，所以可以省略参数i，对应的回溯算法如下：



vector<int> x;//解向量

void disp(vector<int> &x) {					　　//输出一个解(子集)

printf("  {");

for (int k=0;k<x.size();k++)

printf("%d ",x［k］);

printf("}");

}

void dfs(vector<int> &a,int j) {				　　//回溯算法

disp(x);												　　//输出对应的解

for(int j1=j;j1<a.size();j1++) {				　　//j1≥j

x.push_back(a［j1］);

dfs(a,j1+1);

x.pop_back();

}

}

void pset2(vector<int> &a) {				　　//求幂集算法2

dfs(a,0);

}




pset2算法分析： 在对应的解空间树中恰好有2n个结点，每个结点都是解结点，输出一个解的时间为O(n)，所以算法的最坏时间复杂度为O(n×2n)。

说明： pset1和pset2两个算法的差异如下。

(1) pset1采用固定的二选一，结点层次i与当前考虑元素ai的下标一致，算法简单，方便理解，而pset2采用多选一，算法设计相对复杂。

(2) pset1解空间树中的结点个数几乎是pset2解空间树中结点个数的两倍，一般来说解空间树中的结点个数越少则算法的时空性能越好，所以pset2的性能好于pset1。

(3) pset1求出的全部子集是无序的，而pset2求出的全部子集是有序的，即除了第一个空集以外，首先输出以a［0］为首元素的所有子集，接着是以a［1］为首元素的所有子集，以此类推，如果求解问题要求有序性，应该采用以pset2为基础的回溯算法。


扫一扫



视频讲解


【例5．1】子集Ⅱ(LintCode18★★)。给定一个可能具有重复数字的数组nums，设计一个算法返回其所有可能的子集，子集中的每个元素都是非降序的，两个子集间的顺序是无关紧要的，解集中不能包含重复子集。例如，nums={1，2，2}，答案是{{2}，{1}，{1，2，2}，{2，2}，{1，2}，{}}。要求设计如下成员函数：





扫一扫


源程序





vector<vector<int> > subsetsWithDup(vector<int> &nums) { }




解法1： 利用5．2．2节中pset1算法的思路求解，先对nums递增排序，由于nums中存在重复元素，结果子集也一定重复，这里采用set容器实现去重，最后将set中的子集复制到vector<vector<int>>容器ans中，返回ans即可。


扫一扫


源程序


解法2： 利用5．2．2节中pset2算法的思路求解，先对nums递增排序，在考虑求以nums［i］开头的子集时，用j遍历nums［i．．n-1］，xi取a［j］值，如果跳过nums［j］=nums［j-1］(j>i)的nums［j］便可以实现去重。


5．2．3子集树回溯算法框架

设问题的解是一个n维向量{x0，x1，…，xn-1}，约束函数表示每个分量xi应满足的约束条件，记为constraint(xi)； 限界函数记为bound(xi)，一般地，解空间为子集树的递归回溯框架如下：



int x［n］;	//解向量，全局变量

void dfs(int i)	{									　　//子集树的递归框架

if(i>=n)											　　//搜索到叶子结点

产生一个可能解;

else {

for (j=下界;j<=上界;j++)	{ 			　　//用j枚举x［i］所有可能的选择

x［i］=j;									　　//产生一个可能的解分量

…											　　//其他操作

if (constraint(i) && bound(i))

dfs(i+1);							　　//满足约束条件和限界函数,继续下一层

}

}

}



采用上述算法框架需要注意以下几点：

(1) i从0开始调用上述回溯算法框架，此时根结点为第0层，叶子结点为第n层。当然i也可以从1开始，这样根结点为第1层，叶子结点为第n+1层，需要将上述代码中的“if(i>=n)”改为“if (i>n)”。

(2) 在上述框架中通过for循环用j枚举x［i］所有可能的路径，如果扩展路径只有两条，可以改为两次递归调用(例如求解0/1背包问题、子集和问题等都是如此)。

(3) 这里回溯框架只有i一个参数，在实际应用中可以根据具体情况设置多个参数。

5.3图的路径搜索
问题描述： 给定一个含n个顶点的带权无向图以及图中两个顶点s和t，设计一个算法求s到t的所有路径及其路径长度。

解假设带权无向图采用邻接矩阵存放。例如如图5．9(a)所示的带权无向图的邻接矩阵如下：
A=05∞1∞
50∞∞∞
∞∞023
1∞208
∞∞380



图5．9一个带权无向图及其解空间树



现在求从顶点s到顶点t的所有路径(默认为简单路径)，这是一个求所有解的问题，约束条件就是s→t的路径，由于路径是一个顶点序列，所以对应的解向量x={x0，x1，…，xk-1}表示一条路径。下面以s=0，t=4为例进行讨论，x0=0(没有其他选择)，需要求出满足约束条件的其他xi(i≥1)，这里的路径有多条，每条路径对应一个解向量，对应的解空间树如图5．9(b)所示，图中的i表示结点的层次，由于x0是固定的，只需要从x1开始求，根结点的层次i=1，从中看出S1={1，3}，S2={2，4}，S3={4}，其中包含该问题的两个解x={0，3，2，4}和x={0，3，4}。

说明： 在本问题中结点的扩展就是从对应的顶点找所有相邻顶点，即多选一，对应的解空间树属于子集树，由于找到的路径长度不一定相同，所以解向量并不是固定长度的。

为了避免路径中出现重复的顶点，采用visited数组判重，在邻接搜索中跳过当前路径中已经出现的顶点。这里还需要求路径长度，为了简单，将路径长度存放在x的末尾。对应的回溯算法如下：



const int INF=0x3f3f3f3f;

int n=5;

vector<vector<int>> A={{0,5,INF,1,INF},{5,0,INF,INF,INF},　　//邻接矩阵

{INF,INF,0,2,3},{1,INF,2,0,8},{INF,INF,3,8,0}};

vector<vector<int>> ans;													　　//存放答案

vector<int> x;																	　　//解向量

vector<int> visited;

void dfs(int i,int curlen,int t) {											　　//回溯算法

if (i==t) {																	　　//找到终点

ans.push_back(x);													　　//将x添加到ans中

ans.back().push_back(curlen);									　　//在路径的末尾添加路径长度

}

else {

for (int j=0;j<n;j++) {

if(i==j || A［i］［j］==INF) continue;							　　//剪支: 跳过没有边的顶点

if (visited［j］) continue;											　//剪支:跳过在路径中的顶点

visited［j］=1;														　　//x［i］选择顶点j

x.push_back(j);													　　//置访问标记

curlen+=A［i］［j］;													　　//增加路径长度

dfs(j,curlen,t);														　　//继续搜索





curlen-=A［i］［j］;													　　//路径长度回溯

x.pop_back();														　　//路径回溯

visited［j］=0;														　　//访问标记回溯

}

}

};

void allpath(int s,int t) {													　　//求解算法

x.push_back(s);

visited=vector<int>(n,0);

visited［s］=1;

dfs(s,0,t);																	　　//i从0开始

printf("从%d到%d的所有路径:＼n"); 							　　//输出结果

for(int i=0;i<ans.size();i++) {

printf("  路径%d: 长度=%d, 路径:",i+1,ans［i］.back());

for(int j=0;j<ans［i］.size()-1;j++)

printf(" %d",ans［i］［j］);

printf("＼n");

}

}



调用allpath(0,4)的求解结果如下：



从0到4的所有路径:

路径1: 长度=6, 路径: 0 3 2 4

路径2: 长度=9, 路径: 0 3 4




扫一扫



视频讲解


allpath算法分析： 在算法中调用dfs(s，0，t)，考虑最坏情况，s到t的路径为(s，x1，…，xn-2，t)，xi可以是除了s和t以外的任意不重复的顶点，所以最坏时间复杂度为O（(n-2)!)。

【例5．2】路径搜索(LintCode1647★★)。给定一个有n(n≤10)个顶点、m(m≤50)条边的无向图，顶点的编号是0~n-1，设计一个算法输出从s点出发到达t点的所有简单路径，输出的简单路径按字典序排序。


图5．10一个无向图

当一条路径不会经过某个顶点超过一次时，称之为简单路径。例如，n=4，g={{0，1}，{0，2}，{1，2}，{1，3}，{3，2}}，s=0，t=2，对应的图如图5．10所示，从0到2有3条路径，按字典序输出的结果是{{0，1，2}，{0，1，3，2}，{0，2}}。要求设计如下成员函数：



vector<vector<int>> getPath(int n,vector<vector<int>> &g,int s,int t) { }




扫一扫



源程序


解法1： 给定的无向图采用邻接矩阵A存放，采用本节前面讨论的路径搜索方法求解，在搜索顶点i的相邻点j时，j以从0到n-1的顺序试探，所以当s到t有多条路径时会按照字典序找到这些路径。



图5．11邻接表G


扫一扫



源程序


解法2： 给定的无向图采用邻接表G存放，G的类型为vector<vector<int>>，G［i］表示顶点i的所有出边邻接点，例如图5．10所示的无向图对应的邻接表G如图5．11所示。

由于需要按字典序输出s到t的所有路径，所以要保证G［i］中的元素按顶点编号递增排列，采用的方法是在创建G［i］后调用sort()实现排序，其他与解法1相同。

5.4构造表达式

扫一扫


视频讲解


问题描述： 设计一个算法在1、2、……、9(顺序不能变)数字之间插入+或-或什么都不插入，使得计算结果总是100，并求所有的可能性。例如1+2+34-5+67-8+9=100。



图5．12表达式示意图

解用数组a存放1~9的整数，设计解向量x，x［i］表示在a［i］前面插入的运算符，其示意图如图5．12所示。x［i］只能取值'+'、'-'或者空格(三选一)。设计回溯算法dfs(sum，prev，i)，其中sum表示考虑x［i］取值时前面表达式的计算结果(初始值为a［0］)，prev表示考虑x［i］取值时前面的运算数(初始值为a［0］)，i从1开始(a［0］前面没有运算符)：

(1) 若x［i］取值'+'，sum+=a［i］，prev=a［i］，继续搜索下一层，返回时恢复sum和prev。

(2) 若x［i］取值'-'，sum-=a［i］，prev=-a［i］，继续搜索下一层，返回时恢复sum和prev。

(3) 若x［i］取值' '，则需要合并整数，例如prev=2，a［2］=3，若x［2］取值' '，合并的整数是23。如prev=-2，a［2］=3，若x［2］取值' '，合并的整数是-23，所以需要先执行sum-=prev减去前面的元素值，再执行tmp=prev*10±a［i］(±为原prev的符号)得到合并的整数，最后执行sum+=tmp得到合并结果(tmp为新的前面的运算数)，继续搜索下一层，返回时恢复sum和prev。


当i=9时到达一个叶子结点，若sum=100对应一个解，构造对应的表达式并添加到ans中，最后输出ans。对应的算法如下：



#define N 9

int a［N］;

vector<string> ans;//存放答案

char x［N］;												　　//解向量

void dfs(int sum,int prev,int i) {				　　//回溯算法

if (i==N) {											　　//到达一个叶子结点

if (sum==100) {								　　//找到一个解

string s=to_string(a［0］);

for (int j=1;j<N;j++) {

if (x［j］!=' ') s+=x［j］;

s+=to_string(a［j］);

}

s+="=100";

ans.push_back(s);

}

}

else {

x［i］='+';											　　//在位置i插入'+'

sum+=a［i］;										　　//计算当前表达式的值

dfs(sum,a［i］,i+1);

sum-=a［i］;										　　//回溯

x［i］='-';											　　//在位置i插入'-'





sum-=a［i］;										　　//计算当前表达式的值

dfs(sum,-a［i］,i+1);

sum+=a［i］;										　　//回溯

x［i］=' ';											　　//在位置i插入' '

sum-=prev;										　　//先减去前面的元素值

int tmp;											　　//计算新合并值

if (prev>0)

tmp=prev*10+a［i］;						　　//如prev=2,a［i］=3,结果为23

else

tmp=prev*10-a［i］;						　　//如prev=-2,a［i］=3,结果为-23

sum+=tmp;										　　//计算合并结果

dfs(sum,tmp,i+1);

sum-=tmp;										　　//回溯sum

sum+=prev;

}

}

void express() {

for (int i=0;i<N;i++) a［i］=i+1;				　　//为a赋值1,2，…,9

dfs(a［0］,a［0］,1);									　　//插入位置i从1开始

printf("求解结果＼n");

for(int i=0;i<ans.size();i++)

cout << "  (" << i+1 << ") " << ans［i］ << endl;	

}



调用express算法的输出结果如下：



求解结果

(1) 1+2+3-4+5+6+78+9=100

(2) 1+2+34-5+67-8+9=100

(3) 1+23-4+5+6+78-9=100

…

(11) 123-45-67+89=100




express算法分析： 在整数序列1~9中有8个位置，每个位置可以插入3个运算符之一，所以执行时间为38，如果给定整数是1~n，则时间复杂度为O(3n)。


扫一扫



视频讲解


【例5．3】目标和(LintCode1208★★)。给定一个含n个整数的数组 nums(1≤n≤20，0≤nums［i］≤1000)和一个整数s(-1000≤s≤1000)。在数组中的每个整数前添加 '+' 或 '-'，然后串联起来所有整数，可以构造一个表达式，例如，nums={2，1}，可以在2之前添加 '+'，在1之前添加'-'，然后串联起来得到表达式 "+2-1"。设计一个算法求可以通过上述方法构造的运算结果等于s的不同表达式的数目。要求设计如下成员函数：



int findTargetSumWays(vector<int>& nums, int s) { }




解用ans表示满足要求的解个数(初始为0)，设置解向量x={x0，x1，…，xn-1}，xi表示nums［i］(0≤i≤n-1)前面添加的符号，xi只能在'+'和'-'符号中二选一，所以该问题的解空间为子集树。用expv表示当前运算结果(初始为0)。对于解空间中第i层的结点A，若xi选择'+'，则expv+=nums［i］，若xi选择'-'，则expv-=nums［i］，在回退到A时要恢复expv。当到达一个叶子结点时，如果expv=s，说明找到一个解，置ans++。

由于该问题只需要求最后的解个数，所以不必真正设计解向量x，仅设计expv即可。对应的程序如下：



class Solution {

int ans;//存放解个数

public:





int findTargetSumWays(vector<int>& nums,int s) {

ans=0;

dfs(nums,s,0,0);

return ans;

}

void dfs(vector<int>& nums,int s,int i,int expv) {//回溯算法

if (i==nums.size()) { 　　//到达一个叶子结点

if(expv==s) ans++;　　//找到一个解

}

else {

expv+=nums［i］;　　//nums［i］前选择'+'

dfs(nums,s,i+1,expv);

expv-=nums［i］; 　　//回溯：恢复expv

expv-=nums［i］;  　　//nums［i］前选择'-'

dfs(nums,s,i+1,expv);

expv+=nums［i］;  　　//回溯：恢复expv

}

}

};



上述程序提交时通过，执行用时为163ms，内存消耗为5．59MB。

5.5图的m着色问题

扫一扫



视频讲解


问题描述： 给定一个连通图G和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法可以使G中每条边的两个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是给定图G和m种颜色，找出所有不同的着色方案数。例如，如图5．13所示的无向连通图，m=3时不同的着色方案数为12。



图5．13一个无向连通图


解对于连通图G，采用邻接矩阵A存放，这里的A是一个0/1矩阵。图中的顶点编号为0~n-1，共m种颜色，颜色编号为0~m-1。设计解向量x={x0，x1，…，xn-1}，其中x［i］表示顶点i的着色，图中每个顶点可能的着色为0~m-1(初始时x［i］置为-1表示未着色)，所以有0≤x［i］≤m-1，相当于m选一，对应的解空间是一棵m叉树，高度为n+1。i从0开始，当i=n时对应一个叶子结点，表示找到一种着色方案，将着色方案数ans增1，最后输出ans即可。对应的回溯算法如下：



int n=4;

int A［MAXN］［MAXN］={{0,1,1,1},{1,0,0,0},{1,0,0,1},{1,0,1,0}};

int ans=0;//全局变量，累计解个数

int x［MAXN］;									　　//全局变量，x［i］表示顶点i的着色

bool judge(int i,int j) {					　　//判断顶点i是否可以着色j

for(int k=0;k<n;k++) {

if(A［i］［k］==1 && x［k］==j)		　　//存在相同颜色的顶点

return false;

}

return true;

}

void dfs(int m,int i) {						　　//回溯算法

if (i>=n)										　　//到达一个叶子结点

ans++;									　　//着色方案数增1





else {

for (int j=0;j<m;j++) {				　　//试探每一种着色

x［i］=j;

if (judge(i,j))						　　//可以着色j，进入下一个顶点着色

dfs(m,i+1);

x［i］=-1;								　　//回溯

}

}

}

void color(int m) {							　　//求解算法

memset(x,0xff,sizeof(x));				　　//x初始化所有元素为-1

dfs(m,0);

printf("着色方案数:%d＼n",ans); 

}




color算法分析： 算法中每个顶点试探m种颜色，解空间树是一棵m叉树(子集树)，每个结点判断当前着色是否合适的时间为O(n)，所以算法的时间复杂度为O(n×mn)。


扫一扫



视频讲解


【例5．4】频道分配(POJ1129，时间限制为1000ms，空间限制为10000KB)。在非常大的区域广播时需要利用中继器加强信号，每个中继器使用不同的频道，以便不会相互干扰，给定一个中继器网络的描述，求所需的最小频道数目。

输入格式： 输入包含多个中继器网络描述，每个描述以包含中继器个数的行开头，个数介于1和26之间，中继器由以A开头的连续大写字母表示。例如，10个中继器的名称为A、B、C、……、I和J，输入0表示结束。在中继器个数之后是相邻关系列表，每行具有形如“A: BCDH”的格式，表示中继器B、C、D和H与中继器A相邻，第一行描述与中继器A相邻的中继器，第二行描述与B相邻的中继器，以此类推。如果一个中继器不与任何其他中继器相邻，则形如“A:”。中继器按字母顺序列出。注意相邻关系是对称的，如果A与B相邻，则B必然与A相邻。另外，由于中继器位于一个平面内，连接相邻中继器形成的图形没有任何相交的线段。

输出格式： 对于每个中继器网络描述，输出一行包含所需的最小频道数。样例输出显示了这一行的格式，当只需要一个通道时，请注意通道是单数形式。

输入样例：



2

A:

B:

4

A:BC

B:ACD

C:ABD

D:BC

0



输出样例：



1 channel needed.

3 channels needed.




扫一扫



源程序



解本题的每个中继器网络描述可以建立这样的无向图，每个中继器看成一个顶点，相邻关系用一条无向边表示，如果将边看成着色关系，同一条边的两个顶点不能着相同的元素，这样就转换为图着色问题，用m表示当前颜色数目(颜色编号为0~m-1)，实际上是求m可着色的最小m，用minm表示(初始为∞，实际上4 色定理表明最多4种颜色即可，所以minm可以初始为4)。

同样用x作为解向量(所有元素初始化为-1)，m从0开始试探，与前面讨论的图m着色问题的求解过程相比，在为顶点i选择颜色j时，j从0到m-1循环试探，试探成功就继续走下去，否则回溯，除此之外增加另外一种选择，即增加一种颜色，
置x［i］=m，然后在颜色增加的情况下继续走下去，当i=n时说明找到了一种m着色方案，置minm=min(minm，m)，最后输出minm即可。例如，对于图5．13所示的连通图，求最少颜色数的过程如图5．14所示，图中方框为dfs(m,i),带阴影的结点为解结点，minm=min(3，3，4)=3，说明该图着色所需的颜色数最少为3种。



图5．14求图5．13的最少颜色数的过程



5.6子集和问题

扫一扫



视频讲解


问题描述： 给定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}。

解与求幂集问题一样，该问题的解空间是一棵子集树(因为每个整数要么选择，要么不选择)，并且是求满足约束函数的所有解。

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．15所示，图中结点上的数字表示cs，利用深度优先搜索得到两个解，解向量分别是{1，0，1，0}和{0，1，1，1}，对应图中两个带阴影的叶子结点，图中共31个结点，每个结点都要搜索。实际上，解空间是一棵高度为5的满二叉树，从根结点到每个叶子结点都有一条路径，每条路径是一个决策向量，满足约束函数的决策向量就是一个解向量。



图5．15求a={3，1，5，2}，t=8时子集和的解空间


对应的回溯算法如下：



int n,t;

vector<int> a;										　　//存放所有整数

int cnt=0;											　　//累计解个数

int tot=0;                       	　　//累计搜索的结点个数

vector<int> x;										　　//解向量

void disp() {										　　//输出一个解

printf("  第%d个解,",++cnt);

printf("选取的数为: ");

for (int i=0;i<x.size();i++) {

if (x［i］==1)

printf("%d ",a［i］);

}

printf("＼n");

}

void dfs(int cs,int i) { 						　　//回溯算法

tot++;											　　//累计调用次数

if (i>=n) {										　　//到达一个叶子结点

if (cs==t) disp();							　　//找到一个满足条件的解,输出

}

else {												　　//没有到达叶子结点

x［i］=1;										　　//选取整数a［i］

dfs(cs+a［i］,i+1);

x［i］=0;										　　//不选取整数a［i］

dfs(cs,i+1);

}

}

void subs1(vector<int>&A,int T) {		　　//求解子集和问题

n=A.size();

a=A;

t=T;

x=vector<int>(n);

printf("求解结果＼n");

dfs(0,0);										　　//i从0开始

printf("tot=%d＼n",tot);

}



对于子集和问题A={3，1，5，2}，T=8，调用subs1(A，T)时的输出结果如下：



求解结果

第1个解,选取的数为: 3 5 

第2个解,选取的数为: 1 5 2 

tot=31



subs1算法分析： 对于含n个元素的数组a和正整数t，上述算法的解空间是一棵高度为n+1的满二叉树，共有2n+1-1个结点，递归调用2n+1-1次，每找到一个满足条件的解就调用disp()输出，而执行disp()的时间为O(n)，所以subs()算法的最坏时间复杂度为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．16所示，图中共29个结点，除去两个被剪支的结点(用虚框结点表示)，剩下27个结点，也就是说递归调用27次，性能得到了提高。对应的回溯算法如下：



void dfs(int cs,int i) { //回溯算法

tot++;											　　//累计调用次数

if (i>=n) {										　　//到达一个叶子结点

if (cs==t) disp();							　　//找到一个满足条件的解,输出

}

else {												　　//没有到达叶子结点

if (cs+a［i］<=t) {							　　//左孩子结点剪支

x［i］=1;									　　//选取整数a［i］

dfs(cs+a［i］,i+1);

}

x［i］=0;										　　//不选取整数a［i］

dfs(cs,i+1);

}

}

void subs2(vector<int>&A,int T) {		　　//求解子集和问题

n=A.size();

a=A;

t=T;

x=vector<int>(n);

printf("求解结果＼n");

dfs(0,0);										　　//i从0开始

printf("tot=%d＼n",tot);

}






图5．16求a={3，1，5，2}，t=8时子集和的搜索空间


当A={3，1，5，2}，T=8时调用subs2(A，T)算法的求解结果如下：



求解结果

第1个解,选取的数为: 3 5 

第2个解,选取的数为: 1 5 2 

tot=27



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．17所示，图中共17个结点，除去7个被剪支的结点(用虚框结点表示)，剩下10个结点，也就是说递归调用10次，性能得到更有效的提高。



图5．17求a={3，1，5，2}，t=8时子集和的搜索过程


说明： 本例给定a中的所有整数为正整数，如果a中有负整数，这样的左、右剪支是不成立的，因此无法剪支，算法退化为基本深度优先搜索。

对应的回溯算法如下：



void dfs(int cs,int rs,int i) {//回溯算法

tot++;												　　//累计调用次数

if (i>=n) {											　　//到达一个叶子结点

if (cs==t) disp();								　　//找到一个满足条件的解,输出

}

else {													　　//没有到达叶子结点

rs-=a［i］;											　　//求剩余整数的和

if (cs+a［i］<=t) {								　　//左孩子结点剪支

x［i］=1;										　　//选取整数a［i］

dfs(cs+a［i］,rs,i+1);

}

if (cs+rs>=t) {									　　//右孩子结点剪支

x［i］=0;										　　//不选取整数a［i］

dfs(cs,rs,i+1);

}

rs+=a［i］;										　　//恢复剩余整数的和(回溯)

}





}

void subs3(vector<int>&A,int T) {			　　//求解子集和问题

n=A.size();

a=A;

t=T;

x=vector<int>(n);

int rs=0;												　　//表示所有整数的和

for (int j=0;j<n;j++)								　　//求rs

rs+=a［j］;

printf("求解结果＼n");

dfs(0,rs,0);										　　//i从0开始

printf("tot=%d＼n",tot);

}



当a={3，1，5，2}，T=8时调用subs3(a，T)算法的求解结果如下：



求解结果

第1个解,选取的数为: 3 5 

第2个解,选取的数为: 1 5 2 

tot=10



subs2和subs3算法分析： 尽管通过剪支提高了算法的性能，但究竟剪去多少结点与具体的实例数据相关，所以这样的两个算法在最坏情况下的时间复杂度仍然为O(n×2n)。从上述实例可以看出剪支在回溯算法中的重要性。


扫一扫



视频讲解


【例5．5】目标和(LintCode1208★★)。问题描述参见例5．3。

解不妨用a表示nums数组，先求出a中所有整数的和sum，显然sum<s时即使全部加上'+'也不可能成立，此时返回0(无解)，否则本问题就是求以下等式成立的不同表达式的数目(±表示取'+'或者'-'之一)。
±a［0］±a［1］±…±a［n-1］=s

扫一扫


源程序


用sum减去两边后转换为：
(a［0］+a［1］+…+a［n-1］)-(±a［0］±a［1］±…±a［n-1］)=sum-s
等同于：
(a［0］a［0］)+(a［1］a［1］)+…+(+a［n-1］a［n-1］)=sum-s
对于(a［i］a［i］)部分，如果取'-'(对应原来的'+')则为0，如果取'+'(对应原来的'-')则为2a［i］，考虑只取'+'的部分(其他取'-')，假设对应的下标为i1，i2，…，ik，则为：
2a［i1］+2a［i2］+…+2a［ik］=sum-s，即a［i1］+a［i2］+…+a［ik］=(sum-s)/2
其中i1，i2，…，ik是0，1，…，n-1的一个子序列，

这样该问题等价于在原a数组中选择添加'-'的元素的和等于(sum-s)/2的组合总数，属于典型的子集和问题。由于(sum-s)/2一定是整数，所以(sum-s)为奇数时无解，返回0。采用左、右剪支的回溯算法求解。

5.7简单装载问题


扫一扫



视频讲解


问题描述： 有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。

解与求幂集问题一样，该问题的解空间树是一棵子集树(因为每个集装箱要么选择，要么不选择)，但要求最佳装载方案，属于求最优解类型。设当前解向量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，再对某个搜索结点(cw，rw)做cw+rw>bestw的右剪支，通常比广度优先搜索的性能更好。

当第i层的这个结点扩展完成后需要恢复rs，即置rs+=a［i］(回溯)。如果搜索到某个叶子结点(即i≥n)，得到一个可行解，其选择的集装箱重量和为cw(由于左剪支的原因，cw一定小于或等于t)，若cw>bestw，说明找到一个满足条件的更优解，置bestw=cw，bestx=x。全部搜索完毕，bestx就是最优解向量。对应的递归算法如下：



vector<int> w;

int t;

int n;

vector<int> x;	//解向量

vector<int> bestx;									　　//存放最优解向量

int bestw=0;											　　//存放最优解的总重量，初始化为0

int tot=0;                         	 	　　//累计搜索的结点个数

void dfs(int cw,int rw,int i) { 					　　//回溯算法

tot++;

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,i+1);

cw-=w［i］;									　　//恢复当前所选集装箱的重量和(回溯)

}

if (cw+rw>bestw) {							　　//右孩子结点剪支

x［i］=0;										　　//不选择集装箱i

dfs(cw,rw,i+1);

}

rw+=w［i］;										　　//恢复剩余集装箱的重量和(回溯)

}

}





void loading(vector<int>&W,int T) {//求解简单装载问题

w=W;

t=T;

n=w.size();

int rw=0;

for (int i=0;i<n;i++)								　　//累计全部集装箱的重量和rw

rw+=w［i］;

x=vector<int>(n);

dfs(0,rw,0);											　　//i从0开始

printf("求解结果＼n");

for (int i=0;i<n;i++) {      				　　//输出最优解

if (bestx［i］==1)

printf("  选取第%d个集装箱＼n",i);

}

printf("  总重量=%d＼n",bestw);

printf("tot=%d＼n",tot);

}



当w={5，2，6，4，3}，t=10时调用上述算法的求解结果如下：



求解结果

选取第0个集装箱

选取第1个集装箱

选取第4个集装箱

总重量=10

tot=16



实际上还有另外一个最优解，即选择第2个和第3个集装箱，它们的重量和是相等的。

说明： 在上述dfs算法的左结点扩展中，3条语句cw+=w［i］，dfs(cw,rw,x,i+1)和cw-=w［i］可以用一条语句dfs(cw+w［i］,rw,x,i+1)等价地替换。

loading算法分析： 该算法的解空间树中有2n+1-1个结点，每找到一个更优解时需要将x复制到bestx(执行时间为O(n))，所以在最坏情况下算法的时间复杂度为O(n×2n)。在前面的实例中，n=5，解空间树中结点的个数应为63，采用剪支后结点的个数为16(不计虚框中被剪支的结点)，如图5．18所示。



图5．18装载实例的搜索空间


5.80/1背包问题

扫一扫



视频讲解


问题描述： 问题描述见2．4节。

解该问题的解空间树是一棵子集树(因为每个物品要么选择，要么不选择)，要求价值最大的装入方案，属于求最优解类型。

每个物品包含编号、重量和价值，为此采用结构体数组存放所有物品，后面涉及按单位重量价值递减排序，存放物品的结构体类型如下：



struct Goods {//物品类型

int no;												　　//物品的编号

int w;													　　//物品的重量

int v;													　　//物品的价值

Goods(int no,int w,int v) {					　　//构造函数

this->no=no;

this->w=w;

this->v=v;

}

bool operator<(const Goods&s) const	 {	　　//用于按v/w递减排序

return (double)v/w>(double)s.v/s.w;

}

};



例如，表2．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均设计为全局变量。

1) 左剪支

由于所有物品的重量为正数，采用左剪支与子集和问题类似。当搜索到第i(0≤i<n)层的某个结点时，cw表示当前选择的物品重量和(其中不包含w［i］)。检查当前物品被选中后总重量是否超过W，若超过则剪支，即仅扩展满足cw+w［i］≤W的左孩子结点。

2) 右剪支

这里右剪支相对复杂一些，题目求的是价值最大的装入方案，显然优先选择单位重量价值大的物品，为此将g中所有物品按单位重量价值递减排序，例如表2．1中物品排序后的结果如表5．1所示，序号i发生了改变，后面改为按i而不是按物品编号no的顺序依次搜索。


表5．14个物品按v/w递减排序后的结果



序号i物品编号no重量w价值vv/w

02231．5

11341．3

23111

30540．8


先看这样的问题，对于第i层的某个结点A，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)
也就是说，从结点A出发的所有路径中最大价值为bound(cw,cv,i)=cv+r(i)，如图5．19所示。



图5．19bound(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)												　　//最后物品k=j+1只能部分装入

b+=(double)g［j］.v/g［j］.w*rw;

return b;

}



再回过来讨论右剪支，右剪支是判断不选择物品i时是否能够找到更优解。如果不选择物品i，按上述讨论可知在背包容量允许的前提下依次选择物品i+1、物品i+2、……可以得到最大价值，且从物品i+1开始选择的物品价值和的最大值为r(i+1)。如果之前已经求出一个最优解bestv，当cv+r(i+1)≤bestv时说明不选择物品i后面无论如何也不能够找到更优解。所以当搜索到第i层的某个结点时，对应的右剪支就是仅扩展满足bound(cw,cv,i+1)>bestv的右孩子结点。

说明： 上述bound(cw,cv,i+1)算法中包含物品k的一部分价值，这是不是与0/1背包问题矛盾呢？答案是不矛盾，这里的上界值表示沿着该路径走下去可能装入背包的最大价值，是一种启发搜索信息，并不是真的取物品k的一部分。

例如，对于根结点，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,b=bound(cw,cv,i)，若b≤bestv则停止右分支的搜索，也就是仅扩展满足b>bestv的右孩子结点。

对于表2．1所示的实例，n=4，按v/w递减排序后如表5．1所示，初始时bestv=0，求解过程如图5．20所示，图中两个数字的结点为(cw，cv)，只有右结点标记为(cw，v，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)。



图5．200/1背包问题实例的搜索空间

④  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。

对应的递归算法如下： 



vector<Goods> g; //存放全部物品

int W;                      					　　//背包的容量

int n;                      					　　//物品的个数

vector<int> x;                  				　　//解向量

vector<int> bestx;					      			　　//存放最优解向量

int bestv=0; 						    					　　//存放最大价值,初始为0

int tot=0;													　　//累计搜索的结点个数





double bound(int cw,int cv,int i) {…}			　　//同前

void dfs(int cw,int cv,int i) {  						　　//回溯算法

tot++;													　　//累计调用次数 

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,i+1);

}

double b=bound(cw,cv,i+1);					　　//计算限界函数值

if(b>bestv)	{			          			　　//右剪支

x［i］=0;											　　//不选取物品i

dfs(cw,cv,i+1);

}

}

}

void knap(vector<Goods> g1,int W1) {		　　//求0/1背包问题

g=g1;

W=W1;

n=g.size();

sort(g.begin(),g.end());								　　//按v/w递减排序

x=vector<int>(n,0);

dfs(0,0,0);				                    　　//i从0开始

printf("最佳装填方案＼n");

for (int i=0;i<n;i++) {

if (bestx［i］==1)

printf("  选取第%d个物品＼n",g［i］.no);

}

printf("  总重量=%d,总价值=%d＼n",W,bestv);

}



对于表2．1中的4个物品，W=6时调用上述knap()算法的求解结果如下：



最佳装填方案

选取第2个物品

选取第1个物品

选取第3个物品

总重量=6,总价值=8




knap算法分析： 该算法在不考虑剪支时解空间树中有2n+1-1个结点，求上界函数值和保存最优解的时间为O(n)，所以最坏情况下算法的时间复杂度为O(n×2n)。

5.9*完全背包问题

扫一扫



视频讲解


问题描述： 有n种重量和价值分别为wi、vi(0≤i<n)的物品，从这些物品中挑选总重量不超过W的物品，每种物品可以挑选任意多件，求挑选物品的最大价值。该问题称为完全背包问题。

解法1： 与0/1背包问题不同，完全背包问题中的物品i指的是第i种物品，每种物品可以取任意多件。对于解空间中第i层的结点，用cw、cv表示选择物品的总重量和总价值，这样处理物品i的几种操作方式如下。

(1) 不选择物品i。

(2) 当cw+w［i］≤W时，选择物品i一件，下一步继续选择物品i。

(3) 当cw+w［i］≤W时，选择物品i一件，下一步开始选择物品i+1。

实际上与5．2．2节中求幂集的标准子集树算法1相比，这里仅增加了(2)操作，由于该操作后面又可以选择物品i，从而满足每种物品可以挑选任意多件的条件。正是由于后面的物品可以挑选任意多件，所以无法采用求解0/1背包问题中的右剪支的操作(右剪支是针对不选择当前物品的剪支操作)。

例如，n=2，W=2，w={1，2}，v={2，5}，对应的搜索空间如图5．21所示，结点对应的状态是“(cw，cv，i)”，每个分支结点的3个分支分别进行上述3种处理方式。所有阴影结点是叶子结点，其中深阴影结点是最优解结点，虚框结点为被剪支的结点。



图5．21完全背包问题实例的搜索空间(1)


将n、w、v和W等表示求解问题的变量设置为全局变量，利用上述思路设计的回溯法算法如下：



int bestv=0; //存放最大价值,初始为0

void dfs(int cw,int cv,int i) {    			　　//回溯算法

if(i>=n) {

if(cw<=W && cv>bestv)       	　　//找到一个更优解

bestv=cv;

}

else {

dfs(cw,cv,i+1);             		　　//不选择物品i

if(cw+w［i］<=W)							　　//剪支

dfs(cw+w［i］,cv+v［i］,i);     	　　//选择物品i，然后继续选择物品i

if(cw+w［i］<=W)							　　//剪支

dfs(cw+w［i］,cv+v［i］,i+1);   	　　//选择物品i,然后选下一件

}

}

void completeknap1() {						　　//求完全背包问题

dfs(0,0,0);

printf("最大价值=%d＼n",bestv);

}



解法2： 利用5．2．2节中求幂集的标准子集树算法2的思路，设解向量x={x0，x1，…，xm-1}，解空间树中的第i层结点是为xi在物品j~n-1中选择适合的物品j1(即置xi=j1)，由于后面仍然可以选择物品j1，所以置下一步(求xi+1)选择的物品仍然是j1~n-1。这里只需要求最大价值，不必实际设计解向量x。对应的回溯算法如下：



int bestv=0; //存放最大价值,初始为0

void dfs(int cw,int cv,int j) {    			　　//回溯算法

if(cw<=W && cv>bestv) {      		　　//找到一个更优解

bestv=cv;

}

for (int j1=j;j1<n;j1++) {

if(cw+w［j1］<=W) {						　　//剪支

dfs(cw+w［j1］,cv+v［j1］,j1);    　　//选择物品j1，然后可以继续选择物品j1

}

}

}

void completeknap2() {						　　//求完全背包问题

dfs(0,0,0);

printf("最大价值=%d＼n",bestv);

}



例如，n=2，W=2，w={1，2}，v={2，5}，对应的搜索空间如图5．22所示，结点对应的状态是“(cw，cv，j)”，其中深阴影结点是最优解结点，求出bestv=5，对应的解向量x={1}，表示选择物品1一次。



图5．22完全背包问题实例的搜索空间(2)


5.10基于排列树的回溯算法框架
求全排列问题的解空间树是最典型的排列树，本节通过求全排列导出基于排列树的回溯算法框架，后面介绍相关算法设计示例。

5．10．1求全排列

为了通用，将求全排列问题改为求含不同整数元素的数组的全排列。


扫一扫



视频讲解


问题描述： 有一个含n个不同整数的数组a，设计一个算法求其所有元素的全排列。例如，a={1，2，3}，其全排列是（1，2，3）、(1，3，2)、(2，3，1)、(2，1，3)、(3，1，2)、(3，2，1)(输出顺序任意)。

解法1： 设a={a0，…，ai，…，an-1}，解向量为x={x0，…，xi，…，xn-1}，每个解向量对应a的一个排列，显然xi可以是a［0．．n-1］中的任意元素，即n选一，但所有xi不能重复，为此设计一个used数组，used［i］表示ai是否使用过。解空间树中的第i层结点用于确定xi的值。对应的回溯算法如下：



vector<int> x;//解向量

vector<int> used;							　　//used［i］表示a［i］是否使用过

int cnt=0;										　　//累计排列个数

void disp() {									　　//输出一个解

printf("  %2d {",++cnt);

for (int i=0;i<x.size()-1;i++)

printf("%d,",x［i］);

printf("%d}＼n",x.back());

}

void dfs(vector<int> &a,int i) {		　　//回溯算法

int n=a.size();

if (i>=n) {

disp();

}

else {

for(int j=0;j<n;j++) {

if(used［j］) continue;				　　//剪支：跳过已经使用过的a［j］

x［i］=a［j］;

used［j］=1;							　　//选择a［j］

dfs(a,i+1);							　　//转向解空间树的下一层

used［j］=0;							　　//回溯

x［i］=0;

}

}

}

void perm1(vector<int> &a) {			　　//求全排列算法1

int n=a.size();

x=vector<int>(n);

used=vector<int>(n,0);

dfs(a,0);

}



perm1算法分析： 从表面上看调用的dfs算法中每个结点是n选一，实际上通过剪支操作使得解空间树中的根结点层(i=0)有一个结点，i=1层有n个结点，i=2层有n(n-1)个结点，i=3层有n(n-1)(n-2)个结点，以此类推，最后叶子结点层有n!个结点，对应n!个排列。设总结点个数为C(n)，则：
C(n)=1+n+n(n-1)+n(n-1)(n-2)+…+n!
≈n+n(n-1)+n(n-1)(n-2)+…+n!
=n!1+11!+12!+…+1(n-1)!=n!e-1n!-1(n+1)!-…
=n!e-1=O(n!)
叶子结点个数为n!，也就是C(n)和叶子结点个数同级，而每个叶子结点对应一个解，输出一个解的时间是O(n)，所以算法的时间复杂度为O(n×n!)。

解法2： 改进解法1，首先将a存放到x中，通过交换方式避免使用used数组，简单地说，设解向量为x={x0，…，xi，…，xn-1}，当已经生成解向量的{x0，…，xi-1}部分后，现在产生解向量的{xi，…，xn-1}部分，将xi与其中的每一个元素交换，目的是让xi取所有可能的元素值(由于x0，…，xi-1元素已经使用过，所以xi不能取这些元素值)，采用交换的方式也保证了xi的所有元素不重复。对应的回溯算法如下：



vector<int> x;//解向量

int cnt=0;												　　//累计排列个数

void disp() {											　　//输出一个解

printf("  %2d {",++cnt);

for (int i=0;i<x.size()-1;i++)

printf("%d,",x［i］);

printf("%d}＼n",x.back());

}

void dfs(int i) {										　　//回溯算法

int n=x.size();

if (i>=n) {

disp();

}

else {

for(int j=i;j<n;j++) {

swap(x［i］,x［j］);							　　//交换a［i］与a［j］

dfs(i+1);

swap(x［i］,x［j］);							　　//回溯：交换a［i］与a［j］

}

}

}

void perm2(vector<int> &a) {					　　//求全排列算法2

int n=a.size();

x=vector<int>(n);

for(int i=0;i<n;i++)	x［i］=a［i］;				　　//置x=a

dfs(0);

}



思考题： 在dfs()中如果不执行第二个交换语句（即swap(x［i］,x［j］)）会出现什么问题呢？为什么？

例如a={1，2，3}时，求全排列的过程如图5．23所示，它就是该问题的解空间树，根结点的层次i为0，对于第i层的结点，其子树分别对应x［i］位置选择x［i］、x［i+1］、……、x［n-1］元素。树的高度为n+1，叶子结点的层次是n。



图5．23求a={1，2，3}的全排列的过程


perm2算法分析： 分析同perm1算法，算法的时间复杂度为O(n×n!)。

说明： perm1算法按字典序依次生成全排列，而perm2算法产生的全排列是无序的。

5．10．2排列树回溯算法框架

设问题的解是一个n维向量{x0，x1，…，xn-1}，约束函数表示每个分量xi应满足的约束条件，记为constraint(xi)； 限界函数记为bound(xi)。一般地，解空间为排列树的递归回溯框架如下：



int x［n］;//x为解向量

void dfs(int i) {											　　//求解排列树的递归框架

if(i>=n)													　　//搜索到叶子结点

产生一个可能的解;

else {

for (j=i;j<=n;j++) {								　　//用j枚举i所有可能的路径

…													　　//x［i］选择x［j］的操作

swap(x［i］,x［j］);

if (constraint(i) && bound(i))

dfs(i+1);									　　//满足约束条件和限界函数，进入下一层

swap(x［i］,x［j］);								　　//回溯: 恢复状态

…													　　//回退到第i层结点的操作

}

}

}



同样的几点注意见解空间为子集树的回溯算法框架的说明。

5.11n皇后问题

扫一扫



视频讲解


问题描述： n皇后问题的描述参见第3章中的3．8节。这里采用回溯法求解。

解同样用整数数组q存放n皇后问题的求解结果，即q［i］(0≤i≤n-1)的值表示第i个皇后所在的列号，即该皇后放在(i，q［i］)的位置上。

这里q相当于解向量，显然q［0．．n-1］的取值恰好是0~n-1的某个排列，所以该问题转换为求全排列问题，对于每个排列判断是否为一个解，在采用回溯法时对应的解空间树是一棵排列树，根结点的层次为0，用于确定q［0］（即皇后0的列号），层次为i的结点用于确定q［i］（即皇后i的列号），叶子结点的层次为n，每个叶子结点对应一个解。

对应的基于排列树的回溯算法如下：



int q［MAXN］;//存放n皇后问题的解(解向量)

int cnt=0;													　　//累计解个数

void disp(int n) {  									　　//输出一个解

printf("  第%d个解:",++cnt);

for (int i=0;i<n;i++)

printf("(%d,%d) ",i,q［i］);

printf("＼n");

}

bool valid(int i,int j) {                   　　//测试(i,j)位置能否放置皇后

if (i==0) return true;                    　　//皇后0总是可以放置的

int k=0;

while (k<i) {                          　　//k=1~i-1是已放置了皇后的行

if ((q［k］==j) || (abs(q［k］-j)==abs(i-k)))

return false;

k++;

}

return true;

}

void dfs(int n,int i) {						  			　　//回溯算法

if (i>=n)

disp(n);												　　//所有皇后放置结束,输出一个解





else {

for (int j=i;j<n;j++) {							　　//在第i行上试探每一个列j

swap(q［i］,q［j］);								　　//皇后i放置在q［j］列

if(valid(i,q［i］))								　　//剪支

dfs(n,i+1);

swap(q［i］,q［j］);								　　//回溯

}

}

}

void queen(int n) {										　　//求解n皇后问题

for(int i=0;i<n;i++) q［i］=i;      				　　//初始化q为0~n-1

dfs(n,0);

}




扫一扫


视频讲解


queen(n)算法分析： 该算法对应的解空间树是一棵排列树，结点个数为O(n!)，每个分支调用place算法的时间最多为O(n)，所以算法的时间复杂度为O(n×n!)。


【例5．6】n皇后问题Ⅱ(LintCode34★★)。给定一个整数n(n≤10)，设计一个算法求n皇后问题的解的数量。要求设计如下成员函数：



int totalNQueens(int n) { }





扫一扫



源程序


解与前面的求解n皇后问题的思路完全相同，这里改为仅累计n皇后问题的解个数。


5.12任务分配问题

扫一扫



视频讲解


问题描述： 问题描述见第3章中的3．9节，这里采用回溯法求解。

解n个人和n个任务的编号均用0~n-1表示，设计解向量x=(x0，x1，…，xn-1)，以人为主进行搜索，即xi表示人员i分配的任务编号(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］］，调用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)之前的语句顺序相反)。

现在考虑采用剪支提高性能，该问题是求最小值，所以设计下界函数。当搜索到第i层的某个结点时，前面人员0~人员i-1已经分配好了各自的任务，已经累计的成本为cost，现在要为人员i分配任务，如果为其分配任务x［j］(通过swap(x［i］,x［j］)语句实现)，即置x［i］=x［j］，cost+=c［i］［x［i］］，此时部分解向量为P=(x0，x1，…，xi)。那么沿着该路径走下去的最小成本是多少呢？后面人员i+1~n-1尚未分配任务，如果为每个人员分配一个尚未分配的最小成本的任务(其总成本为minsum)，则一定会构成该路径的总成本下界。minsum的计算公式如下：
minsum=∑n-1i1=i+1∑n-1j1=0minx［j1］Pci1,x［j1］


图5．24人员i安排任务x［j］的情况

说明： minsum的含义是在c中所有未分配任务的人员行(i+1~n-1行)和未分配的任务表(used［x［j1］］=false)中每行求一个最小值，然后相加得到minsum。

总成本下界b=cost+minsum，如图5．24所示。显然如果b≥bestc(bestc是当前已经求出的一个最优成本)，说明x［i］=j这条路径走下去一定不可能找到更优解，所以停止该分支的搜索。这里的剪支就是仅扩展b<bestc的孩子结点。带剪支的排列树回溯算法如下：





int n;

vector<vector<int>> c;

vector<int> x;//解向量

vector<int> bestx;									　　//最优解向量

int bestc;												　　//最小成本

vector<bool> used; 

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［x［j1］］==false && c［i1］［x［j1］］<minc)

minc=c［i1］［x［j1］］;

}

minsum+=minc;

}

return cost+minsum;

}

void dfs(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］

swap(x［i］,x［j］);							　　//为人员i分配任务x［j］

used［x［i］］=true;

cost+=c［i］［x［i］］;

if(bound(cost,i+1)<bestc)				　　//剪支

dfs(cost,i+1);							　　//继续为人员i+1分配任务

cost-=c［i］［x［i］］;							　　//cost回溯

used［x［i］］=false;							　　//used回溯

swap(x［i］,x［j］);

}

}

}





void allocate(vector<vector<int>> &C) {  　　//求解任务分配问题

c=C;

n=c.size();

x=vector<int>(n);

for(int i=0;i<n;i++)								　　//将x［0．．n-1］分别设置为0到n-1

x［i］=i;

used=vector<bool>(n,false);

bestc=INF;

dfs(0,0);												　　//从人员0开始

printf("最优分配方案＼n");

for (int k=0;k<n;k++)

printf("   人员%d分配任务%d＼n",k,bestx［k］);

printf("   总成本=%d＼n",bestc);

}



对于表3．2所示的任务分配问题，调用上述算法的输出结果如下：



最优分配方案

人员0分配任务1

人员1分配任务0

人员2分配任务2

人员3分配任务3

总成本=13




扫一扫


视频讲解


allocate算法分析： 该算法的解空间树是一棵排列树，结点个数为O(n!)，剪支操作的时间为O(n2)，所以算法的时间复杂度为O(n2×n!)。

【例5．7】订单分配(LintCode1909★★)。问题描述参见例3．8。这里采用回溯法求解。

解与前面讨论的求解任务分配问题类似，仅将求最小成本改为求最大得分。


扫一扫



源程序


5.13旅行商问题

扫一扫



视频讲解


问题描述： 问题描述参见3．10节，这里采用回溯法求解。

解同样城市道路图采用邻接矩阵A存储，起始点为s，设TSP路径（即解向量）x={s，x1，…，xn-1，s}，如图5．25所示，x1~xn-1只能是0~n-1中非s的顶点，对应的TSP路径长度=A［s］［x1］+A［x1］［x2］+…+A［xn-2］［xn-1］+A［xn-1］［s］。也就是说，x1~xn-1是0~n-1(除了s顶点)的一个排列，从而该问题转换为解空间树为排列树的搜索问题。



图5．25一条TSP路径




图5．26TSP问题(s=0)的解空间树

先将s作为x0，这里假设s=0，再将其他非s的顶点的编号添加到x中，从x1开始搜索，用d记录当前的路径长度，对应的解空间树如图5．26所示，对于层次为i的某个结点，j从i到n-1循环，尝试x［i］取值x［j］。

(1) 判断是否有边： 若路径上前一个顶点x［i-1］到顶点x［j］没有边，则跳过该x［j］。

(2) 剪支： 如果x［i］取值x［j］，则当前路径长度d=d+A［x［i-1］］［x［j］］，假如已经求出一个最优路径长度是bestd，当d≥bestd时跳过该x［j］。


通过上述条件后则x［i］取值为x［j］(通过swap(x［i］,x［j］)实现)，然后继续搜索，当到达叶子结点时通过路径长度比较求最优路径bestx和长度bestd，最后输出最优解。

对应的回溯算法如下：



vector<int> x;//解向量(路径) 

vector<int> bestx;　　//保存最短路径

int d;　　//x路径的长度

int bestd=INF;　　//保存最短路径长度

void dfs(vector<vector<int>> &A,int s,int i) {　　//回溯算法

int n=A.size();

if(i>=n) {　　//到达一个叶子结点

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］);

d+=A［x［i-1］］［x［i］］;

dfs(A,s,i+1);

d-=A［x［i-1］］［x［i］］;

swap(x［i］,x［j］);

}

}

}

}

}

void TSP(vector<vector<int>> &A,int s) {　　//求解TSP(起始点为s)

int n=A.size(); 

x.push_back(s);//添加起始点s

for(int i=0;i<n;i++) {　　//将非s的顶点添加到x中

if(i!=s) x.push_back(i);

}

d=0;

dfs(A,s,1);　　//从x［1］开始求解

printf("  最短路径:  ");　　//输出最短路径

for (int j=0;j<bestx.size();j++) {

if(j==0)

printf("%d",bestx［j］);

else

printf("->%d",bestx［j］);





}

printf("＼n  路径长度:  %d＼n",bestd);

}



针对第3章中的图3．14，设置起始点s=0，调用上述算法的求解结果如下：



最短路径:  0->2->3->1->0

路径长度:  23




扫一扫


视频讲解


思考题： 为了提高回溯算法的时间性能，还可以采用哪些剪支方法？

TSP算法分析： 在算法中求x1~xn-1共n-1个元素的全排列，解空间中的结点个数为O((n-1)!)，叶子结点的个数同级，到达叶子结点时进行路径长度的比较并执行bestx=x实现路径复制的时间为O(n)，所以算法的时间复杂度为O(n×(n-1)!)，即O(n!)。


扫一扫


源程序


【例5．8】旅行计划(LintCode1891★★)。问题描述参见第3章中的例3．9，这里采用回溯法求解。


解采用与前面用回溯法求解旅行商问题完全相同的思路，设置起始点s=0。

5.14练习题

扫一扫



自测题


1． 简述回溯算法中主要的剪支策略。

2． 简述回溯法中常见的两种类型的解空间树。

3． 鸡兔同笼问题是一个笼子里面有鸡和兔子若干只，数一数，共有a个头、b条腿，求鸡和兔子各有多少只？假设a=3，b=8，画出对应的解空间树。

4． 考虑子集和问题，n=3，a={1，3，2}，t=3，回答以下问题：

(1) 不考虑剪支，画出求解的搜索空间和解。

(2) 考虑左剪支(选择元素)，画出求解的搜索空间和解。

(3) 考虑左剪支(选择元素)和右剪支(不选择元素)，画出求解的搜索空间和解。

5． 考虑n皇后问题，其解空间树为由1、2、……、n构成的n!种排列组成，现用回溯法求解，要求：

(1) 通过解搜索空间说明n=3时是无解的。

(2) 给出剪支操作。

(3) 最坏情况下在解空间树上会生成多少个结点？分析算法的时间复杂度。

6． 二叉树的所有路径(LintCode480★)。给定一棵二叉树，设计一个算法求出从根结点到叶子结点的所有路径。例如，对于如图5．27所示的二叉树，答案是{"1->2->5"，"1->3"}。要求设计如下成员函数：



vector<string> binaryTreePaths(TreeNode *root) { }






图5．27一棵二叉树

7． 二叉树的最大路径和Ⅱ(LintCode475★★)。给定一棵二叉树，设计一个算法找到二叉树的最大路径和，路径必须从根结点出发，路径可在任意结点结束，但至少包含一个结点(也就是根结点)。要求设计如下成员函数：



int maxPathSum2(TreeNode *root) {}



8． 求组合(LintCode152★★)。给定两个整数 n 和 k，设计一个算法求从1~n中选出k个数的所有可能的组合，对返回组合的顺序没有要求，但一个组合内的所有数字需要是升序排列的。例如，n=4，k=2，答案是{{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{3，4}}。要求设计如下成员函数：



vector<vector<int>> combine(int n，int k) { }



9． 最小路径和Ⅱ(LintCode1582★★)。给出一个m×n的矩阵，每个点有一个正整数的权值，设计一个算法从(m-1，0)位置走到(0，n-1)位置(可以走上、下、左、右4个方向)，找到一条路径使得该路径所经过的权值和最小，返回最小权值和。要求设计如下成员函数：



int minPathSumII(vector<vector<int>> &matrix) {}



10． 递增子序列(LeetCode491★★)。给定一个含n(1≤n≤15)个整数的数组 nums(100≤nums［i］≤100)，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素，可以按任意顺序返回答案。数组中可能含有重复元素，如果出现两个整数相等，也可以视作递增序列的一种特殊情况。例如，nums={4，6，7，7}，答案是{{4，6}，{4，6，7}，{4，6，7，7}，{4，7}，{4，7，7}，{6，7}，{6，7，7}，{7，7}}。要求设计如下成员函数：



vector<vector<int>> findSubsequences(vector<int>& nums) {}



11． 给表达式添加运算符(LeetCode282★★★)。给定一个长度为n(1≤n≤10)的仅包含数字0~9的字符串num和一个目标值整数target(-231≤target≤231-1)，设计一个算法在num的数字之间添加二元运算符(不是一元)+、-或*，返回所有能够得到 target 的表达式。注意所返回表达式中的运算数不应该包含前导零。例如，num="105"，target=5，答案是{"1*0+5"，"10-5"}。要求设计如下成员函数：



vector<string> addOperators(string num，int target) { }



12． 求解马走棋问题。在m行n列的棋盘上有一个中国象棋中的马，马走“日”字且只能向右走。设计一个算法,求马从棋盘的左上角(1，1)走到右下角(m，n)的可行路径的条数。例如，m=4，n=4的答案是2。

13． 设计一个回溯算法求迷宫中从入口s到出口t的最短路径及其长度。

14． 设计一个求解n皇后问题的所有解的迭代回溯算法。

15． 题目描述见第3章中3．11节的第12题，这里要求采用回溯法求解。

5.15在线编程实验题
1．  LintCode1353——根结点到叶子结点求和★★

2．  LintCode802——数独★★★

3． LintCode135——数字组合★★

4．  LintCode1915——举重★★★

5． LintCode680——分割字符串★★

6． LintCode136——分割回文串★★

7． LintCode816——旅行商问题★★★

8． LeetCode784——字母大小写全排列★★

9． LeetCode1079——活字印刷★★

10． LeetCode93——复原IP地址★★

11． LeetCode22——括号的生成★★

12． LeetCode89——格雷编码★★

13． LeetCode301——删除无效的括号★★★

14． POJ3050——跳房子

15． POJ1724——道路

16． POJ1699——最佳序列

17． POJ1564——求和

18． POJ2245——组合

19． POJ1321——棋盘问题

20． POJ2488——骑士之旅