第八章_贪心算法

第8章 贪心算法

8.1简介

8.1.1 例子

例子： 有4种硬币，面值分别为2角5分、一角、五分和一分。现在要求以

最少的硬币个数找给顾客6角三分。

通常是：先拿两个2角5分的＋1个一角＋3个一分

这种找法所拿出的硬币个数最少。这种算法其实就是贪心算法。顾名思义：

该算法总是作出在当前看来最好的选择，并且不从整体上考虑最优问题，所作出的选择只是在某种意义上的局部最优解。

上面的解法得到的恰好也是最优解。因此，贪心方法的效率往往是很高的。 假如，面值有一角一分、五分和一分，要找给顾客一角五分。如果还是使用上述贪心算法，得到的解是：一个一角一分＋4个一分。而最优解是3个5分。

又例如：

3

2 4 15 1 7 6 4 13 1

12 4 3 5 5

求节点1到节点6的最短路径。用贪心法得19，而实际为17。

显然贪心算法不能对所有问题都能得到最优解，但是对很多问题（包括很多著名的问题）都能产生整体最优解。例如，我们今天要讲的图的单元最短路径问题、最小生成树问题。在有些情况下，算法不能得到整体最优解，但是结果确是最优解的很好近似。

8.1.2 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的

选择来达到，即贪心选择来达到。这是贪心算法可行的第一个基本要素．也是贪心算法与动态规划算法的主要区别：

动态规划算法：每步所做出的选样往往依赖于相关子问题的解，因而只有在解出相关子问题后．才能做出选择。

贪心算法：仅在当前状态下做出最好选样，即局部最优选则。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做出的贪心选则可以依赖于以往做过的选则，但决不依赖于将来所做的选样，也不依赖于子问题的解。

动态规划：是自底向上的方法解各子问题；

贪心算法：是自顶向下的方法。每做出一次贪心选择就将所求问题简化为规模更小的子问题.

使用贪心法的难点在于：证明所设计的算法确实能够正确解决所求解的问题。即对于一个具体的问题，必须证明每一步所做出的贪心选择最终导致问题的整体最优解。

首先，考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做出贪心选择后．原问题简化为规模更小的类似子问题。然后，用数学归纳法证明、通过每一步做贪心选择．最终可得到问题的整体最优解。

其中，证明贪心选择后的问题简化为规模最小的类似子问题的关键在于利用该问题的最优子结构性质。

最优子结构性质： 当一个问题的最优解包含其子问题的最优解时，

称此问题具有最优子结构性质。

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。但是都具有最优子结构的问题该选则贪心法还是动态规划算法求解?是否能用动态规划法的也能用贪心算法解？

背包问题：

给定n种物品{u1,u2,,un}和一个背包，物品i的体积为si，价值为vi。已经知道背包的承重量为C。

2

假设xi是物体i被装入背包的部分，0xi1；要求装满背包且

背包内物体价值最大。

sxi1niiC

maxvixi

i1n选择方法：目标函数的值增加最快，而包载容量的消耗较慢的物体装入包中。故优先选择价值体积比最大的物体装入背包。

背包与0-1背包的区别：

结论0-1背包问题能用动态规划法解，但不能用贪心法解。

8.3单源最短路径问题(狄斯奎诺Dijkstra’s算法)

一、问题描述

G(V,E)是一个有向图，每条边上有一个非负整数表示长度值，其中有一

个顶点s称为源节点。所谓的单源最短路径问题就是：求解该源节点到所有其它节点的最短路径值。不失去一般性，我们假设V{1,2,3,...,n}并且s＝1。那么该问题可以使用Dijkstra’s算法来求解，该算法是一种贪心算法，并且能求得最优解。

二、算法思想

开始时，我们将所有的顶点划分为两个集合X{1},Y{2,3,4,..,n}。所有已经计算好的顶点存放在X中，Y中表示还没有计算好的。Y中的每个顶点y有一个对应的量[y]，该值是从源顶点到y（并且只经由X中的顶点）的最短路径值。

（1） 下面就是选择一个[y]最小顶点yY，并将其移动到X中。

Y中每个和y相邻的顶点w的[w]都要更（2） 一旦y被从Y移动到X中，

新：表示经由y到w的一条更短的路径被发现了。

