简析贪心算法结课论文

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

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

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

3、最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效。[1]2贪心算法2.1贪心算法概述贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。贪心算法可以简单描述为：对一组数据进行排序，找出最小值

4、，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题5简析贪心算法结课论文_(2)导读：局部最好选择，即贪心选择。但是对于一个问题，怎么知道是否可以用贪心算法解决此问题，以及能否得到问题的最

5、优解呢？这个问题难以给予肯定的回答。但是，我们从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性和最优子结构性质。贪心选择性是指所求问题的整体最优解可以通过一系列局部简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部

6、分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一

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