资源描述：
《贪婪算法的研究与应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、目录1引言12贪婪算法的概述12.1什么是贪婪算法12.2贪婪算法的特性22.3贪婪算法解决问题的步骤22.4贪婪算法的优缺点23贪婪算法的应用33.1贪婪算法在资源分配问题中的应用33.2贪婪算法在布线问题中的应用43.3贪婪算法在0/1背包问题中的应用63.3.1传统的贪婪算法解决方案73.3.2改进的贪婪算法策略84总结与展望9参考文献11贪婪算法的研究与应用摘要：贪婪算法的典型应用是解决优化问题，这类算法的策略是只顾眼前，而不考虑以后的影响，它的算法简单容易设计实现，因此在许多实际问题中得到广泛的应用，但是它也存在许多的问题。本文首先对贪
2、婪算法的基本概念做了介绍，然后通过实例论述了贪婪算法在实际应用中的优点，并阐述了对算法缺点的改进方案，最后对贪婪算法的发展前景做了展望。关键字：贪婪算法研究应用11ResearchandApplicationofGreedyalgorithm(PanRongComputerDepartmentofHexiUniversity)Abstract:Solvingtheoptimizedproblemsisthetypicalapplicationofthegreedyalgorithm,thisalgorithm’sstrategyisonlycon
3、siderspresent,butdon’tconsiderstheinfluenceoflater,itsalgorithmissimpleanddesignseasily,thereforeobtainsthewidespreadapplicationinmanyactualproblems,butitalsohasmanyproblems.Firstlythisarticleintroducesthebasicconceptsofthegreedyalgorithm,thendiscussesthemeritsofthegreedyalgo
4、rithminpracticalapplicationbyexamples,thisarticlealsoelaboratestheimprovingprogramoftheshortcomingofthealgorithm,finallythisarticlemakestheforecastforthedevelopmentofthegreedyalgorithm.Keywords:GreedyalgorithmResearchApplication111引言为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展
5、,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。目前常用的算法设计技术有分治法、回溯法、贪婪法、动态规划算法、分支限界法等。其中分治法、回溯法主要用于设计非数值问题的算法,
6、而贪婪法、动态规划算法、分支限界法则主要用于设计数值最优化问题的算法。贪婪法是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对许多问题可能产生整体最优解。2贪婪算法的概述2.1什么是贪婪算法贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通
7、过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大
8、多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的
