2022年贪婪算法在程序设计中的应用分享 .pdf

《2022年贪婪算法在程序设计中的应用分享 .pdf》由会员分享，可在线阅读，更多相关《2022年贪婪算法在程序设计中的应用分享 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、贪婪算法在程序设计中的应用高兵兵1，尹志敏2摘 要：本文是一篇介绍贪婪算法的文章，贪婪算法的思想是很容易理解的，因此本文的重点是“应用”上。本文首先对贪婪算法的思想进行了剖析，提出其内涵以及算法设计的框架，随后通过几个例子说明了贪婪算法在程序设计中的应用。在选取例子时，笔者优先选取了在数据结构课程中学到的几个应用贪婪思想的例子，并把这些例子用C语言实现了（在Dev-C+编译器下通过，并给出了测试数据）。在对例子说明的同时，本文给出了贪婪算法的适用范围，并举出了范例（如31）来说明贪婪策略的局限性。最后对贪婪策略的应用进行了总结，提出了用贪婪策略的注意事项。关键词： 贪婪法；程序设计；应用；局部

2、最优一 贪婪法的思想贪婪法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。在解得范围可以确定的情况下，蛮力枚举或递归搜索算法的效率是非常低的，可能在有限的时间内是找不到问题的解得。这时， 可以考虑使用贪心的策略，选取那些最可能到达解得情况来考虑。“贪婪”可以理解为以逐步的局部最优，达到最终的全局最优。在这里，一定要注意的是：算法设计的关键是贪婪策略的选择问题。选择的贪婪策略要具有无后向性，即某阶段的状态一旦确定以后，只与当前状态有关，不受这个状态以后的决策影响。因此， 适用于贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析

3、其是否满足无后向性。二 贪婪策略算法设计框架1. 贪婪的基本思路从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策，尽可能的求得最好的解。当达到某算法中的某一步不需要在继续前进时，算法停止。2. 该策略下的算法框架从问题的某一初始解出发；While （能朝给定目标前进一步） 利用可行的决策，求出可行解的一个解元素 由解元素组合成问题的一个可行解。三 算法的应用实例及其适用性贪婪算法是一个适用性有限的策略。因此该部分分为三个部分分别举例并指出其适用性。1. 可绝对贪婪问题：例 11：求最小生成树的prim 算法和 kruskal算法：由于求最小生成树的算法的思想在数据结构的

4、课程中已给出详细解释，笔者不再赘述， 只是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 通过具体的代码来分析其核心的思想是贪心算法。此例子中的图论图形如下所示：Prim: #include #include #define MAX 100 #define MAXCOST 0 x7fffffff int graphMAXMAX; int Prim(int graphMAX, int n) int lowcostMAX; int

5、 mstMAX; int i, j, min, minid, sum = 0; for (i = 2; i = n; i+) /* 最短距离初始化为其他节点到1 号节点的距离 */ lowcosti = graph1i; /* 标记所有节点的起点皆为默认的1 号节点 */ msti = 1; /* 标记 1 号节点加入生成树 */ mst1 = 0; for (i = 2; i = n; i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - -

6、 - - - - min = MAXCOST; minid = 0; /* 找满足条件的最小权值边的节点minid ，进行贪婪选择 */ for (j = 2; j = n; j+) if (lowcostj min & lowcostj != 0) min = lowcostj; minid = j; printf(%c - %c : %dn, mstminid + A - 1, minid + A - 1, min); sum += min; lowcostminid = 0; for (j = 2; j = n; j+) if (graphminidj lowcostj) lowcost

7、j = graphminidj; mstj = minid; return sum; int main() int i, j, k, m, n; int x, y, cost; char chx, chy; scanf(%d%d, &m, &n); getchar(); for (i = 1; i = m; i+) for (j = 1; j = m; j+) graphij = MAXCOST; for (k = 0; k n; k+) scanf(%c %c %d, &chx, &chy, &cost); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

8、 - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - getchar(); i = chx - A + 1; j = chy - A + 1; graphij = cost; graphji = cost; cost = Prim(graph, m); printf(Total:%dn, cost); system(pause); return 0; Kruskal: #include #include #define MAX 100 typedef struct int x, y; int w; edge; ed

9、ge eMAX; int rankMAX; int fatherMAX; int sum; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - /* 比较函数，按权值( 相同则按x 坐标 ) 非降序排序 */ int cmp(const void *a, const void *b) if (*(edge *)a).w = (*(edge *)b).w) return (*(edge *)a).x - (*(edge *)b).x

10、; return (*(edge *)a).w - (*(edge *)b).w; void Make_Set(int x) fatherx = x; rankx = 0; int Find_Set(int x) if (x != fatherx) fatherx = Find_Set(fatherx); return fatherx; void Union(int x, int y, int w) if (x = y) return; if (rankx ranky) fathery = x; else if (rankx = ranky) ranky+; fatherx = y; sum

11、+= w; int main() int i, n; int x, y; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - char chx, chy; scanf(%d, &n); getchar(); for (i = 0; i n; i+) scanf(%c %c %d, &chx, &chy, &ei.w); getchar(); ei.x = chx - A; ei.y = chy - A; Make_Set(i);

