第5章 回溯算法

计算机算法设计与分析

DesignandAnalysisofComputerAlgorithms

第五章回溯算法BacktrackAlgorithm王红霞理学院2024年2月29日2理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架学习要点2024年2月29日3提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日4提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日5深度优先搜索算法

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支，如果发现目标，则算法中止，属于盲目搜索。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。2024年2月29日6

同时深度优先搜索算法的时间复杂度不高（为线性时间复杂度），遍历图的效率往往非常高。因此，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇，他们常建议在遇到未知性质的图时，先对图进行深度优先遍历，以了解未知图的性质。因发明“深度优先搜索算法”，霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖：图灵奖2024年2月29日7

搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

2024年2月29日8迷宫游戏2024年2月29日9例：迷宫游戏2024年2月29日10例：N后问题2024年2月29日11引言有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2024年2月29日125.1回溯法的算法框架本节介绍回溯法算法框架的有关问题：一、问题的解空间二、回溯法的基本思想三、递归回溯四、迭代回溯五、子集树与排列树2024年2月29日135.1.1问题的解空间问题所有可能的解构成了问题的解空间，解空间也就是进行穷举的搜索空间。确定正确的解空间很重要！例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。(a)二维搜索空间无解(b)三维搜索空间的解错误的解空间将不能搜索到正确答案！2024年2月29日145.1.1问题的解空间对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种：（1）可能解由一个不等长向量组成，当物品i(1≤i≤n)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是：

{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一个等长向量{x1,x2,…,xn}组成，其中xi=1(1≤i≤n)表示物品i装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是：

{(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}2024年2月29日15问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。2024年2月29日165.1.1问题的解空间

为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi}，所有可能的解向量构成了问题的解空间。问题的解空间一般用解空间树（SolutionSpaceTrees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。2024年2月29日175.1.1问题的解空间

1.背包问题对于n=3的0/1背包问题，其解空间树如下图所示，树中的8个叶子结点分别代表该问题的8个可能解。对物品1的选择对物品3的选择对物品2的选择11111100000001123457811121415310692024年2月29日182旅行售货员问题问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。该问题是一个NP完全问题，有(n-1)!条可选路线最优解(1,3,2,4,1)，最优值251234206305410ABCDEFGHIJKLMNOPQ12343443423224232024年2月29日195.1.2回溯法的基本思想

回溯法从根结点出发，按照深度优先策略搜索（遍历）解空间树，搜索满足约束条件的解。初始时，根结点成为一个活结点，同时也称为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为一个死结点（即不再是一个活节点）。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。20死结点扩展结点活结点扩展结点:一个正在产生儿子的结点称为扩展结点。活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点。死结点:一个所有儿子已经产生的结点称做死结点。2024年2月29日215.1.2回溯法的基本思想在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出限界函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。在搜索过程中，通常采用两种策略避免无效搜索：（1）用约束条件剪去得不到可行解的子树；（2）用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数（PruningFunction）。2024年2月29日225.1.2回溯法的基本思想

例如，对于n=3的0/1背包问题，三个物品的重量为{16,15,15}，价值为{45,25,25}，背包容量为30，从其解空间树的根结点开始搜索，搜索过程如下：ACr=C=30，V=0HIw1=16，v1=45Cr=14，V=45B1DCr<w2不可行解1JCr<w3不可行解1Fw2=15，v2=25Cr=15，V=251CCr=30，V=00Cr=14V=45E0Lw3=15，v3=25Cr=0，V=5050>45x=(0,1,1)1KCr=14V=45x=(1,0,0)0M25<50不是最优解0NOGV<=25不包含最优解02024年2月29日235.1.2回溯法的基本思想回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点，搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造；2024年2月29日245.1.3递归回溯voidbacktrack(intt)//t表示递归深度，即对解空间树的第t层节点进行深度优先搜索；{

if(t>n)output(x);//n表示解空间树的高度；

elsefor(inti=f(n,t);i<=g(n,t);i++){//f(n,t)和g(n,t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；

x[t]=h(i);//h(i)表示在当前扩展结点处x[t]的第i个可选值；

if(constraint(t)&&bound(t))backtrack(t+1);//constraint(t)和bound(t)分别表示在当前扩展结点处的约束函数和限界函数；

}}2024年2月29日255.1.4迭代回溯voidIterativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){//函数solution(t)判断在当前扩展结点处是否找到问题的一个可行解；

if(solution(t))output(x);

elset++;}}

