第5章回溯法回溯法问题的解空间生成问题状态的基本方法回溯法的基本思想递归回溯迭代回溯子集树与排列树装载问题装载问题批处理作业调度批处理作业调度对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。swap(x,i,j);给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。-++-解向量：(x1,x2,…,xn)由于算法backtrack在最坏情况下可能需要计算O(n!)次当前圆排列长度，每次计算需O(n)计算时间，从而整个算法的计算时间复杂性为O((n+1)!){//检查颜色可用性给定n个作业的集合{J1,J2,…,Jn}。if(t>n)compute();(bestc==Float.bestf=f;MyMath.}backtrack(i+1);给定n个作业的集合{J1,J2,…,Jn}。用限界函数剪去得不到最优解的子树。符号三角形问题n后问题解向量：(x1,x2,…,xn)显约束：xi=1,2,…,n隐约束：1)不同列：xixj2)不处于同一正、反对角线：|i-j||xi-xj|0-1背包问题最大团问题最大团问题进一步改进算法的建议图的m着色问题解向量：(x1,x2,…,xn)表示顶点i所着颜色x[i]可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。旅行售货员问题(1)首先将第一艘轮船尽可能装满；更新最优解bestx,bestw;return;宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。if(constraint(t)&&bound(t))backtrack(t+1);}具有限界函数的深度优先生成法称为回溯法staticintn,//作业数因此，回溯法总的时间耗费是while(y[r]<maxint)r++;}MAX_VALUE&&a[x[n]][1]<Float.if(i>n){if(x[j]==1&&!a[i][j]){//i与j不相连for(inti=f(n,t);i<=g(n,t);i++){//检查顶点i与当前团的连接if(i>n)//到达叶结点圆排列问题连续邮资问题r+=w[i];if(i>n)//到达叶结点if(y[j]+k<y[j+x[i-1]*k])y[j+x[i-1]*k]=y[j]+k;如果UV且对任意u，vU有(u，v)E，则称U是G的空子图。可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。给定n个作业的集合{J1,J2,…,Jn}。x[t]=centerx;因此，回溯法总的时间耗费是backtrack(i+1);voidbacktrack(intt)-+++-sqrt(r[t]*r[j]);回溯法效率分析重排原理