第三章 贪心方法 （Greedy Technique）

Presentation on theme: "第三章 贪心方法 （Greedy Technique）"— Presentation transcript:

1 第三章 贪心方法 （Greedy Technique）

2 引例1 找零钱问题(change-making problem)
我们先考虑一个我们许多人都会遇到的问题：找零钱。一个显然的目标是：使零钱数量最少。自动售货机也必须要解决此问题，若要找零钱2.3元，如果机器吐出230个一分或23个一角，就不合适了。 例如：要求找零72元3角 我们很可能回答：1张50元， 2张10元， 2张1元， 1张2角， 1张1角。 我们在这里默认采用了贪心策略思想:每次总是选择小于余额的最大面额钞票

3 货币（100元，50元，10元，1元，2角，1角） 可行解： 总张数 张数（0 ，0 ，7 ，2 ，1 ，1） 11
货币（100元，50元，10元，1元，2角，1角） 可行解： 总张数 张数（ ，0 ， ，2 ，1 ，1） 张数（ ， ，7 ，2 ，0 ，3） 张数（ ， ，2 ，0 ，0 ，23） 张数（ ， ，2 ，2 ，1 ，1） 课堂讨论：总结得到最优解的思路是什么

4 得到最优解的思路： 100元，超过总货币值，故为0张； 50元，只能一张，两张以上也会超过，剩余22元3 角； 10元，两张，剩余2元3角 1元，2张，剩余3角 2角，1张 1角，1张

5 引例2 铺砖问题 有若干种不同规格的砖，要铺满一块平台，希望用较少的砖达到目的。
引例2 铺砖问题 有若干种不同规格的砖，要铺满一块平台，希望用较少的砖达到目的。 例如，有三种规格的砖：2*2，0.8*0.8，0.1*0.1，要铺满2.5*2.5的平面。 采用贪心策略：首先是最大规格的砖2*2一块，再考虑次大的0.8*0.8，无法放入，再考虑最小的0.1*0.1,要25*5+20*5=225块 课堂讨论：是否最优解？请寻找最优解 请手工绘图表示

6 最优解：9块中规格的0.8*0.8，再加上49块0.1*0.1规格的。共需要58块。 说明：贪心法不一定能得到最优解
请手工绘图表示

7 （100元多少张，50元多少张，10元多少张，5元多少张，2元多少张，1元多少张。。。），如此形成一个向量
3.1 一般方法 请问：形成多少维向量？ 1. 问题的一般特征 问题有n个输入（如找零钱问题就是不同的货币组合，铺砖问题中就是不同的规格的砖的组合），问题的解是由这n个输入的某个子集组成，这个子集必须满足某些事先给定的条件。 约束条件：子集必须满足的条件； 可 行 解：满足约束条件的子集；可行解一般不唯一； 目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出； 最 优 解：能够使目标函数取极值（极大或极小）的可行解。 分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。 ——最优化问题求解 贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。

8 2. 贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条件的子集组成。 1）一般方法
贪心算法是把一个整体最优问题分解为一系列的最优选择子问题。 根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排序，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。 这一处理过程一直持续到n个输入都被考虑完毕，则记入最优解集合中的输入子集构成这种量度意义下的问题的最优解 贪心方法: 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法

9 注： 直接将目标函数作为量度标准也不一定能够得到问题的最优解 使用贪心策略求解的关键是选取能够得到问题最优解的量度标准。

10 货轮转载问题：有一艘货轮要装载n种货物，n种货物有不同的重量及价值，货轮有允许载重量，要求在允许载重量范围内能够使总的货物价值达到最大。
3.2 背包问题(Knapsack) 1.问题的描述 货轮转载问题：有一艘货轮要装载n种货物，n种货物有不同的重量及价值，货轮有允许载重量，要求在允许载重量范围内能够使总的货物价值达到最大。 一般的背包问题：已知n种物品具有重量分别为(w1,w2,…,wn)和效益值分别为(p1,p2,…,pn) ，及一个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效益，这里，0≤ xi ≤1, pi >0。（这里的每个物品是可分割的）