elset--;}}2024年2月29日265.1.5子集树与排列树当所给问题是从n个元素的集合S中找出满足某种性质的子集时，解空间为子集树。

当所给问题是从n个元素的集合S中找出满足某种性质的排列时，解空间为排列树。2024年2月29日27遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(constraint(t)&&bound(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(constraint(t)&&bound(t))

backtrack(t+1);swap(x[t],x[i]);}}5.1.5子集树与排列树//更换排列顺序

当前的第一个元素和下面的交换

//搜索完毕后恢复

2024年2月29日28对于n=4的旅行售货员问题（TSP），其解空间树如下图所示。叶子结点代表该问题的可能解，例如结点5代表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。243422343413142412123312134131312321214241434322434123124134n=4的TSP问题的解空间树57101215172123262831333739424447495254575962644691114162022252730323638414346485153565861633813192429354045505560218342411234342024年2月29日295.1.6回溯法的求解过程(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)深度优先搜索解空间，并在搜索中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。2024年2月29日30提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日315.2.1装载问题问题定义有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑wi≤c1+c2装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。例如：当n=3，c1=c2=50，w=[10,40,40]，可以将集装箱1和2装到第一艘轮船上，将集装箱3装到第二艘轮船上。如果w=[20,40,40]，则无法将这3个集装箱都装上轮船。2024年2月29日325.2.2问题分析如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案：(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1

。由此可知，装载问题等价于以下特殊的0-1背包问题。2024年2月29日335.2.3算法设计解空间：子集树可行性约束函数(选择当前元素)：上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r>当前最优载重量bestw101111000不满足约束函数1不满足上界函数00134例w={16,15,15},c=3001603100031163001615151510000000111113131用子集树表示其解空间，用可行性约束函数可剪去不满足条件的子树。在子集树的第j+1层的结点Z处，用cw记当前的装载重量，即cw=，则当cw>c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。355.2.4装载问题算法描述template<classType>classLoading{friendTypeMaxLoading(Type[],Type,int);private:voidBacktrack(inti);intn;//集装箱数Type*w,//集装箱重量数组

c,//第一艘轮船的载重量

cw,//当前载重量

bestw;//当前最优载重量};函数MaxLoading负责该类成员的初始化，返回不超过c的最大子集和，但未给出达到这个最大子集和的相应子集Backtrack实现回溯搜索，Backtrack(1)实现对整个解空间的回溯搜索，Backtrack(i)搜索子集树中第i层子树。36template<classType>TypeMaxLoading(Typew[],Typec,intn){//返回最优载重量Loading<Type>x;x.w=w;x.c=c;x.n=n;x.bestw=0;x.cw=0;

//计算最优载重量

x.Backtrack(1);returnx.bestw;}

装载问题37Backtrack(inti){//搜索第i层结点

如果到达叶结点，则判断当前的cw，如果比前面得到的最优解bestw好，则替换原最优解。

//搜索左子树如果当前剩余空间可以放下当前物品，也就是，cw+w[i]<=c，则把当前载重cw+=w[i]，递归访问其左子树，Backtrack(i+1)，访问结束，回到调用点，cw-=w[i]//搜索右子树Backtrack(i+1);}装载问题38template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i层结点if(i>n){//到达叶结点

if(cw>bestw)bestw=cw;return;}

//搜索子树

if(cw+w[i]<=c){//x[i]=1cw+=w[i];Backtrack(i+1);cw-=w[i];}Backtrack(i+1);//x[i]=0}0160030016151515100000011i=1i=2i=316i=41w={16,15,15},c=30即使把剩余物品都装里也不会得到比当前的最优解更好装载问题右子树永远可行！390160030016151515100000011i=1i=2i=316i=41引入一个上界函数，用于剪去不含最优解的子树，设Z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量和；定义上界函数为cw+r。在以Z为根的子树中任一结点所相应的载重量均不超过cw+r。因此，当cw+r<=bestw时，可将Z的右子树剪去。

装载问题403.上界函数在改进算法中，引入类Loading的一个私有变量r，用于计算上界函数，引入上界函数后，在达到一个叶结点时就不必再检查该叶结点是否优于当前最优解。因为上界函数使算法搜索到的每个叶结点都是迄今为止找到的最优解，时间复杂性没有变化，但在平均情况下改进后的算法检查的结点数较少。

装载问题41Template<classType>classLoading{friendTypeMaxLoading(Type[],Type,int);private:voidBacktrack(inti);intn;//集装箱数Type*w,//集装箱重量数组

c,//第一艘轮船的载重量

cw,//当前载重量

bestw，//当前最优载重量

r;//剩余集装箱重量};

装载问题42template<classType>TypeMaxLoading(Typew[],Typec,intn){//返回最优载重量Loading<Type>x;x.w=w;x.c=c;x.n=n;x.bestw=0;x.cw=0;

x.r=0;for(inti=1;i<=n;i++)x.r+=w[i];//初始时r为全体物品的重量和

//计算最优载重量

x.Backtrack(1);returnx.bestw;}5.2装载问题43Backtrack(inti){//搜索第i层结点

如果到达叶结点，bestw=cw。

//修改剩余重量rr=r-w[i]

//搜索左子树如果当前剩余空间可以放下当前物品也就是，cw+w[i]<=c，则把当前载重cw+=w[i]，递归访问其左子树，Backtrack(i+1)，访问结束，回到调用点，cw-=w[i]。//搜索右子树

如果剩余重量加上当前载重大于最优值，递归访问右子树，Backtrack(i+1)。

//回到上一层调用点

r=r+w[i]}

装载问题44template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i层结点if(i>n){//到达叶结点bestw=cw;return;}

//搜索子树

r-=w[i];

if(cw+w[i]<=c){//x[i]=1cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+r>bestw)//x[i]=0Backtrack(i+1);r+=w[i];}i=1cw=0bestw=0r=46cw=0bestw=0r=30i=2cw=16bestw=0r=15i=3cw=16bestw=0r=0i=4cw=16bestw=161000cw=0bestw=16r=151cw=15bestw=16r=0cw=0bestw=16r=301cw=30bestw=30cw=15bestw=30r=0cw=0bestw=30r=15cw=0bestw=30r=30cw=16bestw=16r=0cw=16bestw=16r=15w={16,15,15},c=3045Template<classType>classLoading{friendTypeMaxLoading(Type[],Type,int,int[]);private:voidBacktrack(inti);intn;//集装箱数

*x,//当前解

*bestx;//当前最优解Type*w,//集装箱重量数组

c,//第一艘轮船的载重量

cw,//当前载重量

bestw，//当前最优载重量

r;//剩余集装箱重量};装载问题46template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//返回最优载重量Loading<Type>X;X.x=newint[n+1];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;

X.r=0;for(inti=1;i<=n;i++)X.r+=w[i];//初始时r为全体物品的重量和

//计算最优载重量

X.Backtrack(1);delete[]X.x;returnx.bestw;}

装载问题47template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i层结点if(i>n){//到达叶结点

for(j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;return;}

//搜索子树

r-=w[i];

if(cw+w[i]<=c){

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];}装载问题48bestx可能被更新O(2n)次，算法计算时间复杂性为O(n2n)。采用两种策略之一改进算法使其复杂度减至O(2n)（1）首先运算只计算最优值的算法，计算出最优装载量W，所需计算时间为O(2n)，然后再运行改进后的backtrack，并在算法中将bestw置为W。（2）动态地更新bsetx，在第i层的当前结点处，当前最优解由x[j],j<i，和bestx[j]，i<=j组成，每当算法回溯一层时，将x[i]存入bestx[i],这样一来，在每个结点处更新bestx只需O(1)时间，从而算法中跟新bestx所需的时间为O(2n)。

装载问题49迭代回溯非递归的方式可以省去O(n)的递归栈空间template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){//迭代回溯

inti=1;//当前层

//x[1:i-1]为当前路径

int*x=newint[n+1];Typebestw=0,//当前最优装载重量cw=0;//当前载重量r=0;//剩余集装箱重量for(intj=1;j<=n;j++)r+=w[j];

装载问题50//搜索子树while(true){while(i<=n&&cw+w[i]<=c){

//进入左子树

r-=w[i];cw+=w[i];x[i]=1;i++;}if(i>n){//到达叶结点for(intj=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}else{//进入右子树

r-=w[i];x[i]=0;i++;}while(cw+r<=bestw){

//剪枝回溯

i--;

while(i>0&&!x[i]){

//从右子树返回r+=w[i];i--;}if(i==0){delete[]x;returnbestw;}

//进入右子树x[i]=0;cw-=w[i];i++;}}}51//搜索子树while(true){while(i<=n&&cw+w[i]<=c){

//进入左子树

r-=w[i];cw+=w[i];x[i]=1;i++;}if(i>n){//到达叶结点for(intj=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}else{//进入右子树

r-=w[i];x[i]=0;i++;}i=1cw=0bestw=0r=46cw=0bestw=0r=30i=2cw=16bestw=0r=15i=3cw=16bestw=0r=0i=4cw=16bestw=16100装载问题w={16,15,15},c=3052i=1cw=0bestw=0r=46cw=0bestw=0r=30i=2cw=16bestw=0r=15i=3cw=16bestw=0r=0i=4cw=16bestw=161000cw=0bestw=16r=151cw=15bestw=16r=0cw=0bestw=16r=301cw=30bestw=30cw=15bestw=30r=0cw=0bestw=30r=15cw=0bestw=30r=30cw=16bestw=16r=0cw=16bestw=16r=15while(cw+r<=bestw){

//剪枝回溯

i--;

while(i>0&&!x[i]){

//从右子树返回r+=w[i];i--;}if(i==0){delete[]x;returnbestw;}

//进入右子树x[i]=0;cw-=w[i];i++;}}}

装载问题w={16,15,15},c=302024年2月29日53习题5-12024年2月29日542024年2月29日55习题5-22024年2月29日562024年2月29日572024年2月29日58提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日59N皇后问题是在N×N的国际象棋棋盘上,放置N个皇后,使任何两个皇后都不能相互攻击。也就是说,任何两个皇后,都不在同一行、同一列或同一斜线上。N皇后问题是由八皇后问题演化而来的。八皇后问题于1848年由国际象棋棋手MaxBazzel提出。八皇后问题自从提出之后,吸引了许多著名数学家的关注,其中包括CarlGauss。近年来,N皇后问题成为计算机应用领域内的一个经典问题,不但成为测试算法的一个工具,还成为检验并行计算系统效率的一个有效工具。引言2024年2月29日603.1问题定义八皇后问题是一个非常著名的问题，最初是由著名数学家高斯提出的。问题的描述是这样的：在一个8×8的棋盘上，摆放8个皇后，任意两个皇后不能处在同一行、同一列和同一斜线上。该问题也可以被扩展为在一个n×n的棋盘上摆放n个皇后的问题。在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。2024年2月29日613.1问题定义4皇后问题：********8皇后问题：1Q2Q3Q4Q5Q6Q7Q8Q123456782024年2月29日62例：N后问题2024年2月29日63经典的回溯算法，该算法的思路如下：•

依次在棋盘的每一行上摆放一个皇后。

•

每次摆放都要检查当前摆放是否可行。如果当前的摆放引发冲突，则把当前皇后摆放到当前行的下一列上，并重新检查冲突。

•

如果当前皇后在当前行的每一列上都不可摆放，则回溯到上一个皇后并且将其摆放到下一列上，并重新检查冲突。

•

如果所有皇后都被摆放成功，则表明成功找到一个解，记录下该解并且回溯到上一个皇后。

2024年2月29日64求解N后问题中的数据表示654321123456i+j=k+l2024年2月29日65求解N后问题中的数据表示i-j=k-l6543211234562024年2月29日663.2问题分析解向量：(x1,x2,…,xn)，x[i]表示皇后i放在棋盘的第i行的第x[i]列。显约束：xi=1,2,…,n隐约束：

1)不同列：xi≠xj(i≠j)

2)不处于同一正、反对角线：|i-j|≠|xi-xj|解空间：排列树约束函数：xi≠xj(i≠j)and|i-j|≠|xi-xj|2024年2月29日67

为了用回溯法求解4皇后问题，算法尝试生成并以深度优先方式搜索一棵完全四叉有根树，树的根对应于没有放置皇后的情况。第一层的节点对应于皇后在第一行的可能放置情况，第二层的节点对应于皇后在第二行的可能放置情况，依次类推。2024年2月29日683.3算法描述//place函数测试若将皇后k放在x[k]列是否与前面已放置的k-1个皇后都不在同一列，而且都不在同一斜线上。boolQueen::Place(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}//递归函数backtrack(1)实现对整个解空间的回溯搜索。voidQueen::Backtrack(intt){if(t>n)sum++;//sum记录当前已找到的可行方案数。

elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}backtrack(i)搜索解空间中的第i层子树。当t即i>n时，表示算法已搜索至一个叶结点，得到一个新的皇后互不攻击方案，因此当前已找到的可行方案sum加1。当i<=n时，当前扩展结点是解空间的一个内部结点。该结点有x[i]=1,2,…n共n个儿子结点。对当前扩展结点的每一个儿子结点，由函数place检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或者剪去不可行子树。2024年2月29日692024年2月29日70N后问题的时间复杂性如果只要找出N后问题的一个解，那么这是一个求路径的问题。求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+1–1，遍历的时间为O(kn)，这里n为找到解的路径长度。N后问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。2024年2月29日71VoidQueen::Backtrack(void){X[i]=0;Intk=1;While(k>0){x[k]+=1;while((x[k]<=n)&&!(place(k)))x[k]+=1;if(x[k]<=n)if(k==n)sum++;else{k++;x[k]=0;}elsek--;}}迭代回溯2024年2月29日72提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日734.1问题定义给定n种物品和一个背包，物品i的重量是wi，价值pi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。2024年2月29日744.2问题分析解空间：子集树可行性约束函数：或：cw+wi<=c75例n=4,c=7,w={3,5,2,1},p={9,10,7,4}0,03,90,086,205,163,97,173,95,101000001111用子集树表示其解空间，左儿子如果可行，进入左子树，只有右子树中有可能包含最优解时才进入右子树搜索，否则将右子树剪去。上界函数：cp+r≤bestp当前获得价值+剩余价值≤当前最优价值。13,9010

0-1背包问题76有时即使满足了cp+r≤bestp，但实际上背包并不能装下所有剩余物品，也就是上界cp+r大了。缩小上界可以提供另一个更好的上界函数。计算右子树中解的上界时，将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树的上界，如果这个上界不能达到当前得到的最优值，则不搜索该子树。5.30-1背包问题77以物品单位重量价值的递减序装入物品。n=4,c=7,p={9,10,7,4},w={3,5,2,1}单位价值量{3,2,3.5,4}。先装入物品4，然后3，1，物品2最多装0.2，得到一个解{1,0.2,1,1}，相应的上界为22。5.30-1背包问题78将物品按单位价值量排序。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数Bound，判断是否可以将右子树剪去。进入左子树时，不需要计算上界。5.30-1背包问题79template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//计算上界Typewcleft=c–cw;//剩余容量

Typepb=cp;

//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}

0-1背包问题80例n=4,c=7,w={1，2，3，5},p={4，7，9，10}0,01,43,11116,2016,20019<2019<2020=205.30-1背包问题814.3算法描述template<classTypew,classTypep>classKnap{//背包描述friendTypepKnapsack(Typep*,Typew*,Type,int);private:TypepBound(inti);voidBacktrack(inti);Typewc;//背包容量intn;//物品数Typew*w,//物品重量数组Typep*p,//物品价值数组

Typewcw;//当前重量

Typepcp;//当前价值Typepbestp;//当前最优价值};Backtrack实现回溯搜索，Backtrack(1)实现对整个解空间的回溯搜索，Backtrack(i)搜索子集树中第i层子树。计算第i层结点的上界5.30-1背包问题82classObject{//物品friendintKnapsack(int*,int*,int,int);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;floatd;//单位重量价值};

0-1背包问题83template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn){//为Knap::Backtrack初始化

TypewW=0;TypepP=0;Object*Q=newObject[n];for(inti=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)returnP;//装入所有物品

//依物品单位重量价值排序

Sort(Q,n);Knap<Typew,Typep>K;K.p=newTypep[n+1];K.w=newTypew[n+1];

for(inti=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}5.30-1背包问题84template<classTypew,classTypep>TypepKnap<Typew,Typep>::Backtrack(inti){if(i>n){bestp=cp;return;}if(cw+w[i]<=c){//x[i]=1cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)//x[i]=0Backtrack(i+1);}

0-1背包问题如何计算？85算法效率

由于计算上界函数Bound需要O(n)时间，在最坏情况下有O(2n)个右儿子结点需要计算上界函数，故解0-1背包问题的回溯算法Backtrack所需的计算时间为O(n2n)。

0-1背包问题2024年2月29日86提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日875.1问题定义完全子图：给定无向图G=(V，E)。如果U

V，且对任意u，v

U有(u，v)

E，则称U是G的完全子图。团：G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团：是指G中所含顶点数最多的团。124532024年2月29日885.1问题定义空子图：如果U

V且对任意u，v

U有(u，v)

E，则称U是G的空子图。独立集：G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集：是G中所含顶点数最多的独立集。补图：对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)

E1当且仅当(u，v)

E。U是G的最大团当且仅当U是G的最大独立集。12453124532024年2月29日895.2问题分析解空间：子集树可行性约束函数：顶点i到已选入的顶点集中每一个顶点都有边相连。上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。2024年2月29日905.3算法描述voidClique::Backtrack(inti)//计算最大团{if(i>n){//到达叶结点

for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}

intOK=1;//检查顶点i与当前团的连接

for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i与j不相连

OK=0;break;}if(OK){//进入左子树

x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//进入右子树

x[i]=0;Backtrack(i+1);}}复杂度分析最大团问题的回溯算法backtrack所需的计算时间为O(n2n)。2024年2月29日91提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日926.1问题定义给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。2024年2月29日936.1问题定义可平面图：如果一个图的所有顶点和边都能用某种方式画在一个平面上且没有任何两边相交，则称这个图是可平面图。四色定理：任何平面图都是可以4着色的。2024年2月29日946.1问题定义图的m着色问题：

给定一个一般连通图G=(V,E)和m种颜色，如果这个图不是m可着色的就给出否定回答，如果这个图是m可着色的，则要找出所有不同的着色方案。2024年2月29日956.2问题分析解向量：(x1,x2,…,xn)表示顶点i所着颜色x[i]。解空间：完全m叉树可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。2024年2月29日966.3算法描述voidColor::Backtrack(intt){if(t>n){sum++;//当前已找到的可m着色方案数加1；

for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk)//检查第k个顶点当前所选颜色x[k]的可用性；{for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}2024年2月29日976.4复杂性分析图m可着色问题的解空间树中内结点个数是∑mi(0≤i≤n-1)。对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是∑mi(mn)=nm(mn-1)/(m-1)=O(nmn)(0≤i≤n-1)2024年2月29日98提纲一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2024年2月29日99

旅行商问题是一个经典的组合优化问题。经典./-可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton

回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP

完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。2024年2月29日100哈密顿回路天文学家哈密顿(WilliamRowanHamilton)提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。

这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不一定是双向的。比如A→B,但B→A是不允许的。换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。

2024年2月29日101从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。

要满足两个条件：

1.封闭的环

2.是一个连通图，且图中任意两点可达

经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。

经过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。

平凡图是哈密顿图。

2024年2月29日102哈密顿

哈密顿，W．R．(Hamilton，WilliamRowan)

1805年8月4日生于爱尔兰都柏林；1865年9月2日卒于都柏林．力学、数学、光学．

2024年2月29日103哈密顿的父亲阿其巴德(ArchibaldRowanHamilton)为都柏林市的一个初级律师．哈密顿自幼聪明，被称为神童．他三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语．14岁时，因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头．

哈密顿自幼喜欢算术，计算很快．1818年遇到美国“计算神童”