12、/* 将边排序，排序的目的是优先选择最短的边，判断一下，如果不构成回路就加入这条边此过程中用了贪心算法 */ qsort(e, n, sizeof(edge), cmp); sum = 0; for (i = 0; i n; i+) x = Find_Set(ei.x); y = Find_Set(ei.y); if (x != y) printf(%c - %c : %dn, ei.x + A, ei.y + A, ei.w); Union(x, y, ei.w); printf(Total:%dn, sum); system(pause); return 0; 名师资料总结 - - -精品

13、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 例 12: 建立 Huffman 树并求出其编码，具体思想见数据结构，在建树的过程中用到了贪婪策略。代码：#include #include #define max 21 typedef struct char data; int weight; int parent; int left; int right; huffnode; typedef struct char dmax; int start; h

14、uffcode; int main() huffnode ht2*max; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - huffcode hcdmax,d; int i,k,f,l,r,n,c,m1,m2,j; printf(元素个数： n); scanf(%d,&n); for(i=1;int结点值： ,i); scanf(%c,&hti.data); printf(t权 重： ); scanf(%d,&hti.weig

15、ht); for(i=1;i=2*n-1;i+) hti.parent=hti.left=hti.right=0; for(i=n+1;i=2*n-1;i+)/建立huffman树 ，选取具有最小权值的俩个结点，分别用l和 r 表示。在此过程中用到贪婪策略 m1=m2=32767; l=r=0; for(k=1;k=i-1;k+) if(htk.parent=0) if(htk.weightm1) m2=m1; r=l; l=k; m1=htk.weight; else if(htk.weightm2) m2=htk.weight; r=k; hti.left=l; hti.right=r;

16、htl.parent=i; htr.parent=i; hti.weight=htl.weight+htr.weight; for(i=1;i=n;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - d.start=n+1; c=i; f=hti.parent; while(f!=0) if(htf.left=c) d.d-d.start=0; else d.d-d.start=1; c=f; f=htf.parent;

17、hcdi=d; for(i=1;i=n;i+) printf(%c:,hti.data); for(j=hcdi.start;j=n;j+) printf(%c,hcdi.dj); printf(n); system(pause); 测试结果如下：2. 可近似贪婪问题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 币种统计问题：某单位给每个职工发工资，为了为了保证不要临时兑换零钱，且取钱的张数最少，取工资前要统计出所有职工的工

18、资所需的各种币值（100,50,20,10，5,2,1共 7 种）算法设计： 为了能达到取款的张数最少，且保证不要临时兑换零钱，应该对没一人的工资用“贪婪”的思想，先尽量多的取大面额的币种，有大面额币种逐渐统计。例 21: 代码：#include #include int main() int i,j,n,GZ,A; int B8=0,100,50,20,10,5,2,1; printf(输入员工数 n); scanf(%d,&n); for(i=1;i=n;i+) printf(输入工资 n); int S8=0; scanf(%d,&GZ); for(j=1;j=7;j+) / 优先选取面

19、值较大的币值（贪婪选择）A=GZ/Bj; Sj+=A; GZ-=A*Bj; for(j=1;j=7;j+) if(Sj!=0) printf(%d-%d ,Bj,Sj); printf(n); system(pause); 测试结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 3. 不可贪婪的问题：数塔问题：给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向左下或是向右下走，一直

20、走到底层。请找出一条路径，使路径上的和最大。例 31：输入样例（数塔）：9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 如果用贪婪的策略，无论是自上而下，还是自下而上都选择一个较大的数进行移动，则路径和分别是：9+15+8+9+10=51（自上而下）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 19+2+10+12+9=52（自下而上）都是不能得到最优解的，真正的最大和是: 9+12+10+18+

21、10=59. 很显然，用贪婪的策略已经不能解决这样的问题了，因此在解决实际问题时要注意贪婪策略的条件。对于这样的问题，可以用动态规划来解决，在这里不做讨论。四贪婪算法总结首先，贪婪算法的原理是通过局部最优来达到全局最优，采用的是逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的（在一定的标准下），决策一旦做出，就不可在更改， 因此一定要注意判断问题是否适合采用贪婪算法策略，找到的解是否一定是问题的最优解。例如在例3 1 中，如果用贪婪的策略来解决，肯定不能找到它的最优解。因此，一定一定要注意的是，在用贪婪策略时，首先判断这个问题是不是适合用贪婪策略来解决，这个是非常重要的！这和现实世界一

22、样，看似可以得到便宜的事，最后却大相径庭。很多问题表面上看用贪婪算法可以找到最优解，其实却将最优解漏掉了。所以贪婪策略一定要精心确定，在使用之前，最好对策略的可行性进行数学证明。所以，贪婪算法要谨慎使用！参考文献：1 吕国英等.算法设计与分析 M. 北京：清华大学出版社2约翰森堡 . 谢菲尔 ( 美). 大学算法教程 M. 北京：清华大学出版社 , 2007 .6. 3 廖荣贵等.数据结构与算法 M. 北京：清华大学出版社 , 2006 年 12 月4http:/ 1 沈继红等 . 数学建模 M. 哈尔滨 : 哈尔滨工程大学出版社,1996.5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -