系研一下学期-算法设计与分析课件ch6.backtracking

Chapter6(Zilei: 迭代回子集树算法框排列树算法框装载问批处理作业调符号三角形问USTCn后问0-1背包问最大团问图的 问旅行售货员问圆排列问电路板排列问连续邮资问USTC一种组织得井井有条的，能避免不必要搜索的穷举式搜索适用于解一些组合数相当大的问如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯；否则，进入该子树，继续按深度优先策略搜USTC注意注意：要确定好组织结构同一个问题可以有多种表示，有些表示方法更简单，所需表示状态空间更小量少，搜索方法简单隐约束：为满足问题的解而对不同分量之间n=3时的0-1背包问题用完全二叉树表示的解空USTC扩展结点：一个正在产生儿子的结点称为扩展结活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结死结点：一个所有儿子已经产生的结点称做死结如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）在一个扩展结点变成死结点之前，它一直是扩展结USTC(boundingfunction)来处死那些实际上不可能产生所需解的活结具有限界函数的深度优先生成法USTC12USTC在任何时刻，算法只保存从根结点到当前扩展结点的路回溯法所需的计算空间通常O(h(n))而显式 整个解空间则需要O(2h(n))或O(h(n)!)的内存空USTCvoidbacktrack(int{if(t>n)output(x);for(inti=f(n,t);i<=g(n,t);i++){if(constraint(t)&&bound(t))}}进入子节解赋子节点遍叶节USTCvoidvoiditerativeBacktrack{intwhile(t>0)iffor(inti=f(n,t);i<=g(n,t);i++)if(constraint(t)&&bound(t))if(solution(t))else elset--}14.USTC遍历子集树需O(2n)计算时

遍历排列树需要O(n!)计算时voidbacktrackvoidbacktrack(int{if(t>n)for(inti=0;i<=1;i++)if(legal(t)) voidbacktrack(int{if(t>n)for(inti=t;i<=n;i++)swap(x[t],if(legal(t))swap(x[t], 10.USTCiwi，且inw c c装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上2艘轮船；如果有，找出一种装载方案(1)首先将第一艘轮船尽可能装(2)将剩余的集装箱装上第二艘轮USTCmaxmaxwixii1s.t.wixic1ixi{0,1},1innwinUSTCvoidbacktrack(inti)//搜索第i{if(in)//r-=if(cww[i]c)x[i]=cw+=backtrack(i+cw-= if(cwrbestw){//x[i]=backtrack(i+ r+=

USTCn个作业的集合{J1,J2,…,Jn}1处理，然后由机器2处理所有作业在机器2上完成处理时间和称为该nnfF2ii1USTC机器机器作业2131作业23它们所相应的完成时间和分别是USTC{if(i>n)for(intj=1;j<=n;bestx[j]=bestf= for(intj=i;j<=n;j++)if(f<bestf)Swap(x[i],Swap(x[i], f1-f- 21.friendFlow(int**,int,int //各作业所需的处理时//当前作业调//当前最优作业调//机器2完成处理时//机器1完成处理时13.USTC14个“14个“组成的符号三角形，2号下面都是“+”，2个异号下面都是“n个符号n，计算有多少个不同“+”和“-”的n个符号n，计算有多少个不同“+”和“-”的个数相同 +USTC可行性约束函数：当前符号三角形所包含的“个数与“-”n*(n+1)/4无解的判断：n*(n+1)/2 +USTC{if((count>half)||(t*(t-1)/2-count>half))if(t>n)for(inti=0;i<2;i++)for(intj=2;j<=t;j++)p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-count+=p[j][t- for(intcount-=p[j][t-count- 18.

计算可行性约束需O(n时间，在情况下有为O(n2n)USTCn在n×n格的棋盘上放置彼此不受的n个皇后（按照国际线上的棋子）。nn×n格的棋盘上n个12345678QQQQQQQ1234678USTCn解向量：(x1x2ixi列显约束：xi=1,2,不同列：xi

boolQueen::Place(int{for(intreturn voidQueen::Backtrack(int{if(t>n)for(inti=1;i<=n;i++)if(Place(t)) USTC{Typewcleftccw;//Typepb=//while(i<=n&&w[i]<=cleft)cleft-=b+=p[i];}if(i<=n)b+=p[i]/w[i]*cleft;returnb;15.nirUSTC团UG的完全子G的最大团是指G中所含顶点数最多的UV且对任意u,vU有(u,v)E，则UG的空子G的最大独立集是G中所含顶点数最多的独立USTCV1=V(u,v)E1当且仅当UUGUG1231234512345USTCvoidClique::Backtrack(int{//计算最大if(in)到达叶结for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn; 检查顶点i与当前团的连intOK=for(intj=1;j<i;if(x[j]&&a[i][j]==0)//i与j不相连OK0;break;}ifOK进入左子树x[i]=1;cn++;x[i]=0;cn--;}if(cnnibestn进入右子x[i]=}}上界函数：有足够多的可选择顶大的1212345复杂度分需的计算时间显然为O(n2n)USTC到一个更精确的上界函数，若cn+Si<=max则剪枝属于找到的团，此时有Si=Si+1+1，否则USTC的 是图的m可 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数 四色猜USTC的 USTCvoidColor::Backtrack(intvoidColor::Backtrack(int{if(t>n)for(inti=1;i<=n;cout<<x[i]<<'cout<< for(inti=1;i<=m;i++)if(Ok(t)) 14.boolColor::Ok(int{//检查颜色可用for(intreturn}复杂度分图m 问题的解空间树中内点个数 对于每一个内结点，在情况，用Ok检查当前扩展结点的每一USTCtemplate<classvoidTraveling<Type>::Backtrack(int{//获得一个排if(i==n)if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge(cca[x[n-1]][x[na[x[n]][1bestc||bestcNoEdge)){//当前排列更for(intj=1;j<=n;j++)bestx[j]=bestc=cc+a[x[n-1]][x[n]]+ else{//继续递for(intj=i;j<=n;//是否可进入x[j]子树(cca[x[i-1]][x[ibestc||bestcNoEdge可能有更优解，搜索子Swap(x[i], 22.

cc-=a[x[i-Swap(x[i],

复杂度分算法backtrack 情况下可能需要更当前O((n-1次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为USTC圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排2 2 USTCvoidvoidCircle::Backtrack(int{if(t>n)for(intj=t;j<=n;j++)Swap(r[t],float Swap(r[t], 14.floatCircle::Center(intfloatfloatif(valuex>temp) return 2.2.{//计算当前圆排列的长floatlow=0,high=0;for(inti=1;i<=n;i++){ifx[i]+r[i]>high)high=x[i]+r[i后端}}由于算法backtrack 情况下可能需要计算O(n!)次当前圆排)为O((n+1)!)USTC 了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票的最佳设计——11开始，增量1的170USTC约定它们从小到大排x[1]=1是唯一的选已选定x[1:i-1]，最大连续邮资区间是接下来x[i]的可取值范围是[x[i-USTC考虑到直接递归的求解复杂度太高，我们尝试计算用不超过m张mmUSTC

1212213∞121∞∞∞ 𝑘10𝑘11for(intj=0;j<=x[i-2]*