11 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？
分析： ① 装入背包的总重量不能超过M ② 如果所有物品的总重量不超过M，则把所有的物品都装入背包中将获得最大可能的效益值 ③ 如果物品的总重量超过了M，则无法把所有的物品都装入背包中，即将有物品不能（部分/全部）装入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包，故最终背包中可刚好装入重量为M的若干物品（整体或一部分）。这种情况下，如果背包没有被装满，则显然不能获得最大的效益值。 目标：使装入背包的物品的总效益达到最大。

12 问题的形式描述 目标函数： 约束条件： 可 行 解：满足上述约束条件的任一(x1,x2,…,xn) 都是问题
的一个可行解——可行解可能为多个。 (x1,x2,…,xn)称为问题的一个解向量 最 优 解：能够使目标函数取最大值的可行解是问题的最优解 ——最优解也可能为多个。

13 例 背包问题的实例 设，物品数目：n=3，背包容纳重量：M=20， 物品价值(p1,p2,p3) = (25,24,15)，物品重量 (w1,w2,w3) = (18,15,10)。 可能的可行解如下： 可行解 重量 效益 (x1,x2,x3) ① (1/2,1/3,1/4) //没有装满背包// ② (1, 2/15, 0 ) ③ (0, 2/3, 1) ④ (0, 1, 1/2)

14 2. 贪心策略求解 度量标准的选择：三种不同的度量标准选择 1）以目标函数作为度量 即，每装入一件物品，就使背包获得最大可能的效益增量。
该度量标准下的处理规则是： ● 按效益值的非增次序将物品一件件地放入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。

15 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 28.2 (次优解,非问题的最优解)
实例分析（例3.1) ∵ p1＞p2＞ p3 ∴ 首先将物品1放入背包，此时x1＝1，背包获得p1＝25的效益增量，同时背包容量减少w1＝18个单位，剩余空间ΔM=2。 其次考虑物品2和3。就ΔM=2而言有，只能选择物品2或3的一部分装入背包。 物品2： 若 x2＝2/15， 则 p2 x2＝16/5＝3.1 物品3： 若 x3＝2/10， 则 p3 x3＝3 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 x2＝2/15 最后，背包装满， ΔM=0，物品3不装包，即x3＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ (次优解,非问题的最优解)

16 2）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而可能不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量装入“较多”的物品。 即，新的标准是：以容量作为度量 该度量标准下的处理规则： ● 按物品重量的非降次序将物品装入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背包；

17 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31 (次优解,非问题的最优解)
实例分析（例3.1) ∵ w3＜w2 ＜w1 ∴ 首先将物品3放入背包，此时x3＝1，背包容量减少w3＝10个单位，还剩余空间ΔM=10。同时，背包获得p3＝15的效益增量。 其次考虑物品2。就ΔM=10而言有，也只能选择物品2的一部分装入背包。下一步将放入物品2的10/15装包，即 x2＝10/15＝2/3 最后，背包装满ΔM=0，物品1将不能装入背包，故 x1＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31 (次优解,非问题的最优解) 存在的问题：效益值没有得到“最大程度”的增加

18 3）最优的度量标准 影响背包效益值的因素： 背包的容量M 放入背包中的物品的重量及其可能带来的效益值 课堂讨论：如何进一步改进以获得最优解

19 思考题： 可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得当前最大的单位效益。 在这种策略下的量度是：已装入的物品的累计效益值与所用容量之比。 故，新的量度标准是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。 此时，将按照物品的单位效益值：pi/wi 比值的非增次序考虑。

20 最终可以获得的背包效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31.5 (最优解)
实例分析（例3.1) ∵ p1/w1＜p3/w3 ＜p2/w2 ∴ 首先，将物品2放入背包，此时x2＝1，背包容量减少w2＝15个单位，还剩余空间ΔM=5。同时，背包获得p2＝24的效益增量。 其次，在剩下的物品1和3中，应选择物品3,且就ΔM=5而言有， 只能放入物品3的一部分到背包中 。即 x3＝5/10＝1/2 最后，背包装满ΔM=0，物品1将不能装入背包，故x1＝0 。 最终可以获得的背包效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ (最优解)

21 思考题： 设计编写背包问题的贪心算法

