浅析贪心算法

《浅析贪心算法》由会员分享，可在线阅读，更多相关《浅析贪心算法（9页珍藏版）》请在装配图网上搜索。

1、浅析贪心算法摘要：本文首先概述了贪心算法，然后探讨并研究了贪心算法的基本思想及 实现过程，通过实例分析了贪心算法的具体应用，指出了贪心算法的特点及存在 问题。关键词：贪心算法；贪心策略；最优解；穿墙问题为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算 法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷 纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。当一个问题具 有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高 效的解法。一贪心算法的概述1.1贪心算法的定义贪心算法（greedy algori thm，又称贪婪算法）是一种能

2、够得到某种度量 意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是 说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部 最优解算法。贪心策略是最接近人类认知思维的一种解题策略，贪心策略是指从问题的初 始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法。 贪心算法就是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求 得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。这时就得 到了问题的一个解，但不能保证求得的最后解是最优的做一种目前最贪婪的行 动。贪心法和递推法有相似之外，也是从问题的某一个初始解出发，向给定的目

3、标递推，但不同的是每一步不是依据某一个固定的递推式，而是做一个当时看似 最佳的贪心选择，不断地将问题归结为更小的相似的问题。1.2贪心算法的基本思想用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽 可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。 贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最 优解，换一种方法说，就是每次都处理出一个最好的方案。利用贪心策略解题，需要解决两个问题：(1) 该题是否适合于用贪心策略求解；(2) 如何选择贪心标准，以得到问题的最优/较优解。13贪心算法的核心贪心算法通过一系列步骤来构造问题的解，每一步

4、对目前构造的部分解做一 个扩展，直到获得问题的完整解为止。该技术的核心是，所做的每一步都必须满 足：(1) 可行的：即它必须满足问题的约束。(2) 局部最优：它是当前步骤中所有可行选择中最佳的局部选择。(3) 不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。这些要求对这种技术的名称做出了解释：在每一步中，它要求“贪婪”地选 择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的最优 解。1.4实现该算法的过程应用同一规则f将原问题变为一个相似的、但规模更小的子问题；(2)从问题的某一初始解出发；While (能朝给定总目标前进一步)do求出可行解的一个解元素；由所有解元素

5、组合成问题的一个可行解。二贪心算法的应用对于一个具体的最优化问题，是否适用于贪心算法求解，按照贪心算法得到 的全局解是否一定最优，“仁者见仁智者见智”没有一个通用的判定方法。但适 用于贪心算法求解的最优化问题一般具有两个特点：(1) 最优子结构一一问题的最优解包含了子问题的最优解(必要性)。(2) 贪心选择性质一一可通过做局部最优(贪心)选择来达到全局最优解 (可行性)。下面，我们用一个例子来讨论贪心算法的具体应用。2.1问题描述在现代的魔术表演中，穿越墙壁是非常受欢迎的，魔术师在一个预先设计好 的舞台上表演穿越几面墙壁。在每次穿越墙壁的表演中，穿越魔术师有一个有限 的穿越能量，通过至多k面墙

6、。墙壁被放在一个网格状的区域中。所有墙的厚度 是一个单元，但长度不同。本题设定没有一个方格会在2面墙或更多面墙中。观 众选择一列方格。穿越者从图的上方沿着一列方格向下走，穿过每一面在他路上 遇到的墙，到达图的下方。如果他试图走的那一列要穿过的墙超过k面，他将无 法完成这个节目。例如墙的结构如图2.1所示，一个穿墙者在k=3的情况下，从 上到下可以选择除了第6列以外的任何一列。图2.122问题分析我们由左到右扫描每一列，要使得拆墙数最少，必须保证左方舞台可穿越的 情况下被拆墙最少，即问题具备了最优子结构的特点。关键是，怎样通过做局部 最优选择来达到全局最优解呢？若当前列的墙数Q w K则不处理；

7、若当前列的墙数Q K,则需拆Q-K面 墙。至于拆除哪些墙，我们采取了这样一个贪心策略：在当前列所有的有墙格中, 选择右方最长的Q-K面墙拆除。由于当前列左方的舞台都可穿越，所有影响穿越的墙从当前列开始，因此途 经当前列的所有墙中，往右的墙格越多，影响穿越的列范围最大，越应该被拆除。 这个简单逻辑引出了上述度量标准。毋庸置疑，由左而右做这样的贪心选择，被 拆墙的面数肯定是最少的。2.3程序如下所示：#includeusing namespace std;int t,n,k,x,y,xl,yl,max_x,max_y,sum_s = 0;/测试用例的个数为 t/墙数为n,穿墙者可通过的墙的最大面数

