浅析贪心算法
摘要：本文首先概述了贪心算法，然后探讨并研究了贪心算法的基本思想及实现过程，通过实例分析了贪心算法的具体应用，指出了贪心算法的特点及存在问题。
关键词：贪心算法；贪心策略；最优解；穿墙问题
为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。当一个问题具有最优子结构性质和贪心选择性质时，贪心算法通常会给出一个简单、直观和高效的解法。
一．贪心算法的概述
1.1 贪心算法的定义
贪心算法（greedy algorithm，又称贪婪算法）是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。
贪心策略是最接近人类认知思维的一种解题策略，贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。 贪心算法就是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。这时就得到了问题的一个解，但不能保证求得的最后解是最优的做一种目前最贪婪的行动。贪心法和递推法有相似之外，也是从问题的某一个初始解出发，向给定的目标递推，但不同的是每一步不是依据某一个固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题归结为更小的相似的问题。
1.2 贪心算法的基本思想
用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。
利用贪心策略解题，需要解决两个问题：
（1）该题是否适合于用贪心策略求解；
（2）如何选择贪心标准，以得到问题的最优/较优解。 1.3贪心算法的核心
贪心算法通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。该技术的核心是，所做的每一步都必须满足：
（1）可行的：即它必须满足问题的约束。
（2）局部最优：它是当前步骤中所有可行选择中最佳的局部选择。 （3）不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。 这些要求对这种技术的名称做出了解释：在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的最优解。
1.4实现该算法的过程
(1)应用同一规则,f将原问题变为一个相似的、但规模更小的子问题； (2)从问题的某一初始解出发； While (能朝给定总目标前进一步)do 求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解。
二．贪心算法的应用
对于一个具体的最优化问题，是否适用于贪心算法求解，按照贪心算法得到的全局解是否一定最优，“仁者见仁智者见智”，没有一个通用的判定方法。但适用于贪心算法求解的最优化问题一般具有两个特点：
（1）最优子结构——问题的最优解包含了子问题的最优解（必要性）。 （2）贪心选择性质——可通过做局部最优（贪心）选择来达到全局最优解（可行性）。
下面，我们用一个例子来讨论贪心算法的具体应用。 2.1问题描述
在现代的魔术表演中，穿越墙壁是非常受欢迎的，魔术师在一个预先设计好的舞台上表演穿越几面墙壁。在每次穿越墙壁的表演中，穿越魔术师有一个有限的穿越能量，通过至多k面墙。墙壁被放在一个网格状的区域中。所有墙的厚度是一个单元，但长度不同。本题设定没有一个方格会在2面墙或更多面墙中。观众选择一列方格。穿越者从图的上方沿着一列方格向下走，穿过每一面在他路上遇到的墙，到达图的下方。如果他试图走的那一列要穿过的墙超过k面，他将无
法完成这个节目。例如墙的结构如图2.1所示，一个穿墙者在k=3的情况下，从上到下可以选择除了第6列以外的任何一列。
图2.1
2.2问题分析
我们由左到右扫描每一列，要使得拆墙数最少，必须保证左方舞台可穿越的情况下被拆墙最少，即问题具备了最优子结构的特点。关键是，怎样通过做局部最优选择来达到全局最优解呢？
若当前列的墙数Q ≤ K，则不处理；若当前列的墙数Q > K，则需拆Q-K面墙。至于拆除哪些墙，我们采取了这样一个贪心策略：在当前列所有的有墙格中，选择右方最长的Q-K面墙拆除。
由于当前列左方的舞台都可穿越，所有影响穿越的墙从当前列开始，因此途经当前列的所有墙中，往右的墙格越多，影响穿越的列范围最大，越应该被拆除。这个简单逻辑引出了上述度量标准。毋庸置疑，由左而右做这样的贪心选择，被拆墙的面数肯定是最少的。
2.3程序如下所示： #include
int t,n,k,x,y,x1,y1,max_x,max_y,sum_s = 0; //测试用例的个数为t
//墙数为n，穿墙者可通过的墙的最大面数为k，墙的端点坐标为（x，y）（x1,y1） //所有墙的最大列坐标为max_x，最大行坐标为max_y，最少拆除墙的面数为sum_s
int map[105][105]; //(i,j)所在的墙序号为map[i][j] int main()
{ printf(\请输入测试用例的个数：\
scanf(\//输入测试用例的个数 while(t--) //依次处理每个测试用例 {
memset(map,0,sizeof(map)); //初始时舞台没有墙
max_x = 0; //墙的最大行列坐标初始化 max_y = 0;
sum_s = 0; //最少拆除墙的面数初始化 printf(\请输入测试用例的数据：\
scanf(\//输入墙数和穿墙者可通过的墙的最大面数 for(int p = 1;p<=n;p++) {
printf(\请输入墙的坐标：\
scanf(\%d %d %d\//输入第p面墙的两个端点坐标 if(x>max_x) //调整墙的最大行列坐标 max_x = x; if(x1>max_x) max_x = x1; if(y>max_y) max_y = y;
if(x < x1) //标记第p面墙 {
for(int j=x;j<=x1;j++) map[j][y] = p; } else {
for(int j=x1;j<=x;j++) map[j][y] = p; } }
for(int i = 0;i<=max_x;i++) //从左而右扫描每一列 {
int tem = 0; //统计第i列墙中的格子数 for(int j=0;j<=max_y;j++) if(map[i][j]>0) tem++;
int offset = tem - k;
if(offset>0) //若第i列中墙的格子数大于k,则需要拆offset面墙， //将offset计入最少拆除墙的面数 {
sum_s+=offset; while(offset--) {
int max_s = 0,max_bh;
for(int k=0;k<=max_y;k++) //搜索i列每个有墙的格子 {
if(map[i][k]>0) //若（i,k）为有墙格，则统计
{
//k行i列右方属于同堵墙的格子数tem_s
}
int tem_s = 0;
for(int z=i+1;z<=max_x;z++) if(map[z][k]==map[i][k]) tem_s++; else
break;
if(max_s //则记下 { max_s = tem_s; max_bh = k; } } } for(int a=i;a<=i+max_s;a++) map[a][max_bh] = 0; //拆除含格子数最多的墙 //（第max_bh行上第i列开始的max_s个格子） } } } printf(\应拆除的墙的个数为：\//输出最少拆除强的面数 printf(\} return 0; 2.4测试结果： 1.只有一个测试用例的运行结果如图2.2所示：