22 3. 背包问题的贪心求解算法 算法3.2 背包问题的贪心算法 procedure GREEDY－KNAPSACK(P,W,M,X,n)
//P(1:n)和W(1:n)分别含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n件物品的效益值和重量。M是背包的容量大小，而X(1:n)是解向量// real P(1:n), W(1:n), X(1:n), M, cu; integer I,n X←0 //将解向量初始化为0// cu←M //cu是背包的剩余容量，其初使容量为M// for i←1 to n do if W(i) > cu then exit endif X(i) ←1 cu ←cu-W(i) repeat if i≤n then X(i) ←cu/W(i) endif end GREEDY-KNAPSACK

23 0-1背包问题 上述背包问题中，不允许切割货物，由于不允许切割，背包会有空余，若n较大，最优解反而不容易求出。

24 生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E')是一棵树，则称T是G的一棵生成树(spanning tree)．
3.5 最小生成树 问题的描述 生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E')是一棵树，则称T是G的一棵生成树(spanning tree)． 最小生成树: 带有成本的图的生成树问题 应用实例：道路网建设规划问题，如何使总的道路里程最小。则建设成本也就最小。城市就是图的顶点，城市间道路就是图的一个边，而道路长度就是成本。

25 2. 贪心策略 度量标准：选择能使迄今为止所计入的边的成本和有最小增加的那条边。 ● Prim算法 ● Kruskal算法

26 3. Prim算法 策略：使得迄今所选择的边的集合A构成一棵树；则将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A∪{(u,v)}也是一棵树的最小成本边。 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 边 (1,2) (2,6) (3,6) (6,4) 成本

27 V(TP) = {1,2,3,4,5,6} E(TP) = { (1,2),(2,6),(3,5),(4,6),(3,6) } 边
10 1 2 边 (3,5) 成本 35 35 3 5 25 15 4 20 6 V(TP) = {1,2,3,4,5,6} E(TP) = { (1,2),(2,6),(3,5),(4,6),(3,6) }

28 procedure PRIM(E,COST,n,T,mincost)
//E是G的边集。COST(n,n)是n结点图G的成本邻接矩阵，矩阵元素COST(i,j)是一个正实数，如果不存在边(i,j)，则为＋∞。计算一棵最小生成树并把它作为一个集合存放到数组T(1:n-1,2)中(T(i,1),T(i,2))是最小成本生成树的一条边。最小成本生成树的总成本最后赋给mincost// real COST(n,n), mincost integer NEAR(n), n, i, k, l, T(1:n-1,2) (k,l)←具有最小成本的边 mincost←COST(k,l) (T(l,1),T(l,2)) ←(k,l) for i←1 to n do //将NEAR置初值// if COST(i,l) ＜ COST(i,k) then NEAR(i)←l else NEAR(i) ←k endif repeat

29 NEAR(k)←NEAR(l)←0 for i←2 to n-1 do //找T的其余n-2条边// 设j是NEAR(j)≠0 且COST(j,NEAR(j))最小的下标 (T(i,1),T(i,2))←(j,NEAR(j)) mincost←mincost+COST(j,NEAR(j)) NEAR(j)←0 for k←1 to n do //修改NEAR// if NEAR(k)≠0 and COST(k,NEAR(k))＞COST(k,j) then NEAR(k)←j endif repeat if mincost＞∞ then print(‘no spanning tree’) endif end PRIM 计算复杂性：

30 4. Kruskal算法 （连通）图的边按成本的非降次序排列，下一条计入生成树T中的边是还没有计入的边中具有最小成本、且和T中现有的边不会构成环路的边。 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 边 (1,2) (3,6) (4,6) (2,6) 成本

31 V(TK) = {1,2,3,4,5,6} E(TK) = { (1,2),(2,6),(3,5),(4,6),(3,6) } 边
10 1 2 边 (3,5) 成本 35 35 3 5 25 15 4 20 6 V(TK) = {1,2,3,4,5,6} E(TK) = { (1,2),(2,6),(3,5),(4,6),(3,6) }

