第八章_贪心算法

第8章 贪心算法

8.1简介

8.1.1 例子

例子： 有4种硬币，面值分别为2角5分、一角、五分和一分。现在要求以最少的硬币个数找给顾客6角三分。

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

这种找法所拿出的硬币个数最少。这种算法其实就是贪心算法。顾名思义：该算法总是作出在当前看来最好的选择，并且不从整体上考虑最优问题，所作出的选择只是在某种意义上的局部最优解。

上面的解法得到的恰好也是最优解。因此，贪心方法的效率往往是很高的。

假如，面值有一角一分、五分和一分，要找给顾客一角五分。如果还是使用上述贪心算法，得到的解是：一个一角一分＋4个一分。而最优解是3个5分。

又例如：

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

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

8.1.2 贪心选择性质

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

3 5 6 1

12 7 3

4

5 13

4 15

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

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

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

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

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

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

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

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

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

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

背包问题：

给定n种物品12{,,,}nuuu和一个背包，物品i的体积为is，价值为iv。已经知道背包的承重量为C。

假设ix是物体i被装入背包的部分，10ix；要求装满背包且背包内物体价值最大。

Cxsinii1

maxiniixv1

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

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

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

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

一、问题描述

),(EVG是一个有向图，每条边上有一个非负整数表示长度值，其中有一个顶点s称为源节点。所谓的单源最短路径问题就是：求解该源节点到所有其它节点的最短路径值。不失去一般性，我们假设},...,3,2,1{nV并且s＝1。那么该问题可以使用Dijkstra’s算法来求解，该算法是一种贪心算法，并且能求得最优解。

二、算法思想

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

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

（2） 一旦y被从Y移动到X中，Y中每个和y相邻的顶点w的][w都要更新：表示经由y到w的一条更短的路径被发现了。

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

三、算法DIJKSTRA

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

输出：G中顶点1到其他顶点的距离

1. }1{X;}1{VY；0]1[

2. For y←2 to n

If y相邻于1 then ],1[][ylengthy

Else ][v；

End if

6. end for

7. for j←1 to n-1

8. 令Yy，找到最小][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

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

14. endfor

15.end for

四、举例说明：

（手工解该题目）

12435611293451341512435611293451341501841317 123456213955346431243513615

6

算法的详细实现：

（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. 因此，执行

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

五、证明

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

证明: 归纳法

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

（2） 假设，当前将y移动到X中，并且在y之前移动到X中的任何一个顶点c，都有][][cc。由于][y是有限的，也就是说必定存在一条从1到y路径，长度为][y（我们需要来证明][][yy）。

那么这条路径总可以写作：

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

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

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

或是

1→[ ]→[ ]→。。。→[x ]→[ ]„→y (B)

√对于情形(A)，

[][][,]yxlengthxy 算法要求

[](,)xlengthxy 归纳假设

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

√对于情形(B)，

我们将x之后的顶点不妨称之为w，即：

1→[ ]→[ ]→。。。→[x ]→[ w]„→y (B)

于是有：

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

),(][wxlengthx 算法要求

),(][wxlengthx 归纳假设

][w 因为是最短路径

][y因为是最短路径

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

六、算法分析

O(n2) 或 O(mn)

8.2.1 稠图的线性时间算法

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

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

算法8.2 SHORTESTPATH

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

输出：G中顶点1到其他顶点的距离.假设已有一个空堆H

1. }1{VY；0]1[;]1[)1(key

8 2. For y←2 to n

If y相邻于1 then ],1[][ylengthy

][)(yykey

INSERT(H,y)

Else ][v；

][)(yykey

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

],[][][wylenthyw

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

][)(wwkey

endif

If Hw 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的权之和是所有生成树中最小的，那么则称之为最小生成树。