对于任意一个顶点 vV，假如我们使用[v]表示源顶点到顶点v的最短路径，最后，我们可以证明上述的贪心法结束后有[v][v]。

三、算法DIJKSTRA

输入：含权有向图G=(V,E), V={1,2,„n} 输出：G中顶点1到其他顶点的距离

4

1. X{1};YV{1}；[1]0 2. For y←2 to n

[1,y] If y相邻于1 then [y]lengthElse [v]；

End if

6. end for

7. for j←1 to n-1

8. 令yY，找到最小[y]

9. X←X∪{y} /*将y从Y移动到X中 10 Y←Y-{y}

For 每条边{y,w}

If w∈Y and [y]+length[y,w]< [w] then

[w][y]lenth[y,w] /*更新 Y中和y相邻顶点的值

14. endfor

15.end for

四、举例说明：

1

32 24115 1099 16413112 1243 3558 （手工解该题目）

121312 23943 3554 51334615564

6

3444134513151765

算法的详细实现：

（1） 有向图用邻接表来表示 如图 （2） 假设每条边是非负的

（3） X和Y集合用两个向量来表示X[1..n] ,Y[1..n]。初始时

X[1]=1,Y[1]=0.并且对于2<=i<=n, X[i]=0,Y[i]=1. 因此，执行

就是X[y]=1, YY{y}的操作就是，Y[y]=0。 XX{y}的操作，

五、证明

下面来证明，使用该DIJKSTRA方法得到的是最优解，也就是[y][y]。其中，[v]表示源顶点到顶点v的最短路径；[y]是从源顶点到y（并且只经由X中的顶点）的最短路径值。

证明: 归纳法

（1） 显然[1][1]0

（2） 假设，当前将y移动到X中，并且在y之前移动到X中的任何一个顶

点c，都有[c][c]。由于[y]是有限的，也就是说必定存在一条从1到y路径，长度为[y]（我们需要来证明[y][y]）。 那么这条路径总可以写作：

。。→[ ]→[ ]→[ ]→y ：1→[ ]→[ ]→。

在上述序列中，我们总是可以找到一个顶点，不妨称之为x（xX），使得x之后的顶点均属于Y，并且x是在y前最迟离开Y的顶点。所以有以下两种情形：

1→[ ]→[ ]→。。。→[ ]→[x ]→y (A) 或是

1→[ ]→[ ]→。。。→[x ]→[ ]„→y (B) √对于情形(A)，

[]y[]xhngtexyl[,]xhxyngtel [](,) 算法要求 归纳假设

6

[y] (A)是最短路径

√对于情形(B)，

我们将x之后的顶点不妨称之为w，即： 1→[ ]→[ ]→。。。→[x ]→[ w]„→y (B)

于是有：

[y][w] 由于y在w之前离开Y

[x]length(x,w) 算法要求 [x]length(x,w) 归纳假设 [w] 因为是最短路径 [y]因为是最短路径

我们已经说了，[y]是最短路径了，因此[y][y]。

六、算法分析

O(n2) 或 O(mn)

8.2.1 稠图的线性时间算法

把算法的复杂度从O(n)降到O(m logn).

2

基本思想是用最小堆数据结构来保持集合Y中的顶点，使Y组中离V-Y最近的顶点y可以在O(logn)时间内被选出. 算法8.2 SHORTESTPATH

输入：含权有向图G=(V,E), V={1,2,„n}

输出：G中顶点1到其他顶点的距离.假设已有一个空堆H 1. YV{1}；[1]0;key(1)[1]

2. For y←2 to n

[1,y] If y相邻于1 then [y]lengthkey(y)[y]

INSERT(H,y) Else [v]；

key(y)[y]

End if

6. end for

7. for j←1 to n-1

8. Y←DELETEMIN(H) 10 Y←Y-{y}

For 对每个邻接于y的顶点w∈Y

If [y]+length[y,w]< [w] then

[w][y]lenth[y,w]

/*更新 Y中和y相邻顶点的值

key(w)[w]

endif

If wH then INSERT(H,w) ELSE SIFTUP(H,H-1(w))

endif endfor 15.end for

其中，H-1(w)返回w再H中的位置，可以用一个数组实现。

8.3 最小生成树

设G =(V,E)是无向连通带权图，(V,T)是是G的一个子图，并且T是一颗树，那么称(V,T)是G的生成树。如果T的权之和是所有生成树中最小的，那么则称之为最小生成树。

8

我们假定G是连通的，如果G是非连通的，那么，可以对G的每个子图应用求解最小生成树的算法。

网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。

8.3.1最小生成树性质

用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：

设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。

8.33 Kruskal算法（克鲁斯卡尔）

一、基本思想

Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。

二、KRUSKAL算法

输入： 具有n个顶点的带权连通无向图G(V,E) 输出：G的最小生成树T

1. 以非降序的方式对E中各条边的权进行排序 2. for each vV 3. MAKESET({v}); 4. end for 5. T{}

6. while Tn1

7. let (x,y)为E中的下一条边 8. if FND(x)FND(y) then 9. Add(x,y) to T 10. UNION(x,y)

11. end if 12.end while

关于集合的一些基本运算可用于实现Kruskal算法。

按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实

10

现这个优先队列。

对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集UnionFind所支持的基本运算。

三、Kruskal算法的正确性

证明：我们只要证明，使用Kruskal算法过程中，每次循环所得到的T(从空集增至最小生成树)总是图G的最小生成树的子集即可。使用归纳法＋反证法。

(1)G总是具有一个最小生成树，不妨记为T*。 (2)当前要加入的边为e(x,y)。

(3)包含x的那颗子树的所有顶点用X表示。

(4)假设在e(x,y)加入之前得到的T均满足TT*，其中

xX,yVX。

令T'T{e}，下面我们要证明T'也是图G的最小生成树的子集。 依据归纳假设，有TT*。 (A)如果eT*：显然有T'T*

(B)如果eT*：那么T*{e}必将构成一个环，也就是T*不再是树。我们知道T*中必定包含这样一条边e'(w,z)，且wX,zVX，且cost(e')cost(e)。否则，e'将被选择加入。 下面我们来证明e'就是e。

定义T**T*，{e}'{e}那么T**也是图的一个生成树，并且cost(T**)证明完毕。

四、时间复杂度：

当图的边数为e时，Kruskal算法所需的计算时间是O(eloge)。

8.4 Prim算法（普里姆）

一、基本思想

设G=(V,E)是连通带权图，V={1,2,„,n},。构造G的最小生成树. Prim算法的基本思想：

首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。

在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。

例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示

12

二、算法

算法8.4 PRIM

输入：含权有向图G=(V,E), V={1,2,„n}

输出：由G生成的最小耗费生成树T组成的边的集合 1.T←{};X←{1}；Y←V-{1} 2. For y←2 to n

If y相邻于1 then N[y]←1

C[y] ←c[1,y]

Else C[y]；

End if

8. end for

9. for j←1 to n-1 {寻找n-1条边} 10. 令yY，找到最小C[y]

11. T←T∪{(y,N[y]} {将边y，N[y]加入T} 12. X←X∪{y} /*将y从Y移动到X中 13 Y←Y∪{y}

For 每个相邻于y的顶点w∈Y If c[y,w]C[w] ←c[y,w]

18. end if 19. endfor 20.end for

在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权c[i][j]最小的边(i,j)。

三、算法分析

用这个办法实现的Prim算法所需的计算时间为O(n2)

当图的边数为e时，Kruskal算法所需的计算时间是O(eloge)。当e(n2)时，

Kruskal算法比Prim算法差，但当eo(n2)时，Kruskal算法却比Prim算法好得多。

8.6 哈夫曼编码

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 哈夫曼编码思想：给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

前缀码

对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。 例：a:10, b:101存在二义性

编码的前缀性质可以使译码方法非常简单。

表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。

平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。构造哈夫曼编码

哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。

在书上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。

算法8.6 HUFFMAN

输入：n个字符的集合C 和他们的频度 输出：Cde huffman树（V，T）

1．根据频度将所有字符插入最小堆H 2．V←C;T={}

14

3．For j←1 to n-1 4． c←DELETEMIN(H) 5． C←DELETEMIN(H)

6． f(v) ←f(c)+f(c) {v是一个新结点} 7． INSERT(H,v)

8． V=V∪{v} {添加v到V}

9． T=T∪{（v，c）,(v, c)}{使c和c成为T中v的孩子}

10． End for

时间复杂度：

算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的取最小和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)

哈夫曼算法的正确性

要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。

(1)贪心选择性质 (2)最优子结构性质

''''