贪心算法论文.doc

山东省农业管理干部学院毕业论文题 目： 贪心算法应用研究 姓 名 ： 盛国选 毕业学院 ： 山东省农业管理干部学院 专业班级 ： 08级计算机系软件1班 学 号 ： 2008052001208 指导教师 ： 张艳君 日 期 ： 年 月 日 XIV目 录1. 贪心算法的基本知识概述21.1 贪心算法定义21.2 贪心算法的基本思路及实现过程21.3贪心算法的核心21.4贪心算法的基本要素21.5 贪心算法的理论基础41.6 贪心算法存在的问题52.贪心算法经典应用举例52.1删数问题52.2 汽车加油问题72.3会场安排问题93.总结13参考文献13摘 要在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。关键词：贪心算法；最小生成树；多处最优服务次序问题；删数问题绪 论 为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术 ,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法 ,你可以使用这些方法来设计算法 ,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且所给出的算法一般比动态规划算法更加简单、直观和高效。1. 贪心算法的基本知识概述1.1 贪心算法定义贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值。1.2 贪心算法的基本思路及实现过程1 贪心的基本思想用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。利用贪心策略解题，需要解决两个问题：（1）该题是否适合于用贪心策略求解；（2）如何选择贪心标准，以得到问题的最优/较优解。2贪心算法的实现过程（1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题；（2）从问题的某一初始解出发：While（能朝给定目标前进一步） 求出可行解的一个解元素；（3）由所有解元素组合成问题的一个可行解。1.3贪心算法的核心贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。1.4贪心算法的基本要素1贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。2最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。3贪心算法的特点贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点：（1）如何贪心怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。（2）贪心的正确性要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。1.5 贪心算法的理论基础正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论拟阵。“拟阵”理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。拟阵M定义为满足下面3个条件的有序对（S，I）：（1）S是非空有限集；（2）I是S的一类具有遗传性质的独立子集族，即若BI，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集必为I的成员；（3）I满足交换性质，即若AI，BI且|A|B|，则存在某一元素xB-A，使得AxI。定理2.1 拟阵M中所有极大独立子集具有相同大小。引理2.1 （拟阵的贪心选择性质）设M=（S，I）是具有权函数M的带权拟阵，且S中元素依权值从大到小排列，又设xS是S中第一个使得x是独立子集元素，则存在S的最优子集A使得xA。引理2.2 设M=(S，I)是拟阵。若S中元素x不是空集的一个可扩元素，则x也不可能是S中任一独立子集A的可扩展元素。引理2.3 （拟阵的最优子结构性质）设x是求带权拟阵M=（S，I）的最优子集的贪心算法Greedy所选择的S中的第一个元素。那么，原问题可简化为求带权拟阵M=（S，I）的最优子集问题，其中S=y|yS且x，yII=B|BS-x且BxIM的权函数是M的权函数在S上的限制（称M为M关于元素x的收缩）。定理2.4（带权拟阵贪心算法的正确性）高M=（S，I）是具有权函数W的带权拟阵，算法Greedy返回M的最优子集。适宜于用贪心策略来求解的许多问题都可以归结为在加权拟阵中找一个具有最大权值的独立子集的问题，即给定一个加权拟阵M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。我们认为，针对绝大多数的信息学问题，只要它具备了“拟阵”的结构，便可用贪心策略求解。拟阵理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。1.6 贪心算法存在的问题（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；（2）贪心算法只能用来求某些最大或最小解的问题；（3）贪心算法只能确定某些问题的可行性范围。2.贪心算法经典应用举例2.1删数问题问题的提出问题提出：给定n位正整数a，去掉其中任意k=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。贪心算法策略分析：n位数a可表示为x1x2xixjxkxn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为T，其最优解A=(y1，y2yk)表示依次删去的k个数，在删去k个数后剩下的数字按原次序排成的新数。即最优值记为TA。 本问题采用贪心算法求解，采用最近下降点优先的贪心策略：即x1x2xixj；如果xkxj，则删去xj，即得到一个新的数且这个数为n一1位中为最小的数Nl，可表示为x1x2xixkxmxn。对N1而言，即删去了1位数后，原问题T变成了需对n-1位数删去k-1个数新问题T。新问题和原问题相同，只是问题规模由n减小为n-1，删去的数字个数由k减少为k-1。基于此种删除策略，对新问题T，选择最近下降点的数进行删除，如此进行下去，直至删去k个数为止。问题的贪心选择性质 先来证明该问题具有贪心选择性质，即对问题T删除最近下降点的数xj后得到的N1是n一1位数是中最小的数。 根据数的进制特点，对a按权展开得： a=x1*10n-1+x2*10n-2+xi*10n-i+xj*10n-j+xk*10n-k+xn 则有：Nl=x1*10n-2+x2*10n-3+xi*10n-i-1+xk*10n-k+xn假设删去的不是xj而是其它位，则有N2=x1*10n-2+x2*10n-3+xi*10n-i-1+xj*10n-k+xn因为有x1x2xixk，则有NlN2。 因此删数问题满足贪心选择性质。 删数问题的C+代码：#include #include using namespace std; int main() string n; int s,i,x,l,m; printf(请输入一个正整数和将要删去的个数!n); while(cinns) i=-1,m=0,x=0; l=n.length(); while(xni+1)/出现递减,删除递减的首数字 n=n.erase(i,1); x+;/ x统计删除数字的个数 i=-1;/从头开始查递减区间 if(i=l-x-2&xs) m=1;/已经无递减区间,m=1脱离循环 printf(最后结果为:n); coutn.substr(0,l-s+x);/只打印剩下的左边l-(s-x)个数字 问题的最优子结构性质在进行了贪心选择后，原问题T就变成了对N1如何删去k-1个数的问题T，是原问题的子问题。若A=(xj，A)是原问题T的最优解，则A是子问题T的最优解，其最优值为TA。 证明：假设A不是子问题T的最优解，其子问题的最优解为B，其最优值记为TB，则有TBTA。而根据TA的定义可知：TA= TA+xj*1On-j，而TBTA，因此有TB+xj*1On-jN，则不可能到达终点；C 加油站间的距离相等，即i=aj=LN，则加油次数k=n/N(n%N=0)或k=n/N+1(n%N！=0)；D 加油站间的距离不相等，即i！=aj，则加油次数k通过贪心算法求解。贪心算法策略该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优解。由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始。为了着手解决遇到的困难，取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。贪心算法正确性证明(1)贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站、，且距离始点比距离始点近，则若在加油不能到达终点那么在加油一定不能到达终点，因为m+Nn+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。(2)最优子结构性质：当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于（b1，b2，bn）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b1=1，则（b2，b3，bn）是从a2到an这段路程上加油次数最少且这段路程上的加油站个数为（a2，a3，an）的最优解，即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)。2.3会场安排问题问题的提出假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。) 数据输入：由文件input.txt给出输入数据。第一行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。结果输出：将编程计算出的最少会场数输出到文件output.txt。会场安排问题的C+代码：#include using namespace std;int Partition(int a, int low, int high )/划分int i,j;int x = alow;i = low;j = high;while(ij) while(ij&x aj) j = j - 1; if(ij) ai = aj; i=i+1; while(i= ai) i = i + 1; if(ij) aj = ai; j=j-1; ai = x; return i;void QuickSort(int a, int low, int high) int Position; if(low -1) n=1;for(;i=bs) /有一个活动结束，新活动可在已空闲的会场进行。 s+;else n+; /要增开一会场 return n;int main( ) int n; cinn; int *st= new intn; int *et=new intn; for(int i=0;istieti; QuickSort(st,0,n-1); QuickSort(et,0,n-1); cout schedule(st,et,0,n-1) endl; delete st; delete et; return 0;输入文件示例输出文件示例input.txt output.txt 5 3 1 23 12 28 25 35 27 80 36 50 编码分析根据会场安排问题的定义，首先将问题简化为：找出两个活动，若ei和ej满足sifj或sjfi，则称这两个活动相容，即问题转化为：要求找出最多相容会场集合A。问题简化为对相容会场A的寻找，下面用贪心方法分析过程，根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。那么问题转化为对度量标准的寻找，判断各个数据是否可以包含在解向量中去，然后根据目标函数来选择最优解。贪心算法（1）将所有活动按结束时间排序，得到活动集合E=e1，e2，en；（2）先将e1选入结果集合A中，即A=e1；（3）依次扫描每一个活动ei：如果ei的开始时间晚于最后一个选入A的活动ej的结束时间，则将ei选入A中，否则放弃ei。最优解证明若E=e1，e2en是按结束时间排序的活动集合，则e1具有最早的结束时间，设存在一个最优安排A不包含e1，并以ei开始，则易见：A-eie1也是最优的活动安排；依此类推，即可推出上述活动都为A中的不相容最优活动。俗话所的好的：纸上得来终觉浅，绝知此事要躬行！那么让我们举个例子来进一步清晰化问题：下面表格有12个活动，并给出各个活动的开始时间与结束时间，那么请用上述贪心解法分析并求解最优会场数