201126100101计自1102曹帝胄贪心算法

贪心算法

曹帝胄

摘要：贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择,也就是

说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题也能产生整体最优解或者是整体最优解的近似解。本文首先介绍了贪心算法的核心、特点及算法本身存在的问题，接下来介绍了前人已经研究出来的成果，包括哈夫曼编码、单源最短路径、最小生成树等。然后结合实践，研究了多处最优服务次序问题、删数问题、汽车加油问题、最优合并问题、会场安排问题等。最后用代码实现其中的两个问题，对贪心算法的具体实现方法做了详细说明。

关键字：贪心算法；哈夫曼编码；最小生成树；最优服务次序；汽车加油问题

Abstract：Greedy algorithm is that, in the problem solving, it always made in the

current appears to be the best option. In other words, not the best on the whole to be considered, he made only a local optimal solution in a sense. Greedy algorithm is not a right that all problems can be the overall optimal solution, but it covers a wide range of issues that he could produce an overall optimal solution or approximate solution of the overall optimal solution. This paper describes the core of the greedy algorithm, characteristics and algorithms inherent problems, then presented the results of our predecessors has been studied out, including Huffman coding, single-source shortest path, minimum spanning tree and so on. Then with practice, study the various optimal service order issues, delete a few issues, car fuel, the optimal merger, venue arrangements and so on. At last, the code to achieve two of them on the greedy algorithm to do the concrete implementation method in detail.

Key words：greedy algorithm；Huffman coding；MST；Optimal service order;Automobile refueling

1.1 贪心算法定义

贪心算法可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态

下最好或最优的选择，从而希望得到结果是最好或最优的算法。

贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值。

1.2 贪心算法的基本思路及实现过程

1 贪心的基本思想

用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。

利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解；

（2）如何选择贪心标准，以得到问题的最优/较优解。 2贪心算法的实现过程

（1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题； （2）从问题的某一初始解出发：

While（能朝给定目标前进一步） 求出可行解的一个解元素；

（3）由所有解元素组合成问题的一个可行解。

1.3贪心算法的核心

贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。

贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。

1.4贪心算法的基本要素

1贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 2最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。 3贪心算法的特点

贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节

约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点：

（1）如何贪心

怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。

具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。

（2）贪心的正确性

要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。

1.5 贪心算法的理论基础

正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论—拟阵。

“拟阵”理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。

拟阵M定义为满足下面3个条件的有序对（S，I）： （1）S是非空有限集；

（2）I是S的一类具有遗传性质的独立子集族，即若B∈I，则B是S的独

立子集，且B的任意子集也都是S的独立子集。空集￠必为I的成员；

（3）I满足交换性质，即若A∈I，B∈I且|A|<|B|，则存在某一元素x∈B-A，使得A∪{x}∈I。

定理2.1 拟阵M中所有极大独立子集具有相同大小。

引理2.1 （拟阵的贪心选择性质）设M=（S，I）是具有权函数M的带权拟阵，且S中元素依权值从大到小排列，又设x∈S是S中第一个使得{x}是独立子集元素，则存在S的最优子集A使得x∈A。

引理2.2 设M=(S，I)是拟阵。若S中元素x不是空集￠的一个可扩元素，则x也不可能是S中任一独立子集A的可扩展元素。

引理2.3 （拟阵的最优子结构性质）设x是求带权拟阵M=（S，I）的最优子集的贪心算法Greedy所选择的S中的第一个元素。那么，原问题可简化为求带权拟阵M'=（S'，I'）的最优子集问题，其中

S'={y|y∈S且{x，y}∈I} I'={B|B?S-{x}且B∪{x}∈I}

M'的权函数是M的权函数在S'上的限制（称M'为M关于元素x的收缩）。 定理2.4（带权拟阵贪心算法的正确性）高M=（S，I）是具有权函数W的带权拟阵，算法Greedy返回M的最优子集。

适宜于用贪心策略来求解的许多问题都可以归结为在加权拟阵中找一个具有最大权值的独立子集的问题，即给定一个加权拟阵M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。我们认为，针对绝大多数的信息学问题，只要它具备了“拟阵”的结构，便可用贪心策略求解。拟阵理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。

1.6 贪心算法存在的问题

（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；

（2）贪心算法只能用来求某些最大或最小解的问题； （3）贪心算法只能确定某些问题的可行性范围。

贪心算法举例： 0-1背包问题

0-1背包问题：给定n种物品和一个背包。物品i的重量和价值分别是wi和vi，背包的容量为C。要求正确的选取装入背包的物品，使得装入背包的物品价值之和最大。例如：C=30物品：A B C 重量：28 12 12 价值：30 20 20

根据贪心选择策略，首先选择A，然后再比较B、C，无法再装入。可以看出，最终的结果是将A装入背包中。但是，如不按贪心算法求解，实际是装入B和C最好。

因此，对于0-1背包问题，贪心选择不能达到结果最优，这是因为在这种情况下，无法保证最终将背包装满，部分闲置的空间使得每公斤背包的价值下降了。因此，在考虑此类的背包问题时，应该比较选择该物品呵不选择该物品所导致的最终方案，然后再做出最好的选择，此时可用动态规划算法求解。

