奋斗贪心算法.doc

《奋斗贪心算法.doc》由会员分享，可在线阅读，更多相关《奋斗贪心算法.doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、奋斗贪心算法1、 贪心算法策略 贪心算法（又称贪婪算法）是指，在对问题求解时,总是做出在当前看来是最好的选择.也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解.贪心法的基本思想是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的方式求得更好的解。即当达到算法中的某一步不能再继续前进时，算法停止,得到问题的一个解，该算法有如下特点：(1） 不能保证求得的最终解是最佳的；（2) 不能用来求最大或最小等有极值要求的问题的解；（3) 只能求得满足某些约束条件的可

2、行解;（4） 在当前状态下一旦选定一个分量，就不再从试其他的可行性；(5） 它并不从整体最优上作出考虑，它的选择只是在贪心准则下的局部最优选择。因此，使用贪心算法得到的最优解不一定是整体最优的，却往往是最优解的很好的近似解。在这里需要注意贪心问题的关键是贪心准则的选取。对于同一个问题,贪心准则可能不是唯一的，往往其中很多看起来都是可行的。但是根据其中大部分贪心准则所得到的所谓的最优解并不一定是当前问题的最优解。在一般情况下,要选出最优贪心准则并不是一件容易的事。当然，如果能够确定当前问题的最优贪心准则,那么用贪心算法求解当前问题就会非常有效.可以用贪心算法求解的问题具有一些共同特征.当遇到一个

3、具体问题的时候，需要判断这种问题应该用什么方法来求解.那么,怎么判断是否应该用贪心算法来求解这个问题呢；如果是，那么用贪心算法来求解这个问题能否得到最优解呢.只要证明要求解的问题有如下两个性质：贪心选择性质和最优结构性质即可解决问题。 （1） 贪心选择性质 在求解一个问题的过程中，如果在每一阶段的选择都是当前状态下的最优选择，即局部最优选择,并且最终能够求得问题的整体最优解,那么说明这个问题可以通过贪心选择求解，这时就说此问题具有贪心选择性质.根据前面对贪心选择性质的定义，要证明一个问题具有贪心选择性质只要证明通过我们每一步所作的贪心选择使得在最后得到问题的一个整体最优解就可以了。通常采用如下

4、的证明过程:首先假设问题的一个整体最优解，那么第一步要证明可以把这个最优解修改成贪心选择开始，此时原问题就简化成为与原问题相似的一个子问题。接下来，使用数学归纳法证明通过每一步的贪心选择可以得到问题的一个整体最优解。（2） 最优子结构性质当一个问题的最优解包含了这个问题的子问题的最优解时，就说这个问题具有最优子问题结构。这个性质决定了一个问题是否可以使用贪心算法来求解。贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码对于其他问题，贪心法一般不能得到我们所要求的答案.一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法.由于贪心法的高效性以及其所求得的答案比

5、较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。2、登山机器人问题（1）问题描述:登山机器人可以携带有限的能量。在登山过程中,登山机器人需要消耗一定能量，连续攀登的路程越长，其攀登的速度就越慢。在对m种不同类型的机器人进行性能测试时,测定出每个机器人连续攀登1，2，n米所用的时间。现在要对这m个机器人进行综合性能测试，举行机器人接力连续攀登演习。攀登的总高度为s米。规定每个机器人攀登1次，每次至少攀登1米，最多攀登n米，而且每个机器人攀登的高度必须是整数，即只能在整米处接力.安排每个机器人攀登适当的高度,使完成接力攀登的时间最短。(2）设计要求：给定m个登山机

6、器人接力攀登的总高度s，以及每个机器人连续攀登1，2,，n米所用的时间，计算最优攀登方案。（3）数据输入：第1行是正整数m，n和s分别表示机器人的个数、每个机器人最多可以攀登的高度和接力攀登的总高度.接下来的m行中，每行有n个正整数，分别表示机器人连续攀登1，2，,n米所用的时间。（4）数据输出:输出登山机器人接力到达终点的最短攀登时间 3、算法分析对于登山机器人问题，假设机器人每步走一米,我们进行一米一米的贪吃办法来算出机器人走过的米数,即步数.由于每个机器人都要走，所以我们先让每个机器人走一步，将问题缩小，再在剩下的数据里面选出走下一步用时最少的机器人，让它走一步，进一步缩小问题规模，依次

7、循环直到走完所有的路程,即可求知各个机器人走的步子，即就是走过的路程，对应给出路程的各个机器人的时间叠加起来就得了最短的时间了。算法中的两个二维数组，data数组用来存放时间数据，a数组用来存放机器人再走一步所用时间间隔和机器人已经走多少米；算法中的函数init（）是用于将数组a赋初值，第一列用于存放机器人再走一步所用时间间隔，第二列用于存放机器人已经走多少米;函数done（）是用于选择每走一米时间间隔最小的机器人，且不断更新数组a中的值，直到不满足所给条件；在主函数main(）中，先定义二维数组data和a，输入机器人的个数n、每个机器人最多可以攀登的高度k、攀登的总高度m后，用malloc

8、函数分配存储空间，然后再输入时间数据;该算法的时间复杂度和空间复杂度:函数init(）的时间复杂度为， 函数done（)的时间复杂度为,主函数main（）的时间复杂度为,故该算法的时间复杂度为+=；空间复杂度为。4、总结在实现该算法的过程中，我们发现如果没有给数组data和数组a分配存储空间，在程序运行时就会发生错误，当用malloc函数分配存储空间后运行时发生的错误便能解决；在选择时间间隔最小的机器人时，要注意两个二维数组下标的变化，稍有不慎便会使结果发生错误；我们要弄清问题的约束条件，在编写代码时如果约束条件不清楚,我们就很难实现该算法。通过对登山机器人问题的解决，我们了解到了算法设计与分

9、析课程的重要性，使我们对算法产生了兴趣;希望在以后的学习中，我们能够接触到更多有关算法的问题,并能够熟悉掌握各个算法的要点。5、小组成员冷双:贪心算法策略和编写文档张丽娟：搜索资料和分析算法周姗姗：负责代码编写陈晶晶：分析算法和总结算法曹思涵:贪心算法策略和总结算法王忠龙：搜索资料和计算时间复杂度6、附件（1）问题源代码如下：includestdio.hincludestdlib.hincludemalloc.hdefine MAXINT 1000int n,k，m，mint=0；/n：机器人个数，k:每个机器人最多走多少米，m：总路程/每个机器人都先走第一步void init(int *da

10、ta，int *a）int i；for(i=0；in;i+）ai0=datai2-datai1;ai1=1；void done(int *data,int a)int i,j,flag；int min；m=n;/每个机器人已经走了一米while（m-)/选择时间间隔最小的机器人min=a00;flag=0;for（i=1;in；i+）if（ai0min&ai1k)min=ai0；flag=i;aflag1+;/当前最小时间间隔机器人步数加一if（aflag1k）aflag0=dataflagaflag1+1dataflagaflag1;elseaflag0=MAXINT;for(i=0;in；

11、i+) mint+=dataiai1；printf（”最短攀登时间： %dn”，mint）；void main()/data读取时间数据，a数组第一列用于存取机器人再走一步所用时间间隔，第二列用于存取机器人已经走多少米int *data,*a;int i,j；printf(”输入机器人的个数n、每个机器人最多可以攀登的高度k、攀登的总高度m : n）；scanf（d %d d”，&n,k，&m)；/输入第一行参数/分配存储空间data=(int *）malloc（n*sizeof(int )）；a=(int *）malloc（n*sizeof（int *)）;for（i=0；in；i+）datai=（int ）malloc(k+1）sizeof(int)）；ai=(int ）malloc(2*sizeof(int)）;/输入时间数据printf（输入时间数据:n）；for(i=0;in；i+）datai0=0；for（j=1;j=k；j+）scanf（”%d”，&dataij）；/调用函数init（data,a)；done(data,a)； (2）输入数据后问题的运行界面如下所示： 图1 运行界面8