贪心算法结课论文

贪心算法求解汽车加油问题1引言随着科学的发展，人们生活中面临的大数据量越来越多。生活的快节奏要求人们对这些庞大的数据进行简单快速的处理，在这种实际需求的背景下，计算机算法设计得到了飞速发展，线性规划、动态规划、贪心策略等一系列运筹学模型越来越多被应用到计算机算法学中。当一个问题具有最优子结构性质和贪心选择性质时，可用动态规划法来解决。但是贪心算法通常会给出一个更简单、直观和高效的解法。贪心算法通过一系列的选择来得到一个问题的解。尽管贪心算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解，而且所给出的算法一般比动态规划算法更加简单、直观和高效[1]。2贪心算法2.1贪心算法概述贪心算法又称贪婪算法，是指在求解问题时，总是做出在当前看来是最好的选择，也就是说，贪心算法并不要求从整体上最优考虑，它所作的仅是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。2.2贪心算法的基本要素贪心算法通过一系列的选择得到问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。但是对于一个问题，怎么知道是否可以用贪心算法解决此问题，以及能否得到问题的最优解呢？这个问题难以给予肯定的回答。但是，我们从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性和最优子结构性质。贪心选择性是指所求问题的整体最优解可以通过一系列局部最优的选择得到。因此，对于一个具体问题，它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终可以得到整体最优的结果，即通过贪心选择后，原问题被简化为规模更小的类似子问题。而最优子结构性质，主要是指原问题的最优解包含子问题的最优解。2.3贪心算法的特性通过对比能够用贪心算法解决的诸多问题，我们不难总结出贪心算法能够解决的问题的一系列特性：（1）存在一个最优的方法来解决的问题。为了构造问题的解决方案,有一个候选的对象是一个集合：比如不同面值的硬币。（2）随着算法的进行，将产生两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但是被丢弃的候选对象。（3）算法中将产生一个用来检查一个候选对象是否提供了问题的解答的函数。当然，该函数并不考虑此时的解决方法是否最优。（4）算中法另一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。（5）选择函数指出哪一个剩余的候选对象可能构成问题的解。（6）最后返回解的值。为了解决原问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,使得贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空，接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象，然后加入到一个集合中，如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。2.4贪心算法的基本思路用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。利用贪心策略解题，需要解决两个问题：（1）该题是否适合于用贪心策略求解；（2）如何选择贪心标准，以得到问题的最优/较优解。具体的实现过程如下：（1）建立数学模型来描述问题。（2）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题。（3）对每一子问题求解，得到子问题的局部最优解。（4）把子问题的解局部最优解合成原来解问题的一个解。实现的算法的过程如下：从问题的某一初始解出发；while（能朝给定总目标前进一步）do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。3经典例子分析3.10-1背包问题0-1背包问题：给定n种物品和一个背包。物品i的重量和价值分别是wi和vi，背包的容量为C。要求正确的选取装入背包的物品，使得装入背包的物品价值之和最大。例如：C=30物品：ABC重量：281212价值：302020根据贪心选择策略，首先选择A，然后再比较B、C，无法再装入。可以看出，最终的结果是将A装入背包中。但是，如不按贪心算法求解，实际是装入B和C最好。因此，对于0-1背包问题，贪心选择不能达到结果最优，这是因为在这种情况下，无法保证最终将背包装满，部分闲置的空间使得每公斤背包的价值下降了。因此，在考虑此类的背包问题时，应该比较选择该物品呵不选择该物品所导致的最终方案，然后再做出最好的选择，此时可用动态规划算法求解。显然，对于以上例子，如果不要求选择物品的全部装入背包，允许我们只选择部分装入背包，此问题及转化为普通背包问题。此时即可用贪心选择算法求解。一般步骤为：首先选择将每公斤价值最大的物品装入背包，如果背包未满，再选择每公斤价值次大的物品装入，以此类推。3.2加油站问题（习题4-16）（一）问题描述一辆汽车加满油后可行驶N公里。旅途中有若干个加油点。设计一个有效算法，指出应在哪些加油站加油，使得旅途中加油次数最少，并证明算法能产生一个最优解。（二）问题分析设汽车在起点已经为加满油的状态，记加油的次数为k，起点与终点距离为S，加油站的个数为n，加油站i与加油站i+1之间的距离存放在一个数组a[i]中（i=0、1、2、3…..n），其中a[0]表示汽车位于起始点,a[n+1]表示汽车到达终点。对于原问题，主要有以下几种情况：A当S<N或S=N时，无需加油，即k=0；B当S>N时：（1）各加油站之间的距离相等且等于N，即a[i]=N，需要加油次数至少为k=n；（2）各加油站之间的距离相等且大于N，即a[i]>N，则不可能到达终点。（3）各加油站之间的距离相等且小于N，即a[i]<N，则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；（4）各加油站之间的距离不相等，即a[i]!=a[j]，则加油次数k可以通过以下算法得到。具体算法描述如下：intadd(intb[],intm,intn){//求一个从m到n的数列的和intsb;for(inti=m;i<n;i++)sb+=b[i];returnsb;}intTanxin(inta[n],intN)//a[n]表示加油站的个数，N为加满油能行驶的最远距离{intb[n];//若在a[i]加油站加油，则b[i]为1，否则为0intm=0;if(a[i]>N)returnERROR;//如果某相邻的两个加油站间的距离大于N，则不能到达终点if(add(a[i],0,n)<N){//如果这段距离小于N，则不需要加油b[i]=0;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]==N){//如果每相邻的两个加油站间的距离都是N，则每个加油站都需要加油b[i]=1;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]<N){//如果每相邻的两个加油站间的距离相等且都小于Nif(add(a[i],m,k)<N&&add(a[i],m,k+1)>N){b[k]=1;m+=k;}returnadd(b[i],0,n);}if(a[i]!=a[j]){//如果每相邻的两个加油站间的距离不相等且都小于Nif(add(a[i],m,k)<N&&add(a[i],m,k+1)>N){b[k]=1;m+=k;}returnadd(b[i],0,n);}viodmain(){inta[];scanf("%d",a);scanf("/n");scanf("/d",&N);Tanxin(a[],0,n);}由于贪心算法适用的问题必须满足连个属性：贪心性质和最优子结构，因此，对于该汽车加油的问题是否适合用贪心算法，要先判定其是否具有这两个性质。●贪心选择性质对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，因为m+N<n+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。●最优子结构由于（b[1]，b[2]，……b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1，则（b[2]，b[3]，……b[n]）是从a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2]，a[3]，……a[n]）的最优解，即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。总结与心得贪心算法是常见的算法之一，是一种重要的算法涉及策略，有简单、直接、高效的特点。按照贪心算法设计出来的许多算法均能得到结果的最优，虽然它不能保证对每一个问题最后的解都是最优的。贪心算法所作出的选择依赖于以往所做过的选择，绝不依赖将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找问题最优解的较好算法。对一个问题可以同时用几种方法