《算法设计与分析》第08章.ppt

《《算法设计与分析》第08章.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第08章.ppt（54页珍藏版）》请在三一办公上搜索。

1、,8.1 一般方法 8.2 n-皇后 8.3 子集和数 8.4 图的着色 8.5 哈密顿环 8.6 0/1背包 8.7 批处理作业调度,第8章 回溯法,8.1.1 基本概念,规定每个xi取值的约束条件称为显式约束（explicit constraint）。对给定的一个问题实例，显式约束规定了所有可能的元组，它们组成问题的候选解集，被称为该问题实例的解空间（solution space）。隐式约束（implicit constraint）给出了判定一个候选解是否为可行解的条件。,8.1 一般方法,目标函数，也称代价函数（cost function），用来衡量每个可行解的优劣。使目标函数取最大（或

2、最小）值的可行解为问题的最优解。状态空间树（state space）是描述问题解空间的树形结构。树中每个结点称为一个问题状态（problem state）。如果从根到树中某个状态的路径代表一个作为候选解的元组，则称该状态为解状态（solution state）。如果从根到某个解状态的路径代表一个作为可行解的元组，则称该解状态为答案状态(answer state)。,剪枝函数和回溯法,为了提高搜索效率，在搜索过程中使用约束函数（constraint function），可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可使用限界函数（bound function）剪去那些不可能包

