您好,欢迎访问三七文档
1第五章贪婪法5.1贪婪法引言5.2背包问题5.3单源最短路径问题5.4最小花费生成树问题5.5霍夫曼编码问题25.1贪婪法引言一货币兑付问题二贪婪法的设计思想三贪婪法的例子_货郎担问题3一货币兑付问题货币兑付问题:用最少的货币张数支付现金集合表示n张面值为的货币,1in出纳员需支付的现金为A,从P中选取一个最小的子集S,使得用向量表示S中所选取的货币,使得出纳员支付的现金必须满足使得:}p,,p,p{=Pn21ipSpi∈A=pi∑)x,,x,x(=Xn21Sp0Sp1=xiii∈A=pxin1=ii∑∑n1=iixmin=d4货币兑付问题(续)解向量:问题中n个元素的具体取值所构成的向量解空间:问题中n个元素的各种不同取值组合所构成的向量全体约束方程:问题中的限制条件所列出的方程目标函数:问题求解所要达到的目标可行解:满足约束方程的向量最优解:使目标函数达极值的向量5二贪婪法的设计思想1.贪婪法的思想方法2.贪婪法的一般描述3.适于用贪婪法求解的条件61.贪婪法的思想方法不断地从问题的n个元素中选取一个最优的元素的取值,作为局部解向量中的一个分量,使其既满足约束方程,又使目标函数取极值最快,当n个元素的取值均求取之后,解向量就成为完整的向量,它就是问题的解72.贪婪法的一般描述greedy(A,n){solution=;for(i=1;in;i++){x=select(A);if(feasible(solution,x))solution=union(solution,x);}returnsolution;}83.适于用贪婪法求解的条件1)贪婪选择性质:所求问题的全局最优解,可以通过一系列局部最优的选择来达到例:从10张10元、10张5元、10张1元、10张5角、10张2角、10张1角的货币中兑付57元8角集合顺序表示货币向量表示支付给客户的货币第一步挑出的货币集合,局部解问题简化为在集合中挑选货币、付出47元8角,在以后的步骤中,可以用同样的方法进行挑选,并能得到问题的全局最优解}p,,p,p{=P6021)x,,x,x(=X6021}p{=S11),0,1(=Y1}p,,p{=P60219适于用贪婪法求解的条件(续)2)最优子结构:问题的最优解,包含它的子问题的最优解付给客户的货币集合的最优解是第一步所简化了的子问题的最优解是所以,出纳员付钱问题具有最优子结构性质}p,p,p,p,p,p,p,p,p,p,p{=S51413122211154321n}p,p,p,p,p,p,p,p,p,p{=S51413122211154321n-n1nSS⊂-n11nS=}p{S∪-10三贪婪法的例子_货郎担问题货郎担问题:5个城市,费用矩阵如下总是选择费用最小的路线前进,选择的路线是:143521,总费用是14123451332623732337254232356253163522343152233423152257423152225423135222542311贪婪法的例子_货郎担问题(续)只选择一个城市作为出发城市,所需时间是n个城市都可以作为出发城市,所需时间是从城市1出发的最优的路线是125431,总费用只有13123451332623732337254232356253)n(O2)n(O3125.2背包问题一背包问题二思想方法三数据结构四算法描述五算法分析13一背包问题载重量为M的背包,重量为、价值为的物体,1in,把物体装满背包,使背包内的物体价值最大物体可以分割的背包问题,及物体不可分割的背包问题,把后者称为0/1背包问题iwip14二思想方法解向量::物体被装入背包的部分,:物体没被装入背包;:物体被全部装入背包约束方程:目标函数:选取价值重量比最大的物体装入,既使目标函数的值增加最快,又使背包载重量的消耗较慢)x,,x,x(=Xn21ix1x0i≤≤0=xi1=xiM=xwin1=ii∑in1=iixpmax=d∑15三数据结构typedefstruct{floatp;//n个物体的价值floatw;//n个物体的重量floatv;//n个物体的价值重量比}OBJECT;OBJECTinstance[n];floatx[n];//n个物体装入背包的份量16四算法描述1.floatknapsack_greedy(floatM,OBJECTinstance[],floatx[],intn)2.{inti;4.floatm,p=0;5.for(i=0;in;i++){O(n)6.instance[i].v=instance[i].p/instance[i].w;7.x[i]=0;8.}9.merge_sort(instance,n);O(nlogn)10.m=M;17算法描述(续)11.for(i=0;in;i++){O(n)12.if(instance[i].w=m)13.x[i]=1;m-=instance[i].w;14.p+=instance[i].p;15.}16.else{17.x[i]=m/instance[i].w;18.p+=x[i]*instance[i].p;19.break;20.}22.returnp;23.}18五算法分析当物体的价值重量比按递减顺序排序后,算法可求得背包问题的最优解证明:设解向量为,分两种情况:1.解向量X中,,物体已全部装入,是最优解2.解向量X中存在j,1jn,使得,,有:(1)假定,算法的最优解是,并且满足(2))x,,x,x(=Xn21n~1=i,1=xi1=x==x=x1j211x0j≤0=x==xn1+jM=M=xw1in1=ii∑)y,,y,y(=Yn21M=M=yw2in1=ii∑19算法分析(续1)若XY,必存在k,对1ik,有,对k,有,这时,有两种情况:1)因为所以根据算法的执行,有则与(1),(2)式矛盾,所以X=Y2)不会全为0iiy=xkkyx≠kkyx1yk≤1xk0=x==xn1+k21MMkkyxik1=iiik1=iiin1=iiywxwxw=M∑∑≥∑n1+ky,,y20算法分析(续2)令并使相应减小得到新解当1ik时有:当i=k时有:当kin时有:并且满足kkkx=yΔ+yn1+ky,,y)z,,z,z(=Zn21iiix=y=zkkkx=zyiiyz0=w)zy(w)yz(iin1+k=iikkk-∑--21算法分析(续3)令若,则Z是一个新的最优解若,则Z与Y同为最优解在此两种情况下,都用Z取代Y,并且对所有的1ik,都有:,而对k+1in,有:对向量Z重复上述步骤,最终必有:对所有的1in,都有:因此,X是最优解nnnnn1+k1+k1+k1+k1+kkkkkkw)zy(wpw)zy(wpw)yz(wp=δ----0=)w)zy(w)zy(w)yz((wpnnn1+k1+k1+kkkkkk----≥0δ0=δiix=ziixz≠iix=z225.3单源最短路径问题一解最短路径的狄斯奎诺(Dijkstra)算法二狄斯奎诺算法的描述三狄斯奎诺算法的分析23一解最短路径的狄斯奎诺(Dijkstra)算法1.单源最短路径问题2.狄斯奎诺算法的实现步骤3.例子241.单源最短路径问题有向赋权图G=V,E,求源顶点u到其它所有顶点的距离252.狄斯奎诺算法的实现步骤1)记号约定::边(u,v)的长度:顶点u到顶点v的距离p(x):从顶点u到顶点x的最短路径中的前一顶点V划分为集合S和T:S中的顶点到u的距离已定T中的顶点到u的距离未定。v,ucv,ud26狄斯奎诺算法的实现步骤(续)2)实现步骤:①S={u},T=V–{u}②xT,若(u,x)E,则,p(x)=u,否则,,p(x)=-1;③寻找tT,使得④S=ST,T=T–{t}⑤若T=,算法结束;否则,转⑥⑥对与t相邻接的所有顶点x,如果转③;否则,令,p(x)=t,转③x,ux,uc=d∞=dx,u}Tx|d{min=dx,ut,u∈x,tt,ux,uc+dd≤x,tt,ux,uc+d=d273.例子求图中顶点a到其它所有顶点的距离邻接矩阵如下:be191262435acfh434137dga0b1c4d4b0c2e9c0d3e6f3g4d0g7e0h1f0e2h5g0f1h3h028例子(续1)求图中顶点a到其它所有顶点的距离的求解过程be191262435acfh434137dgSdabdacdaddaedafdagdahdatt1a1441b2ab34103c3abc49674d4abcd9676f5abcdf87117g6abcdfg8108e7abcdfge99h8abcdfgeh29例子(续1)顶点a到其它所有顶点的路径be191262435acfh434137dgbacbadaefcbafcbagcbahefcba30二狄斯奎诺算法的描述1.数据结构2.算法描述311.数据结构typedefstructadj_list{//邻接表结点的数据结构intv_num;//邻接顶点的编号floatlen;//邻接顶点与该顶点的距离structadj_list*next;//下一个邻接顶点}NODE;NODEnode[n];//邻接表头结点floatd[n];//顶点到源顶点的距离intp[n];//顶点到源顶点的最短路径上前//方顶点的编号BOOLs[n];//为真,顶点在S中,否则,不在中322.算法描述(初始化,步骤①)1.#defineMAX_FLOT_NUM∞//最大的浮点数2.voiddijkstra(NODEnode[],intn,intu,floatd[],intp[])3.{4.floattemp;5.inti,j,t;6.BOOL*s=newBOOL[n];7.NODE*pnode;8.for(i=0;in;i++){//初始化9.d[i]=MAX_FLOAT_NUM;s[i]=FALSE;p[i]=-1;O(n)10.}狄斯奎诺算法的实现步骤(续)33算法描述(步骤①②)11.if(!(pnode=node[u].next))//源顶点与其它顶点不12.return;//相邻接13.while(pnode){//预置与源顶点相邻接14.d[pnode-v_num]=pnode-len;//的顶点距离15.p[pnode-v_num]=u;16.pnode=pnode-next;O(n)17.}18.d[u]=0;s[u]=TRUE;//开始时,集合S仅包含//顶点u狄斯奎诺算法的实现步骤(续)34算法描述(步骤③④)19.for(i=1;in;i++){20.temp=MAX_FLOAT_NUM;t=u;21.for(j=0;jn;j++)//在T中寻找距离u22.if(!s[j]&&d[j]temp){//最近的顶点t23.t=j;temp=d[j];24.}25.if(t==u)berak;//找不到,跳出循环26.s[t]=TRUE;//否则,把t并入集合s狄斯奎诺算法的实现步骤(续))n(O235算法描述(步骤③④)27.pnode=node[t].next;//更新与t相邻接的28.while(pnode){//顶点到u的距离29.if(!s[pnode-v_num]&&d[pnode-v_num]d[t]+pnode-len){30.d[pnode-v_num]=d[t]+pnode-len;31.p[pnode-v_num]=t;32.}33.pnode=pnode-next;O(n)34.}35.}36.deletes;37.}狄斯奎诺算法的实现步骤(续)36三狄斯奎诺算法的分析1.时间复杂性:2.算法正确性证明:略)n(O2375.4最小花费生成树问题一最小花费生成树引言二克鲁斯卡尔(Kluskal)算法三普里姆(Pri
本文标题:第五章贪婪法
链接地址:https://www.777doc.com/doc-2085347 .html