计算理论与算法12年CH4贪心课件.ppt
《计算理论与算法12年CH4贪心课件.ppt》由会员分享,可在线阅读,更多相关《计算理论与算法12年CH4贪心课件.ppt(93页珍藏版)》请在三一办公上搜索。
1、贪心法(贪婪法),2023/4/1,2 of 158,数钱一出纳员支付一定数量的现金。假设他手中有各种面值的纸币和硬币,要求他用最少的货币数支付规定的现金。例如,现有4种硬币:它们的面值分别为1分、2分、5分和1角。要支付2角5分。首先支付2个1角硬币,然后支付一个5分硬币,这就是贪心策略。,2023/4/1,3 of 158,贪心法不一定能产生正确的答案。例如,若引进一个1角1分的硬币,设从如下集合1,1,2,2,2,5,10,10,11,11中数出25分,按贪心法,共4个硬币。但最优解仅为3个硬币。这说明贪心法得到的解只是一个可行解。,2023/4/1,4 of 158,货郎担(TSP)问
2、题,设售货员要到五个城市去售货,最后再回到出发的城市。已知从一个城市到其他城市的费用,求总费用最少的路线,2023/4/1,5 of 158,权为13,从不同结点出发:1)结点a为起点:2)结点b为起点:3)结点c为起点:4)结点d为起点:,权为13,权为13,权为13,或者15,2023/4/1,6 of 158,而实际上图中最短哈密顿回路的长度为12。即abcda,2023/4/1,7 of 158,Huffman编码,某通讯系统只使用5种字符a、b、c、d、e,使用频率分别为0.1,0.14,0.2,0.26,0.3,利用二叉树设计不等长编码:1)构造以 a、b、c、d、e为叶子的二叉树
3、;2)将该二叉树所有左分枝标记0,所有右 分枝标记1;3)从根到叶子路径上标记作为叶子结点所 对应字符的编码;,2023/4/1,8 of 158,a:000 b:001c:01 d:10e:11,5种字符a、b、c、d、e,使用频率分别为0.1,0.14,0.2,0.26,0.3,30000-(1000+1400)*3-(2000+2600+3000)*2=7600,2023/4/1,9 of 158,Huffman编码:贪心选择性质,算法导论P234以及教材P112,2023/4/1,10 of 158,Huffman编码:贪心选择性质,2023/4/1,11 of 158,背包问题,已知
4、一个容量大小为M重量的背包和n种物品,物品i的重量为wi,假定物品i的一部分xi放入背包会得到vixi这么大的收益,这里,0 xi1,vi0。采用怎样的装包方法才会使装入背包的物品总效益最大?例:考虑以下情况下的背包问题n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10),2023/4/1,12 of 158,n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10),1)按效益值非增次序将物品依次放入背包(x1,x2,x3)wixi vixi2)按物品重量的非降次序将物品依次放入背包,(1,2/15
5、,0),20,28.2,(0,2/3,1),20,31,2023/4/1,13 of 158,n=3,M=20,(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10),3)按vi/wi的非增次序将物品依次放入背包(x1,x2,x3)wixi vixi,(0,1,1/2),20,31.5,算法:背包问题的贪心算法,2023/4/1,14 of 158,void GreedyKnapsack(int n,float M,float v,float w,float x)Sort(n,v,w);/使v1/w1v2/w2vn/wn for(int i=1;ic)break;
6、xi=1;c-=wi;if(i=n)xi=c/wi;,2023/4/1,15 of 158,算法的时间复杂性为 O(nlogn)下面来证明使用此贪心算法所得到的贪心解是一个最优解。证明的基本思想是:把这个贪心解与任一个最优解相比较,如果这两个解不同,就去找开始不同的第一个xi,然后设法用贪心解的这个xi去代换最优解的那个xi,并证明在分量作了代换,2023/4/1,16 of 158,之后其总效益与代换之前无任何损失。反复进行这种代换,直到新产生的最优解与贪心解完全一样,从而证明了贪心解是最优解。定理:如果v1/w1 v2/w2 vn/wn,则此算法对于给定的背包问题实例生成一个最优解。,20
7、23/4/1,17 of 158,2023/4/1,18 of 158,j是使xj 1的最小下标,k是使 yk xk的最小下标。,X=(1,1,1/2,0)Y=(1,1,2/3,1/3)j=3,k=3,所以k=j,并且y3x3,(2)X=(1,1,1/2,0)Y=(1,1,1/2,1/2)j=3,k=4,所以kj,并且y4x4,从而证明了ykxk,并且k=j,2023/4/1,19 of 158,j是使xj 1的最小下标,k是使 yk xk的最小下标。,n=4,M=16,(v1,v2,v3,v4)=(20,12,6,6)(w1,w2,w3,w4)=(10,12,6,6)X=(1,1/2,0,0
8、)Y=(1,1/3,1/6,1/6)并且k=2,j=2,Z=(1,1/2,z3,z4),代换,w3(y3z3)+w4(y4z4)=w2(1/21/3),6(1/6z3)+6(1/6z4)=12*1/6,z3+z4=0,即推得Z=(1,1/2,0,0)X,2023/4/1,20 of 158,2023/4/1,21 of 158,有限期的任务安排问题,用贪心法求解有限期的任务安排问题:假设只能在同一台机器上加工n个任务,每个任务i完成时间均是一个单位时间。又设每个任务i都有一个完成期限di0,当且仅当任务i在它的期限截止以前被完成时,任务i才能获得pi的效益,每个任务的期限从整个工序的开工开始计
9、时,问应如何安排加工顺序,才能获得最大效益?n=6,(p1,p2,p3,p4,p5,p6)=(5,25,20,30,10,15),(d1,d2,d3,d4,d5,d6)=(1,5,2,3,3,2),2023/4/1,22 of 158,有限期的任务安排问题首先按效益非增次序进行排序,然后按照期限依次对此次序进行调整,排在后面的或提前或排除。算法的粗略描述void Greedy-Job(D,J,n)/*任务按 p1 p2 pn 的次序输入,它们的期限值Di 1,1in,n 1,J是可以在它们的期限截止前完成的任务的集合*/,2023/4/1,23 of 158,J 1;for(i=2;i=n;i
10、+)if(Ji 的所有任务都能在它 们的截止期限前完成)J Ji;定理:算法Greedy-Job对于有期限的任务安排问题得到一个最优解。证明:X Y Z 贪心解 最优解,2023/4/1,24 of 158,假设n个任务已按 p1 p2 pn 排序。首先将任务1存入解数组J中,然后处理任务2到任务n。假设已处理了i-1个任务,其中有k个任务已记入J(1),J(2),J(k)之中,并且有d(J(1)d(J(2)d(J(k)。现在处理任务i。为了判断Ji是否可行,只需看能否找出这样的位置:可以按期限的非降次序插入任务i,使得i在此处插入后,有 d(J(r)r,1 r k+1。,2023/4/1,2
11、5 of 158,找任务i可能的插入位置可如下进行:(a)若d(i)d(J(k),即任务i的期限比这k个任务的所有期限都长,则i可直接加入到k个任务的后面,即J(k+1)=i(b)将d(J(k),d(J(k-1),d(J(1)逐个与d(i)比较,直到找到位置q,它使得d(J(q)d(i)d(J(t)qtk,2023/4/1,26 of 158,此时若d(J(t)t qtk 这说明:第t个要加工的任务以及它以后加工的所有任务都可以向后移动一个单位时间。即这k-q个任务均可延迟一个单位时间加工。在以上条件成立的情况下,只要 d(i)q+1,就可将任务i插入到第q+1个位置上,从而得到一个按期限的非
12、降次序排列的含有k+1个任务的可行解。,2023/4/1,27 of 158,以上过程反复进行到对第n个任务处理完毕。所得到的贪心解就是一个最优解。任务 0 1 2 3 4 5 6 pi 0 30 25 20 15 10 5 di 0 3 5 2 2 3 1J(1)=3 J(2)=4 J(3)=1 J(4)=2 总效益:90,2023/4/1,28 of 158,void greedy-job(d,J,n,k)/*任务按 p1 p2 pn 的次序输入,它们的期限值d(i)1,1in,n 1,J(i)是最优解中的第i个任务,结束时d(J(i)d(J(i+1)*/,2023/4/1,29 of 1
13、58,d(0)0;J(0)0;k 1;J(1)1;for(i=2;id(i)if(d(J(q)d(i)&d(i)q),2023/4/1,30 of 158,for(t=k;t=q+1;t-)J(t+1)J(t);J(q+1)i;k k+1;,2023/4/1,31 of 158,活动安排:问题描述,有n个活动集E=1,2,n使用同一资源,而同一时间内同一资源只能由一个活动使用。每个活动的使用时间为si,fi)i=1,n,si为开始时间,fi为结束时间,若si,fi)与sj,fj)不相交称活动i和活动j是相容的。,问题:选出最大的相容活动子集合。,2023/4/1,32 of 158,贪心策略
14、将各活动按结束时间排序f1f2fn,先选出活动1,然后按活动编好从小到大的次序依次选择与当前活动相容的活动。,注:这种策略使剩余的可安排时间极大化,以便于安排尽可能多的相容活动。证明:见算法导论P224,2023/4/1,33 of 158,2023/4/1,34 of 158,void ActivitySelection(int n,s,f,bool a)/f已排序,a记录选择的活动,即ai=true表示活动i已选择 a1=true;int j=1;for(int i=2;i=fj)ai=true;j=i;else ai=false;,T(n)=O(nlogn),2023/4/1,35 of
15、 158,活动安排:计算示例,11个活动已按结束时间排序,用贪心算法求解:i 1 2 3 4 5 6 7 8 9 10 11start_timei 1 3 0 5 3 5 6 8 8 2 12finish_timei 4 5 6 7 8 9 10 11 12 13 14,相容活动:a3,a9,a11,a1,a4,a8,a11,a2,a4,a9,a11,2023/4/1,36 of 158,最小生成树,最小生成树的定义Kruskal算法 Prim算法,2023/4/1,37 of 158,网络的最小生成树在实际中有广泛应用。例如,在设计通信网络时,用图的顶点表示城市,用边(v,w)的权cvw表示
16、建立城市v和城市w之间的通信线路所需的费用,则最小生成树就给出了建立通信网络的最经济的方案。,最小生成树,2023/4/1,38 of 158,最小生成树,设G=(V,E)是一个无向连通带权图,如果G的一个子图T是一棵包含G的所有顶点的树(G的生成树),生成树T上各边权的总和(生成树的耗费)最小,则T称为G的最小生成树(MST:minimum spanning tree),2023/4/1,39 of 158,Kruskal最小生成树算法 Kruskal 在1956年提出了1个最小生成树算法。设G=(V,E)是一个连通带权图,V=1,2,n。将图中的边按其权值由小到大排序,然后作如下的贪婪选择
17、,由小到大顺序选取各条边,若选某边后不形成回路,则将其保留作为树的一条边;若选某边后形成回路,则将其舍弃,以后也不再考虑。如此依次进行,到选够(n-1)条边即得到最小生成树。,最小生成树,2023/4/1,40 of 158,例如,对于下图中的带权图,各边按权值排序为:d13=1 d46=2 d25=3 d36c4 d14=5d34=5 d23=5 d12=6 d35=6 d56=6,2023/4/1,41 of 158,按Kruskal算法选取边的过程如下图所示。,2023/4/1,42 of 158,Kruskal最小生成树算法,最小生成树,/在一个具有n个顶点的网络中找棵最小生成树令E为
18、网络中边的集合令T为所选边的集合,初始化T为空集 while(E 不是空集 算法复杂度为O(n+eloge),2023/4/1,43 of 158,Prim最小生成树算法 Prim在1957年提出另一种算法,这种算法特别适用于边数相对较多,即比较接近于完全图的图。此算法是按逐个将顶点连通的步骤进行的,它只需采用一个顶点集合。这个集合开始时是空集,以后将已连通的顶点陆续加入到集合中去,到全部顶点都加入到集合中了,就得到所需的生成树。,最小生成树,2023/4/1,44 of 158,Prim最小生成树算法 设G=(V,E)是一个连通带权图,V=1,2,n。构造G的一棵最小生成树的Prim算法的过
19、程是:首先从图的任一顶点起进行,将它加入集合S中置,S=1,然后作如下的贪婪选择,从与之相关联的边中选出权值cij最小的一条作为生成树的一条边,此时满足条件iS,jV-S,并将该j加入集合中,表示连两个顶点已被所选出的边连通了。,最小生成树,2023/4/1,45 of 158,以后每次从一个端点在集合S中而另一个端点在集合S外的各条边中选取权值最小的一条作为生成树的一条边,并把其在集合外的那个顶点加入到集合S中。如此进行下去,直到全部顶点都加入到集合中S。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。由于Prim算法中每次选取的边两端总是一个已连通顶点和一个未连通顶点,故这个边选取后
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论 算法 12 CH4 贪心 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-4024588.html