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

天津师范大学计算机与信息工程学院算法设计与分析结课论文题目贪心算法的分析与实际应用专业计算机科学与技术班级1402班学号1430090056姓名王悦宁任课教师刘洋完成日期2015-1-18算法设计与分析结课论文收稿日期：2015-01-20作者简介：王悦宁1430090056计算机科学与技术1402班指导教师：刘洋-1-贪心算法的分析与实际应用王悦宁摘要：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。本文主要介绍了贪心算法的核心、特点及算法本身存在的问题。关键词：贪心算法；最优解；背包问题；马踏棋盘Thegreedyalgorithmanalysisandpracticalapplication王悦宁TianjinnormaluniversityComputerandInformationEngineeringCollegeTianjin300387Abstract：Greedyalgorithmrefersto,inthesolutionoftheproblem,alwaysmakeinthecurrentviewisthebestchoice.Thatistosay,nottobeconsideredasawhole,hemadeonlyinasenseofthelocaloptimalsolution.Thegreedyalgorithmisnotabletoobtaintheglobaloptimalsolutionforallproblems,butforawiderangeofproblems,hecanproducetheglobaloptimalsolutionortheapproximatesolutionoftheglobaloptimalsolution.Thispapermainlyintroducesthecoreofthegreedyalgorithm,thecharacteristicsandtheexistingproblemsofthealgorithmitself..Keywords：greedyalgorithm;optimalsolution;knapsackproblem;0引言研究背景：为了满足人们对大数据量信息处理的渴望，为了解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的算求解算法更像是一门艺术而不是像技术，但仍存在一些行之有效的、能够用于解决许多问题的算法设计方法。当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常给出一个简单，直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的字问题。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题、哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且说给出的算法一般比动态规划算法更加简单、直观和高效。1贪心算法1.1贪心算法概述贪心算法(Greedyalgorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心法不要回溯。贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种算法设计与分析结课论文-2-量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪心算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪心算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪心选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。1.2贪心算法基本思想用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法的思想本质就是分治，或者说：分治是贪心的基础。每一次都形成局部最优解，换一种方法说，就是每次都处理处一个最好的方案。1.3贪心算法的核心贪心算法的核心问题是选择能生产最优解的最优度量标准，即具体的贪心策略。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法。其实，从“贪心策略”一词我们便可看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题的自身的特性决定论该问题可以运用贪心策略得到最优解或较优解。1.4贪心算法特性贪心算法可解决的问题通常大部分都有如下的特性:⑴有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合:比如不同面值的硬币。⑵随着算法的进行，将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。⑶有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。⑷还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。⑸选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。⑹最后，目标函数给出解的值。为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。1.5贪心算法的理论基础-拟阵贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法旺旺越是难以证明。“拟阵”理论是一种能够确定贪心策略何时能产生最优解的理论。拟阵M定义为满足下面3个条件的有序对（S,I）:（1）S是非空有限集；（2）I是S的一类具有遗传性质的独立子集族，即若B∈I，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集∅比为I的子集；（3）I满足交换性质，即若A∈I，B∈I，且|A||B|,则存在某一元素x∈B-A,使得A∪{x}∈I；定理2.1拟阵M中所有极大独立子集具有相同大小。引理2.1（拟阵的贪心选择性质）设M=（S,I）是具有权函数M的带权拟阵，且S中元素依权值从算法设计与分析结课论文-3-大到小排列，又设x∈S是S中的第一个使得{x}是独立子元素，则存在S的最优子集A使得x∈A。引理2.2设M=（S,I）是拟阵。若S中元素x不是空集∅的一个可扩元素，则x也不可能是S中任一独立子集A的可扩展元素。引理2.3（拟阵的最优子结构性质）设x是求带权拟阵M=（S,I）的最优子集的贪心算法Greedy所选择的S中的第一个元素。那么，原问题可简化为求带权拟阵M’=（S’,I’）的最优子集问题。定理2.4（带权拟阵贪心算法的正确性）高M=（S,I）是具有权函数W的带权拟阵，算法Greedy返回M的最优子集。适宜贪心策略来求解的许多问题都可以归结为在加权拟阵中找一个具有最大全权值独立子集的问题，即给定一个加权拟阵M=（S,I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大独立子集。我们认为，针对绝大多数的信息学问题，只要具备了拟阵的结构便可用贪心策略求解。拟阵理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。1.6贪心算法的优缺点贪心算法是一种重要的算法设计策略而且其效率高。贪心算法并不从整体最优考虑他所做出的选择只是在某种意义上的局部最优选择，即在当前看来最好的选择。希望通过每次所作的贪心选择导致最终结果是问题的一个最优解。贪心算法具有良好的爬坡能力，一般情况下该算法都可以较快的求出满足计算精度要求的近似最优解，当算法不能在限定的时间内给，找满足问题要求的近似最优解时，给出一个可行解及其计算误差，作为决策参考。但随着问题规模和复杂的不断提升，单一的算法在其收敛性和求解速度等方面已经表现出的局限性，即使贪心算法的效率很高也只适用于少量实例。2利用贪心算法解决问题2.1背包问题2.1.1问题描述[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。由于每次装东西进背包，我们只考虑能否装进，以及是否当前状态下的最优选择，也就是说，我们需要用背包的容量去设计一个数组，存储每一单位个容量的最大价值是多少，以此类推，获得背包容量下的最大价值是多少。2.1.2贪心算法策略目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi=M(M=150），每次选取单位重量价值最大的物品，成为解本题的策略。值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：⑴贪心策略：选取价值最大者。反例：W=30物品：ABC重量：281212价值：302020根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。⑶贪心策略：选取单位重量价值最大的物品。反例：W=30物品：ABC重量：282010价值：282010根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。【注意：如果物品可以分割为任意大小，那么策略3可得最优解】对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样算法设计与分析结课论文-4-的，则优先选择重量小的。这样，上面的反例就解决了。但是，如果题目是如下所示，这个策略就也不行了。W=40物品：ABC重量：252015价值：2520152.1.3贪心解决背包问题的算法实现代码如下：#includeiostream.hstructgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品该放的数量intflag;//物品编号};//物品信息结构体voidIn