贪心算法的分析及实际应用

《贪心算法的分析及实际应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、WORD格式可编辑天津师范大学计算机与信息工程学院算法设计与分析结课论文题目贪心算法的分析与实际应用专业计算机科学与技术班级1402班学号1430090056姓名王悦宁任课教师刘洋完成日期2015-1-18专业知识分享WORD格式可编辑贪心算法的分析与实际应用王悦宁摘要：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整

2、体最优解的近似解。本文主要介绍了贪心算法的核心、特点及算法本身存在的问题。关键词：贪心算法；最优解；背包问题；马踏棋盘Thegreedyalgorithmanalysisandpracticalapplication王悦宁TianjinnormaluniversityComputerandInformationEngineeringCollegeTianjin300387Abstract：Greedyalgorithmrefersto,inthesolutionoftheproblem,alway

3、smakeinthecurrentviewisthebestchoice.Thatistosay,nottobeconsideredasawhole,hemadeonlyinasenseofthelocaloptimalsolution.Thegreedyalgorithmisnotabletoobtaintheglobaloptimalsolutionforallproblems,butforawiderangeofproblems,hecanproducetheglobaloptimalsol

4、utionortheapproximatesolutionoftheglobaloptimalsolution.Thispapermainlyintroducesthecoreofthegreedyalgorithm,thecharacteristicsandtheexistingproblemsofthealgorithmitself..Keywords：greedyalgorithm;optimalsolution;knapsackproblem;专业知识分享WORD格式可编辑0引言研究背景：

5、为了满足人们对大数据量信息处理的渴望，为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的算求解算法更像是一门艺术而不是像技术，但仍存在一些行之有效的、能够用于解决许多问题的算法设计方法。当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常给出一个简单，直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是在当前状态下具有某种意义的最好选择，

6、即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的字问题。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题、哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且说给出的算法一般比动态规划算法更加简单、直观和高效。1贪心算法1.1贪心算法概述贪心算法(Greedyalgorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择

7、，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心法不要回溯。贪心专业知识分享WORD格式可编辑算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如

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