贪心算法论文

《贪心算法论文》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贪心算法论文姓名：高翔班级：706指导老师：范江文一概念；贪心，贪心顾名思义即不顾一切地追求目标。在FreePascal中贪心算法可以解释为：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续。前进时，算法停止。这时就得到了问题的一个解，但不能保证求得的最后解是最优的。在改进算法中，贪心算法演化为爬山法。注意：贪心算法并不能保证求得的解是最优的，一定要三思而后行！！二特点及使用范围贪心算法的优点在于时间复杂度极低。而贪心算法与其他最优化算法的区别在于：它具有不可后撤性，可以有后效性，一般情况下不满足最优化原理。贪心算法的特

2、点就决定了它的适用范围，它一般不适用于解决可行性问题，仅适用于较容易得到可行解的最优性问题。这里较容易得到可行解的概念是：当前的策略选择后，不会或极少使后面出现无解的情况。另外，对于近年来出现的交互性题目，贪心算法是一个较好的选择。这是因为，在题目中，一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提供较优的初始界值。三经典例题 例一背包问题有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。   要求尽可能让装入背包中的物品总价值最大，但

3、不能超过总容量。   物品ABCDEFG   重量35306050401025   价值10403050354030   分析：   目标函数：∑pi最大   约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150)   （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？   （2）每次挑选所占重量最小的物品装入是否能得到最优解？   （3）每次选取单位重量价值最大的物品，成为解本题的策略。   值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。   贪心算法还是很常见的算法之一，这是由于它简单

4、易行，构造贪心策略不是很困难。   可惜的是，它需要证明后才能真正运用到题目的算法中。   一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。   对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：   （1）贪心策略：选取价值最大者。反例：   W=30   物品：ABC   重量：281212   价值：302020   根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。   （2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。   （3）贪心策略：选取单位重量价值最大的物品。

5、反例：   W=30   物品：ABC   重量：282010   价值：282010根据策略，三种物品单位重量价值一样，程序无法依据现有策略做出判断，如果选择A，则答案错误。注意：此题用贪心算法解的确不错，但不是最优解。解此题思路⒈建立数学模型来描述问题。⒉把求解的问题分成若干个子问题。⒊对每一子问题求解，得到子问题的局部最优解。⒋把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。二贪心算法之汽车加油问题问题描述   一辆汽车加满油后可以行

6、驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。   给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。  问题分析（前提行驶前车里加满油）   对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n   1.始点到终点的距离小于Ｎ，则加油次数k=0；   2.始点到终点的距离大于N，   A 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=

7、n；   B 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点；   C 加油站间的距离相等，即ａ[i]=a[j]=L