logo资料库

算法分析课程毕业论文.pdf

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：0.57M 资料格式：pdf 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    贪心算法设计及其实际应用研究 姜昱璇 浙江工业大学 计算机学院 数字媒体技术专业 1101 班 摘要：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择,也就是说，不从整体最优 上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解， 但对范围相当广泛的许多问题也能产生整体最优解或者是整体最优解的近似解。本文首先介绍了贪心算法 的核心、特点及算法本身存在的问题，然后结合实践研究了多处最优服务次序问题。最后进行总结和展望。 关键词：贪心算法；最优服务次序 Greedy algorithm design and its practical application JIANG Yu-xuan Zhejiang University Of Technology, College of Computer, Digital Media Technology ,Class 1101 Abstract：Greedy algorithm is that, in the problem solving, it always made in the current appears to be the best option. In other words, not the best on the whole to be considered, it made only a local optimal solution in a sense. Greedy algorithm is not a right that all problems can be the overall optimal solution, but it covers a wide range of issues that he could produce an overall optimal solution or approximate solution of the overall optimal solution. This paper describes the core of the greedy algorithm, characteristics and algorithms inherent problems. Then with practice, study the various optimal service order issues. At last, make a conclusion and outlook. Key words：greedy algorithm；Optimal service order 引言 当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直 观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都 是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简 为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对许多问题不能总是产生整体 最优解，但对诸如最短路径问题、最小生成树问题等具有最优子结构和贪心选择性质的问题 却可以获得整体最优解。而且所给出的算法一般比动态规划算法更加简单、直观和高效。 贪心算法的定义（是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或 较优解)的一种解题方法），贪心算法的基本要素（最优子结构性质、贪心选择性质）、贪心 算法的思路及过程，贪心算法的核心（贪心策略）及特性（无回溯）、探讨贪心算法存在的 问题。然后结合实际中的例子（多处最优服务次序问题），对贪心算法进行分析与运用。
    通过研究来探讨贪心算法理论基础以及对贪心策略在更多实例中的运用做可行的研究， 为贪心算法能够运用到更多的实际中的问题作示范。 贪心算法是计算机算法策略中常用的一个，往往在需要解决一些最优性问题时，都可以 应用贪心算法。贪心算法的用法特点有：一是明显的贪心，一般此类应用问题本身就是贪心； 二是贪心数据结构，如：堆，最小树；三是可证明贪心策略的贪心，这是我们最常见的；四 是博弈、游戏策略，这些策略大多是贪心；五是求较优解或多次逼近最优解。通过用贪心算 法求解以上问题，可以找到解决这些问题的最优算法，为其它的类似问题的解决有示范和例 证作用。 本文从如下方面进行组织：先提出贪心算法的基本知识，再从贪心算法的几个现有的成 果研究探讨，然后对贪心算法中的几个经典问题进行研究，最后进行总结。 1 贪心算法的基本知识概述 1.1 贪心算法定义 贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小 值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选 择，从而希望得到结果是最好或最优的算法。 贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择 来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心 选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种策略是一种很简洁的方 法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得 到整体最优解，只能说其解必然是最优解的很好近似值。 1.2 贪心算法的基本思路及实现过程 1.2.1 贪心的基本思想 用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求 得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就 是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都 处理出一个最好的方案。 利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解；
    （2）如何选择贪心标准，以得到问题的最优/较优解。 1.2.2 贪心算法的实现过程 （1）应用同一规则 F，将原问题变为一个相似的、但规模更小的子问题； （2）从问题的某一初始解出发： While（能朝给定目标前进一步） 求出可行解的一个解元素； （3）由所有解元素组合成问题的一个可行解。 1.3贪心算法的核心 贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解) 的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看 来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种 意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较 优解。 1.4贪心算法的基本要素 1.4.1 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心 选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区 别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关 子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选 择。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于 以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种 差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方 式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更 小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择 最终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解， 使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用数 学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选
    择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 1.4.2 最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪 心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动 态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则 不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的 选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般 是一维问题。 1.4.3 贪心算法的特点 贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方 级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些 空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因 为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最 好的。但是应该注意，贪心算法有两大难点： （1）如何贪心 怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分 都是有规律的。正因为贪心有如此性质，它才能比其他算法快。 具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时， 看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问 题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有 特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当 一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现， 单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。 （2）贪心的正确性 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会 与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就 成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可 行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然 正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并 不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。
    1.5 贪心算法存在的问题 （1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选 择，因此并不从整体上加以考虑； （2）贪心算法只能用来求某些最大或最小解的问题； （3）贪心算法只能确定某些问题的可行性范围。 2 多处最优服务次序问题 2.1 问题的提出 设有 n 个顾客同时等待一项服务。顾客 i 需要的服务时间为 ti，1<=i<=n。共有 s 处可 以提供此项服务。应如何安排 n 个顾客的服务次序才能使平均等待时间达到最小？平均等待 时间是 n 个顾客等待服务时间的总和除以 n。 2.2 贪心选择策略 假设原问题为 T，而我们已经知道了某个最优服务系列，即最优解为 A={t(1)， t(2)，…．t(n)}(其中 t(i)为第 i 个用户需要的服务时间)，则每个用户等待时间为： T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)； 那么总等待时问，即最优值为： TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)； 由于平均等待时间是 n 个顾客等待时间的总和除以 n，故本题实际上就是求使顾客等待 时间的总和最小的服务次序。 本问题采用贪心算法求解，贪心策略如下：对服务时间最短的顾客先服务的贪心选择策 略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题 T 变成了需对 n-1 个顾客服务的新问题 T’。新问题和原问题相同，只是问题规模由 n 减小为 n-1。基于此 种选择策略，对新问题 T’，选择 n-1 顾客中选择服务时间最短的先进行服务，如此进行下 去，直至所有服务都完成为止。 2.3 问题的贪心选择性质 先 来 证 明 该 问 题 具 有 贪 心 选 择 性 质 ， 即 最 优 服 务 A 中 t(1) 满 足 条 件 ： t(1)<=t(i)(2t(i)(i>1)。 设另一服务序列 B=（t(i)，t(2)，…，t(1)…，t(n)） 那么
    TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0 即 TA>TB，这与 A 是最优服务相矛盾。 故最优服务次序问题满足贪心选择性质。 2.4 问题的最优子结构性质 在进行了贪心选择后，原问题 T 就变成了如何安排剩余的 n-1 个顾客的服务次序的问题 T’，是原问题的子问题。 若 A 是原问题 T 的最优解，则 A’={t(2)，…t(i)…t(n))是服务次序问题子问题 T’的 最优解。 证明：假设 A’不是子问题 T’的最优解，其子问题的最优解为 B’，则有 TB’
    问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、 动态规划法等比较，它的适用区域相对狭窄许多。总之，如果一个贪心解决方案存在，就可 以使用它。 3.2 展望 对于贪心算法的应用，如果某个问题具有贪心算法的贪心选择性质和最优子结构性质， 那么，它就可以采用贪心策略进行分析，进而求解，贪心算法的应用举例不仅只有本论文中 的那几个，他对于背包问题、最优装载问题、硬币找钱问题等都是十分方便有效的算法，贪 心算法在科学计算和工程中的应用也越来越广泛，例如用贪心算法进行三角剖分的指纹匹配 方法、贪心算法在竞赛中的应用、贪心算法在排课系统中的应用、贪心聚类算法及其在遥感 图像分类和压缩中的应用等等，在未来出现的一些问题中，只要符合贪心算法的贪心策略性 质，就可以用贪心算法求解，让贪心算法能够应用到更广更多的问题中去吧！ 参考文献： [1] 王晓东.计算机算法设计与分析(第 4 版)[M].北京：电子工业出版社,2012． [2] M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京:电子工业出版社,2004． [3] 谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006． [4] 常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,第 13 卷，第 13 期，2008.9. [5] 张洁,朱莉娟.贪心算法与动态规划的比较[M].新乡师范高等专科科学学报,第 19 卷，第五期，2005.9. [6] 殷建平.关于贪心算法的正确性证明[M].江西师范大学学报（自然科学版）,第 22 卷增刊,1998.10. [7] 李盘林,李丽双.离散数学[M].北京:高教出版社,1999． [8] 陈媛.《算法与数据结构》[M],清华大学出版社, 第 1 版,2005.4. [9]URL http://baike.baidu.com/view/298415.htm?fr=ala0 [10]URL http://blog.sina.com.cn/s/blog_5cd377280100artn.html [11]Computer Algorithms—Introduction to Design and Analysis(Third Edition)，高等教育出 版社，2001.7 [13] MelhiM,Ipson S S,Boothw. A novel triangulation procedure for thinning hand written text[J].Pattern Recognition Letters,2001,22(10):1059-1071. [14] Florescu D,Grunhagen A,Kossmann D.XL:A Platform for Web Services[C].Proc.of the 1st Biennial Conference on innovative Data Systems Research, 2003 [15] Thomas H.Cormen et.Introduction to algorithms[M].北京:高教出版社,20O2． [16] Donald E．knuth.arf of computer proquamming.VoI [M].北京:清华大学出版社,2000．
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料