32 算法3.9 Kruskal算法 procedure KRUSKAL(E,COST,N,T,mincost)
//G有n个结点，E是G的边集。COST(u,v)是边(u,v)的成本。T是最小成本生成树的边集，mincost是它的成本// real mincost, COST(1:n,1:n); integer PARENT(1:n), T(1:n-1,2),n 以边成本为元素构造一个min堆 PARENT←1//每个结点都在不同的集合中// i←mincost←0 while i＜n-1 and 堆非空 do 从堆中删去最小成本边(u,v)并重新构造堆 j←FIND(u); k←FIND(v) if(j≠k) then i←i+1 T(i,1) ←u; T(i,2) ←v mincost←mincost + COST(u,v) call UNION(j,k) endif repeat if i≠n-1 then print(‘no spanning tree’) endif return end KRUSKAL

33 注： ● 边集以min-堆的形式保存，一条当前最小成本边可以在О(loge)的时间内找到； ● 当且仅当图G是不连通的，i≠n-1；此时算法具有最坏的执行时间； ● 算法的计算时间是О(eloge)

34 关于最小生成树算法的课堂练习 1。分别用Prim算法和Kruskal算法给出下图的最小生成树

35 2。如果要对任意的图（不一定是连通图）求出最小生成森林
（minimum spanning forest），最小生成森林是一个森林，其中的树都是 一个图的连通子图的最小生成树，应该如何修改Kruskal算法。

36 3。 Prim算法和Kruskal算法对权重有负数的图有效吗？

37 3。 Prim算法和Kruskal算法对权重有负数的图有效吗？
4。设计一个算法求一个连同图的最大生成树（maximum spanning tree） ,最大生成树是权重之和最大的生成树。（算法作业也可以答这个题目）

38 3.6 单源最短路径 1. 问题描述 最短路径问题： ● 每对结点之间的路径问题 ● 特定线路下的最短路径问题 ● 单源最短路径问题等
3.6 单源最短路径 1. 问题描述 最短路径问题： ● 每对结点之间的路径问题 ● 特定线路下的最短路径问题 ● 单源最短路径问题等 单源最短路径问题 已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。 注：假定边的权值为正。

39 例3.10 如图所示。设v0是起始点，求v0到其它各结点的最短路径。
45 50 10 15 20 3 35 30 路径 长度 (1) v0v (2) v0v2v (3) v0v2v3v (4) v0v V5不可达 注：路径按照长度的非降次序给出

40 2. 贪心策略求解 路径 长度 (1) v0v2 10 (2) v0v2v3 25 (3) v0v2v3v1 45 (4) v0v4 45
1) 度量标准 量度的选择：迄今已生成的所有路径长度之和——为使之达到最小，其中任意一条路径都应具有“最小”长度： 假定已经构造了i条这样的最短路径，则下一条要构造的路径应是下一条最短的路径。 处理规则：按照路径长度的非降次序依次生成从结点v0到其它各结点的最短路径。 例： 路径 长度 (1) v0v (2) v0v2v (3) v0v2v3v (4) v0v 问题：如何对尚未生成的路径长度进行排序，以确定其中最短者？如左边的v0v2v3是如何确定的?

41 2) 贪心算法 则有: ♠ 设S是已经对其生成了最短路径的结点集合（包括源结点v0)。
♠ 对于当前不在S中的结点w，记DIST(w)是从v0开始，只经过S中的结点而在w结束的那条最短路径的长度。 则有: S 如上例中的步骤(1)中S就是v0v2时DIST(V1)=50但步骤(2)中S是 v0v2v3时 DIST(V1)=45 W 如上例中的步骤(1)中S就是v0v2步骤(2)中的S就是 v0v2v3

42 ① 如果下一条最短路径是到结点u，则这条路径是从结点v0出发，在u处终止，且只经过那些在S中的结点,即由v0至u的这条最短路径上的所有中间结点都是S中的结点，证明如下：
设w是这条路径上的任意中间结点，则从v0到u的路径也包含了一条从v0到w的路径，且其长度小于从v0到u的路径长度。 v0,s1,s2,…,w,…,sm-1,均在S中 根据生成规则：最短路径是按照路径长度的非降次序生成的，因此从v0到w的最短路径应该已经生成。从而w也应该在S中。 故,不存在不在S中的中间结点。 ② 所生成的下一条路径的终点u必定是所有不在S内的结点中具有最小DIST(u)值的结点。即DIST(u)=min{DIST(x)|x∈V-S}证明见教材p36