3、含最优答案结点的子树。约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruning function）。,使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法（backtracking）；广度优先生成结点，并使用剪枝函数的方法称为分枝限界法（branch-and-bound）。,【程序81】递归回溯法Void RBacktrack(int k)/应以Rbacktrack(0)调用本函数 for(每个xk,使得 xkT(x0,xk-1),【程序8-2】迭代回溯法Void IBacktrack(int n)int

4、k=0;while(k=0)if(还剩下尚未检测的xk，使得xk T(x0,xk-1),回溯法的效率分析,回溯算法的最坏情况时间复杂度可达O(p(n)n!)（或O(p(n)2n)或O(p(n)nn)），这里p(n)是n的多项式，是生成一个结点所需的时间。,蒙特卡罗方法（Monte Carlo）。这种估计方法的基本思想是在状态空间树中随机选择一条路径(x0,x1,xn1)。设X是这条随机路径上，代表部分向量(x0,x1,xk1)的结点，如果在X处不受限制的孩子数目是mk，则认为与X同层的其他结点不受限制的孩子数目也都是mk。整个状态空间树上将实际生成的结点数估计为 m=1+m0+m0m1+m0m

5、1m2+,【程序8-3】蒙特卡罗算法int Estimate(SType*x)int k=0,m=1,r=1;do SetType S=xk|xkT(x1,xk1),8.2.1 问题描述,n-皇后问题要求在一个nn的棋盘上放置n个皇后，使得它们彼此不受“攻击”。n-皇后问题要求寻找在棋盘上放置这n个皇后的方案，使得它们中任何两个都不在同一行、同一列或同一斜线上。,8.2 n-皇后,8.2.2 回溯法求解,皇后问题可用n-元组（x0,x1,xn1）表示n-皇后问题的解，其中xi表示第i行的皇后所处的列号(0 xin)。显式约束的一种观点是：Si=0,1,n1，0in。相应的隐式约束为：对任意0i

6、,jn，当ij时，xixj且。此时的解空间大小为nn。另一种显式约束的观点是：Si=0,1,n1，0in，且xi xj(0i,jn,ij)。相应的隐式约束为：对任意0i,jn，当ij时，。与此相对应的解空间大小为n!。,皇后问题的状态空间树是一棵排列树。排列树有n!个叶结点，遍历排列树的时间为(n!)。,8.2.3 n-皇后算法,【程序8-4】n-皇后问题的回溯算法bool Place(int k,int i,int*x)/判定两个皇后是否在同一列或在同一斜线上 for(int j=0;jk;j+)if(xj=i)|(abs(xj-i)=abs(j-k)return false;return

7、true;void NQueens(int n,int*x)NQueens(0,n,x);,void NQueens(int k,int n,int*x)for(int i=0;in;i+)if(Place(k,i,x)xk=i;if(k=n-1)for(i=0;in;i+)coutxi;coutendl;else NQueens(k+1,n,x);,8.2.4 时间分析,可通过计算得到这5次试验中实际需要生成的结点数的平均值为1625。8-皇后问题状态空间树的结点总数是：因此，需要实际生成的结点数目大约占总结点数的1.55%。,问题描述,已知n个不同正数wi，0in-1，的集合，求该集合的所

8、有满足条件的子集，使得每个子集中的正数之和等于另一个给定的正数M。例82 设有n=4个正数的集合W=w0,w1,w2,w3=(11,13,24,7)和整数M=31，求W的所有满足条件的子集，使得子集中的正数之和等于M。,8.3 子集和数,8.3.2 回溯法求解,解结构形式：可变长度元组和固定长度元组。可变长度元组（x0,xk1,xk），0kn。元组的每个分量的取值可以是元素值，也可以是选入子集的正数的下标。固定长度n-元组（x0,x1,xn1），xi0,1,0in。xi=0，表示wi未选入子集，xi=1，表示wi入选子集。,称这种从n个元素的集合中找出满足某些性质的子集的状态空间树为子集树。子

9、集树有2n个解状态，遍历子集树的时间为(2n)。,约束函数：Bk(x0,x1,xk)为true，当且仅当,子集和数算法,【程序85】子集和数的回溯算法 void SumOfSub(float s,int k,float r,int*x,float m,float*w)xk=1;if(s+wk=m)for(int j=0;j=k;j+)coutxj;coutendl;,else if(s+wk+wk+1=m),例83 设有n=6个正数的集合W=(5,10,12,13,15,18)和整数M=30，求W的所有元素之和为M的子集。,问题描述,已知无向图G=(V,E)和m种不同的颜色，如果只允许使用这m

10、种颜色对图G的结点着色，每个结点着一种颜色。问是否存在一种着色方案，使得图中任意相邻的两个结点都有不同的颜色。这就是m-着色判定问题（m-colorability decision problem）,8.4 图的着色,回溯法求解,设无向图G=(V,E)采用如下定义的邻接矩阵a表示：解的形式：n-元组(x0,x1,xn1),xi1，m,0in，表示结点i的颜色，这就是显式约束。xi=0表示没有可用的颜色。因此解空间的大小为mn。隐式约束可描述为：如果边(i,j)E，则 xixj。,约束函数：对所有i和j，0i,jk，ij，若aij=1，则xixj。,8.4.3 图着色算法,【程序86】图的m着色

11、算法 template void MGraph:NextValue(int k,int m,int*x)do xk=(xk+1)%(m+1);if(!xk)return;for(int j=0;jk;j+)if(akj,template void MGraph:mColoring(int k,int m,int*x)do NextValue(k,m,x);if(!xk)break;if(k=n-1)for(int i=0;in;i+)cout xi;cout endl;else mColoring(k+1,m,x);while(1);,template void MGraph:mColorin

12、g(int m,int*x)mColoring(0,m,x);,8.4.4 时间分析,算法的计算时间上界可由状态空间树的结点数确定。每个结点的处理时间即NextValue的执行时间，为O(mn)。因此总时间为,问题描述,已知图G=(V,E)是一个n个结点的连通图。连通图G的一个哈密顿环(Hamiltonlan cycle)是图G的一个回路，它经过图中每个结点，且只经过一次。一个哈密顿环是从某个结点v0V开始，沿着图G的n条边环行的一条路径（v0,v1,vn1,vn），其中，(vi,vi+1)E,0in，它访问图中每个结点且只访问一次，最后返回开始结点，即除v0=vn，路径上其余结点各不相同。,

13、8.5 哈密顿环,8.5.2 哈密顿环算法,对于n个结点的图G=(V,E)的哈密顿环问题，可采用n-元组表示问题的解(x0,x1,xn1)。每个xi0,1,n-1,0in，代表路径上一个结点的编号，这就是显式约束。因此解空间的大小为nn。其隐式约束可描述为：xixj,0i,jn，ij，且（xi,xi+1）E，xi,xi+1V，i=0,1,n2，又（xn1，x0）E。哈密顿环问题的分析和求解方法与图的m-着色问题非常相似,【程序87】哈密顿环算法 template void MGraph:NextValue(int k,int*x)do xk=(xk+1)%n;if(!xk)return;if(

14、axk-1xk)for(int j=0;jk;j+)if(xj=xk)break;if(j=k)if(kn-1)|(k=n-1),template void ExtMGraph:Hamiltonian(int k,int*x)do NextValue(k,x);if(!xk)return;if(k=n-1)for(int i=0;in;i+)coutxi;cout 0n;else Hamiltonian(k+1,x);while(1);,template void ExtMGraph:Hamiltonian(int*x)Hamiltonian(1,x);,8.7.1 问题描述,设有n个作业的集

15、合0,1,n-1，每个作业有两项任务要求分别在2台设备P1和P2上完成。每个作业必须先在P1上加工，然后在P2上加工。P1和P2加工作业i所需的时间分别为ai和bi。作业i的完成时间fi(S)是指在调度方案S下，该作业的所有任务得以完成的时间，则是采用调度方案S的平均完成时间。,8.7 批处理作业调度,批处理作业调度(batch job schedule)问题要求确定这n个作业的最优作业调度方案使其MFT最小。这等价于求使得所有作业的完成时间之和最小的调度方案。,例85 设有三个作业和两台设备，作业任务的处理时间为（a0,a1,a2）=(2,3,2)和（b0,b1,b2）=(1,1,3)。这三

16、个作业有6种可能的调度方案：(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0),它们相应的完成时间之和分别是19,18,20,21,19,19。其中，最佳调度方案S=(0,2,1)。在这一调度方案下，f0(S)=3，f1(S)=7，f2(S)=8，FT=3+7+8=18。,回溯法求解,对于双机批处理作业调度问题，其可行解是n个作业所有可能的排列，每一种排列代表一种作业调度方案S，其目标函数是使FT(S)具有最小值的调度方案或作业排列是问题的最优解。对于双机作业调度，存在一个最优非抢先调度方案，使得在P1和P2上的作业完全以相同次序处理。批处理作业调度

17、问题的状态空间树解空间的大小为 n！。,求解这一问题没有有效的约束函数，但可以使用最优解的上界值U进行剪枝。如果对于已经调度的作业子集的某种排列，所需的完成时间和已经大于迄今为止所记录下的关于最优调度方案的完成时间和的上界值U,则该分枝可以剪去。,8.7.3 批处理作业调度算法,【程序89】批处理作业调度算法class BatchJobpublic:BatchJob(int sz,int*aa,int*bb,int up)n=sz;U=up;f=f1=0;a=new intn;b=new intn;f2=new intn;y=new intn;for(int i=0;in;i+)ai=aai;

18、bi=bbi;yi=i;,int JobSch(int*x);private:void JobSch(int i,int*x);int*a,*b,n,U,f,f1,*f2,*y;,void BatchJob:JobSch(int i,int*x)if(i=n)for(int j=0;jn;j+)xj=yj;U=f;else,for(int j=i;jf1)?f2i1:f1)+byj;f+=f2i;if(fU)Swap(y,i,j);JobSch(i+1,x);Swap(y,i,j);f1-=ayj;f-=f2i;,int BatchJob:JobSch(int*x)JobSch(0,x);return U;,