贪心算法结课论文

《贪心算法结课论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、湖南理工学院课程论文论文题目贪心算法论文课程名称算法分析与设计姓名学号专业计算机科学与技术年级12级01班学院计算机学院日期（2014年4月13日）课程论文评价标准指标评价内容评价等级（分值）得分ABCD选题选题是否新颖；是否有意义；是否与本门课程相关。20-1615-1110-65-0论证思路是否清晰；逻辑是否严密；结构是否严谨；研究方法是否得当；论证是否充分。20-1615-1110-65-0文献文献资料是否翔实；是否具有代表性。20-1615-1110-65-0规范文字表达是否准确、流畅；是否符合学术道德规范。20-1615-1110-65-0能力是否运用了本门课程的有关理论知识

2、；是否体现了科学研究能力。20-1615-1110-65-0评阅教师签名：年月日总分：1引言随着科学的发展，人们生活屮面临的人数据最越来越多。生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展,线性规划、动态规划、贪心策略等-啄列运筹学模型越来越多被应用到计算机算法学中。当一个问题具有最优子结构性质和贪心选择性质吋，町用动态规划法来解决。但是贪心算法通常会给出一个更简单、肓观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码

3、问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效叫=12.1贪心算法概述贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看來是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所冇问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。贪心算法可以简单描述为：对一纽数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当

4、前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。贪婪算法是一种对某些求授优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的人量时间，它采用口顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的了问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是戢优的。贪焚算法是一种改进了的分级处理方法。其核心是根据题意选取-种量度标准。然后将这

5、多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前己构成在这种量度意义卜-的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，卅其屮的人多数量度标准作贪焚处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产牛问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一•件容易的事，但对某问题能选择出最优量度标准麻，用贪婪算法求解则特别有效。

6、最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择示产生的相应的了问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。2.2贪心算法的基本要素贪心算法通过一系列的选择得到问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。但是对于一个问题，怎么知道是否可以用贪心算法解决此问题，以及能否得到问题的最优解呢？这个问题难以给予肯定的回答。但是，我们从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性和最优子结构性质。贪心选择性是

7、指所求问题的整体最优解町以通过一系列局部最优的选择得到。因此，对于一个具体问题，它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终可以得到鉴体最优的结果，即通过贪心选择示，原问题被简化为规模更小的类似了问题。

8、佃最优子结构性质，主要是指原问题的最优解包含子问题的最优解。2.3贪心算法的特性通过对比能够用贪心算法解决的诸多问题，我们不难总结出贪心算法能够解决的问题的—•系列特性：（1）存在一个最优的方法来解决的问题。为了构造问题的解决方案，