43 ③如果选出了这样结点u并生成了从v0到u的最短路径之后，结点u将成为S中的一个成员。此时，那些从v0出发，只经过S中的结点并且在S外的结点w处结束的最短路径长度可能会减小——DIST(w)的值变小：
这些长度发生改变的路径，必定是一条从v0出发，经过u然后到w的更短的路径。 S W u v0 ★ 根据DIST(w)的定义， DIST(w)所表示的最短路径上，所有中间结点都在S中；故只考虑<u,w>∈E和 的情况 ★ 对于从v0至w，且经过最后一个中间结点为u的最短路径，有： DIST(w) = DIST(u) + c(u,w) ★ 随着u的加入， DIST(w)调整为 DIST(w) = min(DIST(w),DIST(u) + c(u,w)) 老的DIST(w)

44 procedure SHORTEST-PATHS(v,COST,DIST,n)
算法3.10 生成最短路径的贪心算法 procedure SHORTEST-PATHS(v,COST,DIST,n) //G是一个n结点有向图，它由其成本邻接矩阵COST(n,n)表示。DIST(j)被置 从结点v到结点j的最短路径长度，这里1≤j≤n。DIST(v)被置成零// boolean S(1:n);real COST(1:n,1:n),DIST(1:n) integer u,v,n,num,i,w for i←1 to n do //将集合S初始化为空// S(i) ←0;DIST(i) ←COST(v,i) //若 ，则DIST(i)=∞// repeat S(v) ←1;DIST(v) ←0 //结点v计入S// for num←2 to n-1 do //确定由结点v出发的n-1条路// 选取结点u,它使得DIST(u)= S(u) ←1 //结点u计入S// for 所有S(w)＝0的结点w do //修改DIST(w)// DIST(w) = min(DIST(w), DIST(u) + COST(u,w)) end SHORTEST-PATHS

45 3) 计算时间 ⑵最短路径算法的时间复杂度 ⑴ 算法3.10的计算时间是：О(n2) ⑴ for i←1 to n do
S(i) ←0;DIST(i) ←COST(v,i) repeat ⑵ for num←2 to n-1 do 选取结点u,它使得DIST(u)= S(u) ←1 for 所有S(w)＝0的结点w do DIST(w) = min(DIST(w), DIST(u) + COST(u,w)) ⑵最短路径算法的时间复杂度 由于任何一条边都有可能是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是О(e)。 在用邻接矩阵表示的图的情况下复杂度是： О(n2) 这里我们要注意学习粗线条的分析方法

46 例3.11 求下图中从v1出发到其余各结点的最短路径
20 50 25 70 10 55 40 30 图的成本邻接矩阵： ∞ +∞ ∞ +∞ ∞ +∞ ∞ +∞ +∞ ∞ +∞ +∞ +∞ ∞ ∞ +∞ +∞ +∞ +∞ ∞ +∞ +∞ +∞ +∞ ∞ +∞ +∞ +∞ +∞ ∞ 0

47 算法的执行在有n-1个结点加入到S中后终止，此时求出了v0至其它各结点的最短路径。
算法的执行轨迹描述 迭代 选取的结点 S DIST (1) (2) (3) (4) (5) (6) (7) 置初值 1 2 3 4 5 － 6 1,2 1,2,4 1,2,4,3 1,2,4,3,5 1,2,4,3,5,6 ∞ +∞ +∞ ∞ ∞ ∞ ∞ 算法的执行在有n-1个结点加入到S中后终止，此时求出了v0至其它各结点的最短路径。 问题：如何求出所有这些最短路径？

48 3. 最短路径生成树 对于无向连通图G，由结点v到其余各结点的最短路径的边构成G的一棵生成树，称为最短路径生成树。
2 1 3 5 6 7 4 8 55 25 40 35 15 10 50 20 45 30 原始图 由结点1出发的最短路径生成树 最小成本生成树