8、为k,墙的端点坐标为(x, y) (xl,yl)/所有墙的最大列坐标为max_x，最大行坐标为max_y,最少拆除墙的面数为sum_s int map105105;/(i,j)所在的墙序号为 mapijint main() prin tf(请输入测试用例的个数：)；scanf(%d, &t);while(t-)memse t( map,0,sizeof(map);max_x = 0;max_y = 0;sum_s = 0;prin tf(请输入测试用例的数据: scanf(%d %d, &n, &k);for(int p = 1;pmax_x)/调整墙的最大行列坐标max_x = x;if(x

9、1max_x)max_x = x1; if(ymax_y)max_y 二 y;if(x x1)for(int j二x;j=x1;j+) mapjy = p;elsefor(int j=x1;j二x;j+) mapjy = p;for(int i 二 0;i二max_x;i+)int tem = 0;for(int j=0;j0)tem+;int offset 二 tem k;if(offset0) /若第i列中墙的格子数大于k,则需要拆offset面墙, /将 offset计入最少拆除墙的面数sum_s+=offset; while(offset-) int max_s = O,max_bh;

10、for(int k=0;k0)/若(i,k)为有墙格，则统计/k行i列右方属于同堵墙的格子数tem_sint tem_s = 0;for(int z=i+1;z=max_x;z+) if(mapzk=mapik)tem_s+;elsebreak;if(max_stem_s) /若该堵墙的格子数最多，/则记下max_s = tem_s; max_bh = k;for(int a=i;a=i+max_s;a+) mapamax_bh = 0;/拆除含格子数最多的墙/(第max_bh行上第i列开始的max_s个格子) returnprintf(应拆除的墙的个数为：)；/输出最少拆除强的面数pri n

11、tf (%dn,sum_s);2.4测试结果：1.只有一个测试用例的运行结果如图2.2所示:图2.2输入：输入的第一行输入一个整数t,表示测试用例的个数；输入的第二行输入的 是第一个测试用例的数据，要输入两个整数，分别是n和k,n表示墙的面数，k 表示穿墙者可以通过的墙的最大面数；在上一行后，给出n行，每行包含两个 （x,y）对，表示一面墙的两个端点坐标。如上所示的测试用例与图2.1相对应。输出：每个测试用例一行，给出一个整数，表示最少拆除墙的面数，使得穿墙者能 从上方任意一列开始穿越。2.有3个测试用例的运行结果如图2.3所示：说明：当输入的测试用例的个数大于等于2时，要先输入完第一个测试用

12、例 的数据，输出结果后，再一次输入后面的测试用例的数据。三贪心算法特点及存在的问题3.1贪心算法特点从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程，后 面的每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，不依赖于 未做出的选择。贪心算法的最大特点就是快，通常是线性到二次式，不需要多少 额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出 正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。3.2贪心算法存在的问题(1) 不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是 最优的选择，因此并不从整体上加以考虑。(2) 贪心

13、算法只能用来求某些最大或最小解的问题。从前面的讨论中，找零 钱问题要求得到最小数量采用贪心算法是可行的，但是在另外一个求解权值最小 路径时采用贪心算法得到的结果并不是最佳。(3) 贪心算法只能确定某些问题的可行性范围。四结束语贪心算法是计算机算法策略中常用的一个,往往在需要解决一些最优性问题时，都可以 应用贪心算去。贪心算去是很常见勺算去，贪心策咯是最接近人的日常思维的一种解题策略 虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围。 贪心算去在科学计算和工程中勺应用也越来矿泛例如用贪心算法进行三角剖分的指纹匹 配方法贪心算法在排课系统中的应用、贪心聚类算法如在遥感图像分类和压缩中的应用 等等 在未来出现的一些问题中,只要符合贪心算法的贪心策咯性质，就可以用贪心算去求 解。总之，我们应该不断推广贪心算法的应用，让它能解决更广泛的问题。