资源描述：
《算法设计技巧与分析 第8章 贪心算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法设计技巧与分析AlgorithmsDesignTechniquesandAnalysis南方医科大学医工学院信息技术系第8章贪心算法理解贪心算法的基本原理掌握贪心算法的算法实例（难点）掌握用贪心算法设计算法的方法（重点）TeachingRequestContent贪心算法原理算法实例单源最短路径问题最小耗费生成树(Kruskal)最小耗费生成树(Prim)文件压缩Example：PackageProblem0-1背包问题：给定n种物品和一个背包。物品i的体积是si，其价值为vi，背包的容量为C。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？背包
2、问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。GreedyAlgorithmvoidKnapsack(intn,floatM,floatv[],floats[],floatx[]){Sort(n,v,s);//将各种物品按单位体积价值排序for(inti=1;i<=n;i++)x[i]=0;//将解向量初始化为零floatc=M;//将背包剩余容量初始化为Mfor(i=1;i<=n;i++){if(s[i]>c)break;x[i]=1;c-=s[i];}if(i<=n)x[i]=c/s[i];}首先
3、计算每种物品单位体积的价值vi/si，然后将尽可能多的单位体积价值最高的物品装入背包。SingleSourceShortestPaths设：G=(V,E)为一个有向图，每一条边都具有非负长度，有一个特异顶点s称为源。求：从s到V中每一个其他顶点v的距离，即最短路径δ(v)。假设：V={1,2,…,n}，并且s=1。BasePrincipleofDijkstra将顶点分为两个集合X和Y，其中X包含的是距离已经确定的顶点，令λ(y)为Y中顶点y只经过X中顶点的最短路径的长度，则1.初始时X={1}，Y={2,3,…,n}；2.从Y中选定距离已经确定的顶点y，将其移至X
4、；3.更新Y中与y相邻的其他顶点的标记；4.迭代直至Y为空。Example1234561129345131540112∞∞∞410198171317算法8.1 DIJKSTRA输入:含权有向图G=(V，E)，V=(1，2，···，n)。输出:G中顶点1到其他顶点的距离。2.fory←2ton5.endif6.endfor1.X=｛1｝;Y←V-｛1｝;[1]←04.else[y]←3.ify相邻于1then[y]←length[1，y]10.Y←Y-{y}{将顶点y从Y中删除}7.forj←1ton-19.X←X∪{y}{将顶点y加入X}11.for每条边(y，w
5、)14.endfor8.令yY，使得[y]为最小12.ifwYand[y]+length[y,w]<[w]then15.endfor13.[w]←[y]+length[y,w]在算法DIJKSTRA中，当顶点y在第8步中被选中，如果标记λ(y)是有限的，那么λ(y)=δ(y)。引理8.1TimeComplexity第8步：执行了n-1次，每次时间是Θ(n)共需时间Θ(n2)第11步：for循环执行了m次，m=
6、E
7、共需时间Θ(m)算法的时间复杂度：Θ(n2+m)定理8.1给出一个边具有非负权的有向图G和源顶点s，算法DIJKSTRA在时间内找出从s到其它每一顶点距
8、离的长度。AmendatoryAlgorithm思路：用最小堆数据结构来保持集合Y中的顶点，使Y组中离V-Y最近的顶点y可以在Ο(logn)时间内被选出。堆定义：是一个几乎完全的二叉树，总是保持父节点的键值不小于子节点的键值。堆运算：SIFT-UP、SIFT-DOWN、DELETEMAX、DELETE、INSERT、MAKEHEAP算法8.2 SHORTESTPATH输入:含权有向图G=(V，E)，V=(1，2，···，n)。输出:G中顶点1到其他顶点的距离，假设已有一个空堆H。2.fory←2ton3.ify邻接于1then6.INSERT(H，y)7.else
9、5.key[y]←[y]4.[y]←length[1，y]1.Y←V-｛1｝;[1]←0;key(1)←[1]8.[y]←9.key(y)←[y]10.endif11.endfor12.forj←1ton-114.Y←Y-{y}{将顶点y从Y中删除}19.endif13.y←DELETEMIN(H)15.for每个邻接于y的顶点wY16.if[y]+length[y,w]<[w]then20.ifwHthenINSERT(H，w)18.key(w)←[w]17.[w]←[y]+length[y,w]21.elseSIFTUP(，(w))22.endif23.end
10、for24
