《算法设计和分析资料报告课程论文设计.doc》由会员分享，可在线阅读，更多相关《算法设计和分析资料报告课程论文设计.doc（8页珍藏版）》请在课桌文档上搜索。
1、word 贪心法的应用摘要：在解决问题的过程中，通过逐步获得最优解从而获得整体最优解的策略就是贪心策略，在已经学会在解的围可以确定的情况下，可以采用枚举或递归策略，一一比拟它们最后找到最优解；但当解的围非常大时，枚举和递归的效率会非常低。这时就可以考虑用贪心策略。贪心算法没有固定的框架，算法设计的关键是贪心策略的选择，贪心策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略的影响。当一个问题有好几种解决方法时，贪心法应该是最好的选择之一。本文讲述了贪心算法的含义、根本思路以与贪心算法在实例中的应用。关键词：贪心算法；删数问题；最小生成树1、 引言在平时解决问题的过程中，当一个问
2、题就有无后向性和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下就有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化解为一个更小的与原问题具有一样形式的子问题。尽管贪心算法对于很多问题不能总是产生整体最优解，但对于最短路径、最小生成树问题，以与删数问题等却可以获得整体最优解，而且所给出的算法一般比动态规划算法更为简单、直观和高效。2、 贪心算法的含义和特点（1） 贪心算法的含义 贪心算法是通过一系列的选择来得到问题解的过程。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出
3、在当前看来是最有的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。（2） 贪心算法的特点 1、从全局来看，运用贪心策略解决的问题在程序运行过程中无回溯过程，后面的每一步都是当前看似最优的选择，这种选择依赖已作出的选择，但并不依赖未作出的选择。 2、不能保证最后求出的解是最优的。由于贪心策略总是采用从局部看来是最优的选择 ，并不从整体上加以考虑 。另外贪心算法只能用来求某些最大或最小解的问题，因为当遇到求解权值最小路径等问题采用贪心算法得到的结果并不是最优。2、 贪心算法在实例中的应用（1） 删数问题给定n位正整数a，去掉其中任意k个数字后，剩下的数
4、字按原次序排列组成一个新的正整数。对于给定的位正整数和正整数，设计一个算法找出剩下数字组成的新数最小的删数方案。、 算法原理从最高位开始，依次向低位搜索，一旦遇到前一位高数的数大于当前位，如此删去前一位，直到删除个数，如果到达末尾还没有删除个，如此说明现在这个数已经是从小到大排列了，如此从最低位开始删除要求的位数。、 过程分析 k=3比大删除比大删除 6比3大删除 只看这个实例，有可能归纳不出正确的算法，看下一个实例，再进一步解释。 n2=2 k=33比1大删除 2 2比1大删除 8比3大删除 由实例n1，相邻数字只需从前向后比拟；而从实例n2 中可以看出当第i位与第i+1位比拟，假设删除第i
5、位后，必须向前考虑第i-1位与第i+1位进展比拟，才能保真结果的真确性。（2） 最小生成树设G = (V, E)是一个无向连通带权图，即一个网络。E的每条边(v, w)的权为cvw。如果G的一个子图G是一棵包含G的所有顶点的树，如此称G为G的生成树。生成树的各边的权的总和称为该生成树的消耗。在G的所有生成树中，消耗最小的生成树称为G的最小(优)生成树。1、 算法原理（1） Prim算法 根本思想：在保证连通的前提下依次选出权重较小的n 1条边。G=(V, E)为无向连通带权图，令V=1, 2, , n。设置一个集合S ，初始化S = 1，T = 。贪心策略：如果VS中的顶点j与S中的某个点i连
6、接且(i, j)是E中的权重最小的边，于是就选择j(将j参加S)，并将(i, j) 参加T中 。重复执行贪心策略，直至VS为空。（2） Kruskal算法 根本思想：在保证无回路的前提下依次选出权重较小的n 1条边。 贪心策略：如果(i, j)是E未被选中的边中权重最小的，并且(i, j)不会与已经选择的边构成回路，于是就选择 (i, j)。假设边(i, j) 的两个端点i和j属于同一个连通分支，如此选择(i, j) 会造成回路，反之如此不会造成回路。因此初始时将图的n个顶点看成n个孤立分支。（3） 两种算法的异同两种算法不同之处在于，Prim算法是在在保证连通的前提下依次选出权重较小的n 1
7、条边。而Kruskal算法在保证无回路的前提下依次选出权重较小的n 1条边。两种算法的一样之处在于都是在各自的前提条件下采取依次取出权值最小n-1条边的贪心策略。2、分析过程1Prim算法给定一个联通带权图如下：初始时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,66,4 ；第四次选择：(2, 3)权最小， S=1,3,6,4,2， T= (1,3)3,66,42,3 ；第五次选择：(2,5)权最小， S=1,
8、3,6,4,2,5， T= (1,3)3,66,42,32,5 ；（2） Kruskal算法 给定一个联通带权图如下： 初始时为六个孤立的点，选择了1，于是1、3点合并为同一个集合；选择了2，于是4、6点合并为同一个集合；选择了3，于是2、5点合并为同一个集合；选择了4，于是1、3、4、6点合并为同一个集合；考察边5，因为1、4为同一集合，故被放弃；选择了6，于是1、3、4、6、2、5点合并为同一个集合；选择了1，于是1、3点合并为同一个集合；已经选择边了n1条边，算法完毕。结果如如下图：3、 算法设计（1） Prim算法Prim(int n, Type *c) int j = 1; sj =
9、 true; /初始化将节点1放入s并初始化closest和lowcostfor (int i = 2; i = n; i+) closesti = 1; lowcosti=c1i; si=false;for (int i = 1; i n; i+) / /执行以下操作n-1次 min= inf; for (int k = 2; k = n; k+) /依据lowcost找出与s最近的点j并放入S if (lowcostkmin&!sk) min = lowcostk; j = k sj = true; for (int k = 2; k = n; k+) /调整closest和lowcost
10、 if (cjk lowcostk&!sk) lowcostk = cjk; closestk = j （2） Kruskal算法 Kruskal(int n, *e) Sort(e, w); /将边按权重从小到大排序 initialize(n); /初始时每个顶点为一个集合 k = 1; /k累计已选边的数目， j = 1; /j为所选的边在e中的序号 while (k n) /选择n 1条边 a = Find(eju); b = Find(ejv); /找出第j条边两个端点所在的集合 if (a != b) tk+ = j; Union(a, b) /假设不同，第j条边放入树中并合并这两个
11、集合 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算法好得多。3、 总结与展望一总结 贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最优的，但是它可以为某些问题确定一个可行性围。贪心算法所作的选
12、择依赖于以往所作过的选择，但决不依赖于将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比拟，它的适用区域相对狭窄许多。总之，如果一个贪心解决方案存在，就可以使用它。 二展望对于贪心算法的应用，如果某个问题具有贪心算法的贪心选择性质和最优子结构性质，那么，它就可以采用贪心策略进展分析，进而求解，贪心算法的应用举例不仅只有本论文中的那几个，他对于背包问题、最优装载问题、硬币找钱问题等都是十分方便有效的算法，贪心算法在科学计算和工程中的应用也越来越广泛，例如用贪心算法进展三角剖分的指纹匹配方法、贪心算法在竞赛中的应用、贪心算法在排课系统中的应用、贪心聚类算法与其在遥感图像分类和压缩中的应用等等，在未来出现的一些问题中，只要符合贪心算法的贪心策略性质，就可以用贪心算法求解，让贪心算法能够应用到更广更多的问题中去吧！【参考文献】1吕英国.任瑞征.钱宇华.算法设计与分析M.:清华大学.2URL wenku.baidu./view/f11d5d2a3169a4517723a341.html.8 / 8
