算法与程序设计：第5章 回溯法

1第5章回溯法2学习要点理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）子集树算法框架（2）排列树算法框架3通过应用范例学习回溯法的设计策略（1）0-1背包问题；（2）n后问题；（3）子集和数问题；（4）图的着色问题；（5）旅行商问题（TSP）；（6）连续邮资问题。4

回溯法(backtracking)

回溯法的基本做法是搜索，是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。5问题的解空间(solutionspace)问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。例：n=3时0-1背包问题的解空间（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）6解空间搜索方法扩展结点（E结点）:一个正在产生子女结点的结点称为扩展结点。活结点:一个自身已生成但其子女结点还没有全部生成的结点称做活结点。死结点:一个所有子女结点已经产生的结点称做死结点。1.深度优先搜索法：如果对一个扩展结点R，一旦产生了它的一个子女C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个子女（如果存在）。2.宽度优先搜索法：在一个扩展结点变成死结点之前，它一直是扩展结点。具有限界函数的深度优先生成结点的方法称为回溯法。E结点一直保持到死为止的生成结点的方法称为分支限界法。7回溯法的基本步骤(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。85.40-1背包问题问题描述【0－1背包问题】给定n种物品和一背包。物品i的重量是wi，价值是vi，背包容量是W。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？【抽象描述】给定要求给出一个n元0-1向量使得，而且

达到最大。92.回溯法解决（1）定义问题解空间应用回溯法解问题，应首先明确定义问题的解空间，该空间中应至少包含问题的一个（最优）解。

对于0－1背包问题，它的解空间由长度为2n的0－1向量组成。当n=3时，解空间包含23个0－1向量。5.40-1背包问题102.回溯法解决（2）确定解空间结构0－1背包问题的解空间就可以用一棵完全二叉树表示出来。5.40-1背包问题112.回溯法解决（3）深度优先搜索解空间回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活动结点为止。在搜索过程中用剪枝函数避免无效搜索。0-1背包问题中，只要左孩子结点是一个可行解，搜索就进入左子树；只有右子树中包含可能更优解时，才进入右子树搜索。5.40-1背包问题12约束函数：用于左子树搜索。限界函数：将当前状态下的0-1背包问题看作是背包问题，利用贪心算法找出装满当前背包所能达到的最大价值，并与已经找到的最大价值进行比较，比较结果作为是否搜索右子树的条件。【例】n=3,W=30,w=[16,15,15],v=[45,25,25]5.40-1背包问题131293645781112101111100010131015140例题的状态空间树05.40-1背包问题14(4)算法实现BT-Knapsack(W,n,w,v,fw,fv,X)cw←cv←0k←1fw←fv←-1

dowhilek≤nandcw+w[k]≤Wdo//进入左子树

{cw←cw+w[k]cv←cv+v[k]y[k]←1k←k+1}

ifk>n//搜索到叶子结点

{thenfv←cvfw←cwk←n

X←Y}elsey[k]←015

whileBound(cv,cw,k,W)≤fvdo//不去右子树

{whilek≠0andy[k]≠1do

｛k←k-1｝//回溯ifk=0thenreturny[k]←0//进入上一层的右子树cw←cw-w[k]cv←cv-v[k]}k←k+1while(1)(4)算法实现16(5)算法实现之限界函数boundBound(cv,cw,k,W)b←cvc←cwfori←k+1tondoc←c+w[i]ifc<Wthenb←b+v[i]elsereturnb+(W-(c-w[i]))/w[i]*v[i]5.40-1背包问题173.子集树当所给的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树（subsettree）。0-1背包问题对应的解空间树就是一棵子集树，树中所有结点都可能成为问题的一个解。子集树中最多有2n个叶结点。5.40-1背包问题183.子集树遍历子集树需O(2n)计算时间

backtrack(intt)if(t>n)thenoutput(x)elsefori←0to1

dox[t]=i;if(legal(t))thenbacktrack(t+1)

19练习已知0-1背包问题实例如下n=4,w={20,25,15,35},v={40,49,25,60},W=62。完成以下题目：

(1)给出问题解空间，并用二叉树表示；

(2)对该树用回溯法遍历顺序给各结点编号；

(3)用回溯法求出最优值和最优解；

(4)指出未遍历到的结点。205.3子集和数问题(subset-sumproblem)1.问题描述给定n个互不相同的正整数pi(1≤i≤n)及一个正数S，要求找出为S的所有子集。例如，n=4,(p1,p2,p3,p4)=(5,7,12,18),S=30可以应用于如下实际问题：假定有一个Internet服务器，给定一个下载请求的集合。每个下载请求已知下载文件的大小。确定这些下载请求的一个子集，使得子集中整数之和恰好等于服务器一分钟可以容纳的宽带。215.3子集和数问题(subset-sumproblem)2.定义问题解空间用定长n元组(x1,x2,x3…xn)，xi∈{0,1}表示pi是否被选中。这样，解空间由2n个元组组成。3.确定解空间结构用一棵完全二叉树来表示上述解空间。22

4.深度优先搜索解空间树

约束函数：用于访问左子树判断条件；

界限函数：用于访问右子树判断条件。其中，假定pi按照非降次序排列，s为已选定整数之和，r为剩余整数之和。初始状态s=0，r=sum(p1,...pn)5.3子集和数问题(subset-sumproblem)235.3子集和数问题(subset-sumproblem)

【例】n=5，(p1,p2,p3,p4,p5)=(5,10,12,13,15),S=30245.6旅行商问题(travelsalesmanproblem)问题描述

某旅行商要到若干村庄去售货，各村庄之间的路程是给定的，为了提高效率，旅行商决定从所在商店出发，到每个村庄售一次货，然后返回商店，问他应该选择一条什么路线才能使所走的总路程最短？252343010546201【形式化描述】设G=(V,E)是一个带权图。图中各边的费用（权）为一正数，图中的一条周游路线是包括V中的每个顶点在内的一条回路，一条周游路线的费用是这条路线上所有边的费用之和。问题就是在G中找出一条有最小费用的周游路线。5.6旅行商问题(travelsalesmanproblem)262.解空间定义及表达

该问题的解可以组织成一棵树，从树根结点到任一叶结点定义了图G的一条周游路线。13222422432343344n＝4时，树的结构如图所示273.深度优先搜索及剪枝函数

如果从根结点到当前扩展结点处的部分周游路线的费用已经超过当前找到的最好的周游路线费用，则可以判断以该结点为根的子树中不含最优解，因此可以将该子树剪去。284.算法描述

旅行商问题的解空间是一棵排列树。对于排列树的回溯搜索与生成1，2，…，n的所有排列的递归算法类似。295.算法实现Backtrack(a,X,i)if(i=n)thenif(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j<=n;j++)//是否可进入x[j]子树?if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[i]]<bestc||bestc==NoEdge)){//搜索子树Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];Backtrack(a,X,i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。306.排列树遍历排列树需要O(n!)计算时间

backtrack(intt)if(t>n)thenoutput(x)elsefori←ttondoswap(x[t],x[i]);if(legal(t))thenbacktrack(t+1)swap(x[t],x[i])

当所给问题是从n个元素的集合中找出满足某种性质的排列时，相应的解空间树称为排列树（permutationtree）。31练习已知旅行商问题实例由如下边权值邻接矩阵定义：完成以下题目：

(1)画出解空间树；

(2)对该树用回溯法遍历顺序给各结点编号；

(3)用回溯法求出最优值和最优解；

(4)指出未遍历到的结点。325.2n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ3334解向量：(x1,x2,…,xn)显约束：xi=1,2,…,n隐约束：1)不同列：xixj2)不处于同一正、反对角线：|i-j||xi-xj|5.2n后问题boolQueen::Place(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(t+1);}}353.递归回溯

回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。backtrack(t)if(t>n)thenoutput(x)elsefori←f(n,t)tog(n,t)dox[t]←h(i)if(constraint(t)&&bound(t))thenbacktrack(t+1)364.迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。iterativeBacktrack()t←1while(t>0)doif(f(n,t)<=g(n,t))thenfori←f(n,t)tog(n,t)dox[t]←h(i)if(constraint(t)&&bound(t))thenif(solution(t))thenoutput(x)elset++elset--37图的m着色问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。38解向量：(x1,x2,…,xn)表示顶点i所着颜色x[i]可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。图的m着色问题voidColor::Backtrack(intt){if(t>n){sum++;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){//检查颜色可用性for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是39连续邮资问题假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。40连续邮资问题解向量：用n元组x[1:n]表示n种不同的邮票面值，并约定它们从小到大排列。x[1]=1是唯一的选择。可行