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

贪心算法的分析与实际应用用时可以删除天津师范大学计算机与信息工程学院算法设计与分析结课论文专业计算机科学与技术班级1402班 学号56姓名王悦宁 而且说给而且说给出的算法一般比动态规划算法更加简法概述ithm优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。本文主要介绍了贪心ThegreedyalgorithmanalysisandpracticalapplicationAbstract：Greedyalgorithmrefersto,inthesolutionoftheproblem,alwaysmakeinthecurrentviewisthebestchoice.Thatistosay,nottobeconsideredasawhole,hemadeonlyinasenseofthelocaloptimalsolution.Thegreedyalgorithmisnotabletoobtaintheglobaloptimalsolutionforallproblems,butforawiderangeofproblems,hecanproducetheglobaloptimalsolutionortheapproximatesolutionoftheglobaloptimalsolution.Thispapermainlyintroducesthecoreofthegreedyalgorithm,thecharacteristicsandtheexistingproblemsofthealgorithmitself..Keywords：greedyalgorithm;optimalsolution;knapsackproblem;0引言，为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一纷运用到计算机算法学中，产个好的算求解算法更像是一门艺术而不是像技术，但仍存在一些行之有效的、能够用于解决许质和贪心选择性质时，贪心算法通常给出一个简单，直观和高效的解法。贪心算法通过一系列的选择来得到一且每次贪心选择都能将问题化简为一个更小的与许多问题不能总是产生整体最优解，但对诸如最构和贪心选择性质的问题却可以获得整体最优方法。其核心后将这多个输所要求的顺序，按这种顺序当前已构成在解加在一起不能产生部分解中。这下最优解的分级处理方，往往可能有好几种量度标准似乎都是可取不是问题的择能产生问题最并不是一件最优量度标准效。最优解可以通贪心选择来达到，根这个选择后产生子问题，最终可得到问本思想始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进。贪心算法的思想本质就是分治，就是每次都处理处一个最好的方案。的核心贪心算法的核心问题是选择能生产最优解的贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的便可看出，贪心策略总是做出在当前看来是最优考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题的自身的特性决定论该问题法特性贪心算法可解决的问题通常大部分都有如下有一个候选的对象的集合:比包含已经被考虑过并被选出的候选对象，另。函数一样，婪算法一步对象的集合函数，算法从剩余候选对象中选出最有希望构成解的对象。到集合里。每一次都。如果贪婪贪心算法的理论基础-拟阵贪心策略是最接近人类认知思维的一种解题“拟阵”理论是一种能够确定贪心策略何时(S,I):(1)S是非空有限集；(2)I是S的一类具有遗传性质的独立子集I满足交换性质，即若A∈I，B∈I，且引理(拟阵的贪心选择性质)设M=(S,I)是引理(拟阵的最优子结构性质)设x是求带MSI的最优子集的贪心算法Greedy化为求带权拟阵M’=(S’,I’)的最优子集问题。定理(带权拟阵贪心算法的正确性)高M=(S,I)是具有权函数W的带权拟阵，算法Greedy结的问题，即给定一个加权拟阵M=(S,I)，若能找题，只求解。拟阵一复杂优缺点贪心算法是一种重要的算法设计策略而且其效率高。贪心算法并不从整体最优考虑他所做出的选择只是在某种意义上的局部最优选择，即在选择导致最终结果是问题的一个最优解。贪心算法具有良好的爬坡能力，一般情况下该算法都可当算法不能在限定的时间内给，找满足问题要求的近似最优解时，给出一个可行解及其计算误差，作为决策参考。但随着问题规模和复杂的不断提升，单一的算法在其收敛性和求解速度等方面已经表现出的局限性，即使贪心算法的效率很只适用于少量实例。贪心算法解决问题，也就是，以此类多少。以是一。题的(无法被证明)的，解释如下：最大者。020最小。它的反例与第重量价值最大的物282010重量价值一样，程分割为任意大小，那么策最大的物品这个策规