搜索
1湖南理工学院课程论文论文题目贪心法的应用课程名称算法设计与分析姓名学号专业计算机科学与技术年级学院计算机日期（2014年4月10日）课程论文评价标准指标评价内容评价等级（分值）得分ABCD选题选题是否新颖；是否有意义；是否与本门课程相关。20-1615-1110-65-0论证思路是否清晰；逻辑是否严密；结构是否严谨；研究方法是否得当；论证是否充分。20-1615-1110-65-0文献文献资料是否翔实；是否具有代表性。20-1615-1110-65-0规范文字表达是否准确、流畅；是否符合学术道德规范。20-1615-1110-65-0能力是否运用了本门课程的有关理论知识；是否体现了科学研究能力。20-1615-1110-65-0评阅教师签名：年月日总分：2贪心法的应用摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的范围可以确定的情况下，可以采用枚举或递归策略，一一比较它们最后找到最优解；但当解的范围非常大时，枚举和递归的效率会非常低。这时就可以考虑用贪心策略。贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路以及贪心算法在实例中的应用。关键词：贪心算法；删数问题；最小生成树一、引言在平时解决问题的过程中，当一个问题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以及删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。二、贪心算法的含义和特点（一）贪心算法的含义贪心算法是通过一系列的选择来得到问题解的过程。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。（二）贪心算法的特点31、从全局来看，运用贪心策略解决的问题在程序运行过程中无回溯过程，后面的每一步都是当前看似最佳的选择，这种选择依赖已作出的选择，但并不依赖未作出的选择。2、不能保证最后求出的解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，并不从整体上加以考虑。另外贪心算法只能用来求某些最大或最小解的问题，因为当遇到求解权值最小路径等问题采用贪心算法得到的结果并不是最佳。二、贪心算法在实例中的应用（一）删数问题给定n位正整数a，去掉其中任意k≤ｎ个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的ｎ位正整数ａ和正整数ｋ，设计一个算法找出剩下数字组成的新数最小的删数方案。１、算法原理从最高位开始，依次向低位搜索，一旦遇到前一位（高数）的数大于当前位，则删去前一位，直到删除ｋ个数，如果到达末尾还没有删除ｋ个，则说明现在这个数已经是从小到大排列了，则从最低位开始删除要求的位数。２、过程分析ｎ１＝＂１２４３５８６３＂k=3４比３大删除＂１２３５８６３＂８比６大删除＂１２４３５６３＂6比3大删除＂１２４３５８３＂只看这个实例，有可能归纳不出正确的算法，看下一个实例，再进一步解释。n2=＂2３１１８３＂k=33比1大删除＂2１１８３＂2比1大删除＂１１８３＂8比3大删除＂１１３＂由实例n1，相邻数字只需从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保真4结果的真确性。（二）最小生成树设G=(V,E)是一个无向连通带权图，即一个网络。E的每条边(v,w)的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树的各边的权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小(优)生成树。1、算法原理（1）Prim算法基本思想：在保证连通的前提下依次选出权重较小的n–1条边。G=(V,E)为无向连通带权图，令V={1,2,…,n}。设置一个集合S，初始化S={1}，T=Φ。贪心策略：如果V–S中的顶点j与S中的某个点i连接且(i,j)是E中的权重最小的边，于是就选择j(将j加入S)，并将(i,j)加入T中。重复执行贪心策略，直至V–S为空。（2）Kruskal算法基本思想：在保证无回路的前提下依次选出权重较小的n–1条边。贪心策略：如果(i,j)是E中尚未被选中的边中权重最小的，并且(i,j)不会与已经选择的边构成回路，于是就选择(i,j)。若边(i,j)的两个端点i和j属于同一个连通分支，则选择(i,j)会造成回路，反之则不会造成回路。因此初始时将图的n个顶点看成n个孤立分支。（3）两种算法的异同两种算法不同之处在于，Prim算法是在在保证连通的前提下依次选出权重较小的n–1条边。而Kruskal算法在保证无回路的前提下依次选出权重较小的n–1条边。两种算法的相同之处在于都是在各自的前提条件下采取依次取出权值最小n-1条边的贪心策略。2、分析过程（1）Prim算法5给定一个联通带权图如下：初始时S={1}，T=Φ；第一次选择：(1,3)权最小，S={1,3}，T={(1,3)}；第二次选择：(3,6)权最小，S={1,3,6}，T={(1,3)（3,6）}；第三次选择：(4,6)权最小，S={1,3,6,4}，T={(1,3)（3,6）（6,4）}；第四次选择：(2,3)权最小，S={1,3,6,4,2}，T={(1,3)（3,6）（6,4）（2,3）}；第五次选择：(2,5)权最小，S={1,3,6,4,2,5}，T={(1,3)（3,6）（6,4）（2,3）（2,5）}；（2）Kruskal算法给定一个联通带权图如下：初始时为六个孤立的点，选择了1，于是1、3点合并为同一个集合；选择了2，于是4、6点合并为同一个集合；选择了3，于是2、5点合并为同一个集合；选择了4，于是1、3、4、6点合并为同一个集合；考察边5，因为1、4为同一集合，故6被放弃；选择了6，于是1、3、4、6、2、5点合并为同一个集合；选择了1，于是1、3点合并为同一个集合；已经选择边了n–1条边，算法结束。结果如图所示：3、算法设计（1）Prim算法Prim(intn,Type**c){intj=1;s[j]=true;//初始化将节点1放入s并初始化closest[]和lowcost[]for(inti=2;i=n;i++){closest[i]=1;lowcost[i]=c[1][i];s[i]=false;}for(inti=1;in;i++){//执行以下操作n-1次min=inf;for(intk=2;k=n;k++){//依据lowcost[]找出与s最近的点j并放入Sif(lowcost[k]min&&!s[k]){min=lowcost[k];j=k}s[j]=true;}7}for(intk=2;k=n;k++){//调整closest[]和lowcost[]if(c[j][k]lowcost[k]&&!s[k]){lowcost[k]=c[j][k];closest[k]=j}}}（2）Kruskal算法Kruskal(intn,**e){Sort(e,w);//将边按权重从小到大排序initialize(n);//初始时每个顶点为一个集合k=1;//k累计已选边的数目，j=1;//j为所选的边在e中的序号while(kn)//选择n–1条边{a=Find(e[j][u]);b=Find(e[j][v]);//找出第j条边两个端点所在的集合if(a!=b){t[k++]=j;Union(a,b)}//若不同，第j条边放入树中并合并这两个集合j++}}//继续考察下一条边4、Prim和kruskal算法两者的复杂性Prim算法为两重循环，外层循环为n次，内层循环为O(n)，因此其复杂性为O(n2)。Kruskal算法中，设边数为e，则边排序的时间为O(e)，确定边的时间为O(loge)，所以整个时间复杂性为O(eloge)。当e=Ω(n2)时，Kruskal算法要比Prim算法差；当e=ο(n2)时，Kruskal算法比Prim算法好得多。三、总结与展望（一）总结贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行8性范围。贪心算法所作的选择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。总之，如果一个贪心解决方案存在，就可以使用它。（二）展望对于贪心算法的应用，如果某个问题具有贪心算法的贪心选择性质和最优子结构性质，那么，它就可以采用贪心策略进行分析，进而求解，贪心算法的应用举例不仅只有本论文中的那几个，他对于背包问题、最优装载问题、硬币找钱问题等都是十分方便有效的算法，贪心算法在科学计算和工程中的应用也越来越广泛，例如用贪心算法进行三角剖分的指纹匹配方法、贪心算法在竞赛中的应用、贪心算法在排课系统中的应用、贪心聚类算法及其在遥感图像分类和压缩中的应用等等，在未来出现的一些问题中，只要符合贪心算法的贪心策略性质，就可以用贪心算法求解，让贪心算法能够应用到更广更多的问题中去吧！【参考文献】[1]吕英国.任瑞征.钱宇华.算法设计与分析[M].北京:清华大学出版社.[2]URL