显然，对于以上例子，如果不要求选择物品的全部装入背包，允许我们只选择部分装入背包，此问题及转化为普通背包问题。此时即可用贪心选择算法求解。一般步骤为：首先选择将每公斤价值最大的物品装入背包，如果背包未满，再选择每公斤价值次大的物品装入，以此类推。

会场安排问题

问题的提出

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)

数据输入：由文件input.txt给出输入数据。第一行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。 结果输出：将编程计算出的最少会场数输出到文件output.txt。

会场安排问题的C++代码： #include using namespace std;

int Partition(int a[], int low, int high )//划分 {

int i,j;

int x = a[low]; i = low; j = high; while(i

while(i

j = j - 1; }

if(i

a[i] = a[j]; i=i+1; }

while(i= a[i]) {

i = i + 1; } if(i

a[j] = a[i]; j=j-1; } }

a[i] = x; return i; }

void QuickSort(int a[], int low, int high) {

int Position;

if(low < high) {

Position = Partition(a,low,high); QuickSort(a, low, Position-1); QuickSort(a, Position+1, high); } }

int schedule(int a[],int b[],int s,int e)

{

int n=0; int i=s+1; if (a[s]>-1) { n=1;

for(;i<=e;i++)

if(a[i]>=b[s]) //有一个活动结束，新活动可在已空闲的会场进行。

s++; else

n++; //要增开一会场 }

return n; }

int main( ) { int n; cin>>n;

int *st= new int[n]; int *et=new int[n]; for(int i=0;i

cin>>st[i]>>et[i]; QuickSort(st,0,n-1); QuickSort(et,0,n-1);

cout<< schedule(st,et,0,n-1) <

输入文件示例输出文件示例

input.txt output.txt 5 3 1 23 12 28 25 35 27 80 36 50 编码分析

根据会场安排问题的定义，首先将问题简化为：找出两个活动，若ei和ej满足si≥fj或sj≥fi，则称这两个活动相容，即问题转化为：要求找出最多相

容会场集合A。

问题简化为对相容会场A的寻找，下面用贪心方法分析过程，根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。那么问题转化为对度量标准的寻找，判断各个数据是否可以包含在解向量中去，然后根据目标函数来选择最优解。 贪心算法

（1）将所有活动按结束时间排序，得到活动集合E={e1，e2，?，en}； （2）先将e1选入结果集合A中，即A={e1}；

（3）依次扫描每一个活动ei：如果ei的开始时间晚于最后一个选入A的活动ej的结束时间，则将ei选入A中，否则放弃ei。 最优解证明

若E={e1，e2?en}是按结束时间排序的活动集合，则e1具有最早的结束时间，设存在一个最优安排A不包含e1，并以ei开始，则易见：A-{ei}∪{e1}也是最优的活动安排；依此类推，即可推出上述活动都为A中的不相容最优活动。

俗话所的好的：纸上得来终觉浅，绝知此事要躬行！那么让我们举个例子来进一步清晰化问题：

下面表格有12个活动，并给出各个活动的开始时间与结束时间，那么请用上述贪心解法分析并求解最优会场数目。如表8-1所示。

表8-1 会场活动安排表

活动i 开始时间s（i） 结束时间E（i）

1 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 2 13

11 12 14

（1）根据贪心策略：现将1～12个活动的结束时间排序（为解说方便上表格已经排好）排序可用快速排序。

（2）毋庸置疑将E1先分配入会场集合A1，然后按照顺序找出下个活动，使得其开始时间小于E1的结束时间（即满足时间不冲突），如图易知为E4，再将E4分配给A1，以后每一步骤都重复如E4的选择。经过第一轮的筛选可知会

场集合A1中包含：A1={E1，E4，E8，E11}。

（3）此时已经没有活动在相容于会场A1中，那么再继续对A2进行同样的选取，同理：A2={E2，E6} A3={E3，E7} A4={E5，E9} A5={E10}。

（4）那么得出总的会场数目：S=5。

总结与心得

贪心算法是很常见的算法，贪心策略是最接近人的日常思维的一种解题策略，虽然它不能保证求得的最后解一定是最佳的，但是它可以为某些问题确定一个可行性范围，具有有简单、直接、高效的特点。按照贪心算法设计出来的许多算法均

能得到结果的最优，虽然它不能保证对每一个问题最后的解都是最优的。贪心算法所作出的选择依赖于以往所做过的选择，绝不依赖将来的选择，这使得算法在编码和执行过程中都有一定的速度优势。对于一个问题的最优解只能用穷举法得到时，用贪心算法是寻找

问题最优解的较好算法。对一个问题可以同时用几种方法解决，贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时，就需判断贪心性质的正确性了。与回溯法、动态规划法等比较，它的适用区域相对狭窄许多。

参考文献：

[1] 王晓东.计算机算法设计与分析 [M]．北京：电子工业出版社,2007． [2] 严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997． [3] 谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006．

[4] LARRY NYHOFF.ADTS,DATA STRUCTUERS,AND PROBLEM SOVLING WITH C++ [5] 钱能.C++程序设计教程[M]：清华大学出版社，2010

本文来源：https://www.bwwdw.com/article/2n8r.html