第4章-贪心法

1、1贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，以逐步的局部最优，达到最终的全局最优。第第4章章 贪心法贪心法（Greedy Approach）24.1 贪心法的设计思想贪心法的设计思想4.2 贪心法的正确性证明贪心法的正确性证明4.3 对贪心法得不到最优解情况的处理对贪心法得不到最优解情况的处理4.4 贪心法的典型应用贪心法的典型应用 4.4.1 最优前缀码最优前缀码 4.4.2 最小生成树最小生成树 4.4.3 单源最短路径单源最短路径第第4章章 贪心法贪心法（Greedy Approach）3例：币种统计问题例：币种统计问题某单位给每个职工发工资（精确到元）。为了保证

2、不要临某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱时兑换零钱, 且取款的张数最少，取工资前要统计出所有且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值职工的工资所需各种币值(100,50,20,10,5,2,1元共七种元共七种)的的张数。张数。注：假若注：假若,某国的币种是这样的某国的币种是这样的,共共9种种: 100,70,50,20,10,7,5,2,1。4活动选择问题活动选择问题输入：输入：S =1, 2, , n为为n 项活动的集合，项活动的集合，si, fi 分别为活动分别为活动 i 的开始和结束时间，的开始和结束时间，活动活动 i 与与 j 相容相容 s

3、i fj 或或 sj fi .求：最大的两两相容的活动集求：最大的两两相容的活动集 A 实例实例策略策略1：排序使得：排序使得 s1 s2 sn，从前向后挑选，从前向后挑选策略策略2：排序使得：排序使得 f1s1 f2s2 fnsn，从前向后挑选，从前向后挑选策略策略3：排序使得：排序使得 f1 f2 fn，从前向后挑选，从前向后挑选以上策略中的挑选都要注意满足相容性条件以上策略中的挑选都要注意满足相容性条件4.1贪心法的设计思想贪心法的设计思想i12345678910si1325456882fi45679910111213两个反例两个反例 2310 2 5 8 10 15 20 2310 2

4、 5 8 10 15 20 策略策略1：S=1,2,3，s1=0, f1=20, s2=2, f2=5, s3=8, f3=15 策略策略2：S=1,2,3，s1=0, f1=8, s2=7, f2=9, s3=8, f3=15 6贪心算法贪心算法算法算法4.1 Greedy Select输入：活动集输入：活动集S，si，fi, i=1,2,n，且，且 f1 fn 输出：输出：A S，选中的活动子集，选中的活动子集 1. nlengthS / 活动个数活动个数 2. A1 3. j1 /已选入的最后一个活动的标号已选入的最后一个活动的标号 4. for i2 to n do 5. if si

5、fj /判断相容性判断相容性 6. then A A i 7. j i 8. return A 最后完成时间最后完成时间 t = max fk: k A 7输入：输入：S=1, 2, , 10i12345678910si1305356882fi45678910111213问题：如何证明该算法对所有的实例都能得到正确的解？问题：如何证明该算法对所有的实例都能得到正确的解？算法运行实例算法运行实例解解: : A = 1, 4, 8, t =11时间复杂度：排序时间复杂度：排序+活动选择活动选择=O(nlogn)+O(n)=O(nlogn)8算法的正确性证明算法的正确性证明证：证：S=1, 2, ,

6、 n是活动集，是活动集，且且 f1 fn 归纳基础：归纳基础：k=1, 证明存在最优解包含活动证明存在最优解包含活动1任取最优解任取最优解A, A中的活动按截止时间递增排列中的活动按截止时间递增排列. 如果如果A的第的第一个活动为一个活动为 j，j 1, 令令 A= (A j ) 1, 由于由于 f1 fj , A也是最优解，且含有也是最优解，且含有1. 定理定理4.1 算法算法Select 执行到第执行到第 k 步步, 选择选择 k 项活动项活动 i1= 1, i2, , ik, 那么存在最优解那么存在最优解 A 包含包含 i1=1, i2, , ik .根据定理：针对上述问题，算法至多到第

7、根据定理：针对上述问题，算法至多到第 n 步得到最优解步得到最优解9)(,.,.,112121 kkkkiBiiiiBiii也是原问题的最优解也是原问题的最优解. .归纳步骤：假设命题对归纳步骤：假设命题对 k 为真为真, 证明对证明对 k+1 也为真也为真. 算法执行到第算法执行到第 k 步步, 选择了活动选择了活动 i1=1, i2, , ik, 根据归纳假设根据归纳假设存在最优解存在最优解 A 包含包含 i1= 1, i2, , ik , A中剩下的活动选自集合中剩下的活动选自集合 S= i | i S, si fk, 且且 A = i1, i2, , ik B其中其中B是是S的最优解的

8、最优解.（若不然（若不然, S的最优解为的最优解为B*, B*的活动的活动比比 B多，那么多，那么B* 1, i2, , ik是是 S 的最优解，且比的最优解，且比 A的活的活动多动多,与与 A 的最优性矛盾的最优性矛盾.）根据归纳基础，存在根据归纳基础，存在 S的最优解的最优解B含有含有S中的第一个活动，中的第一个活动，即即ik+1, 且且|B|=|B|, 于是于是 算法正确性证明（续）算法正确性证明（续）10贪心算法的特点贪心算法的特点设计要素：设计要素：(1)贪心法适用于组合优化问题贪心法适用于组合优化问题. 求解过程是多步判断过程，最终的判断序列对应于问题求解过程是多步判断过程，最终的

9、判断序列对应于问题 的最优解的最优解. 判断依据某种判断依据某种“短视的短视的”贪心选择性质，性质的好坏决贪心选择性质，性质的好坏决 定了算法的成败定了算法的成败. 贪心法必须进行正确性证明贪心法必须进行正确性证明贪心法的优势：贪心法的优势：算法简单，时间和空间复杂性低算法简单，时间和空间复杂性低11 4.2 贪心法的正确性证明贪心法的正确性证明数学归纳法数学归纳法 1. 叙述一个描述算法正确性的命题叙述一个描述算法正确性的命题P(n)，n为算法步数或者为算法步数或者 问题规模问题规模 2. 归纳基础：归纳基础：P(1) 或或 P(n0)为真为真, n0为某个自然数为某个自然数 3. 归纳步骤

10、：归纳步骤：P(k) P(k+1) 第一数学归纳法第一数学归纳法 k(k | I |； 那么那么 I* 1是关于是关于 N 和和C的解且的解且 | I* 1| | I 1 | = | I| 与与 I 的最优性矛盾的最优性矛盾.正确性证明正确性证明14最小延迟调度最小延迟调度例例4.3 最小延迟调度最小延迟调度给定客户集合给定客户集合A， i A，ti 为服务时间，为服务时间，di 为客户期待完成为客户期待完成时间，时间，ti, di为正整数为正整数. 一个一个调度调度是函数是函数 f : AN，f(i)为客为客户户 i 的开始时间的开始时间. 求求最大延迟达到最小的调度，即求最大延迟达到最小的

11、调度，即求 f 使使得得)(maxminiiAifdtif )()(or)()(,iftjfjftifjiAjiji h(A,B) = |ba|minmaxBbAa15实例实例调度调度1： f1(1)=0, f1(2)=5, f1(3)=13, f1(4)=17, f1(5)=27 各任务延迟：各任务延迟：0, 1, 2, 16, 10; 最大延迟：最大延迟：16 1 2 3 4 5 5 13 17 27 30 调度调度2： f2(1)=0, f2(2)=15, f2(3)=23, f2(4)=5, f2(5)=27 各任务延迟：各任务延迟：0, 11, 12, 4, 10; 最大延迟：最大延

12、迟：12A=1, 2, 3, 4, 5, T=, D= 1 4 2 3 5 5 15 23 27 3016贪心策略选择贪心策略选择贪心策略贪心策略1：按照：按照 ti 从小到大安排任务从小到大安排任务贪心策略贪心策略2：按照：按照 di ti 从小到大安排任务从小到大安排任务贪心策略贪心策略3：按照：按照 di 从小到大安排任务从小到大安排任务策略策略1 对某些实例得不到最优解对某些实例得不到最优解. 反例：反例：t1=1, d1=100, t2=10, d2=10 策略策略2 对某些实例得不到最优解对某些实例得不到最优解. 反例：反例：t1=1, d1=2, t2=10, d2=10 17算

13、法设计算法设计算法算法4.3 Schedule 输入：输入：A, T, D输出：输出：f 1. 排序排序A使得使得 d1 d2 dn 2. f(1)0 3. i2 3. while i n do 4. f(i)f(i 1)+ti 1 /任务任务i-1结束时刻是任务结束时刻是任务i开始时刻开始时刻 5. ii+1设计思想：按完成时间从早到晚安排任务，没有空闲设计思想：按完成时间从早到晚安排任务，没有空闲 18交换论证：正确性证明交换论证：正确性证明算法的解的性质：算法的解的性质： (1) 没有空闲时间没有空闲时间, 没有逆序没有逆序. (2) 逆序逆序 (i, j): f(i) dj 引理引理4

14、.14.1 所有没有逆序、没有空闲时间的调度具有相同的所有没有逆序、没有空闲时间的调度具有相同的最大延迟最大延迟. . 证证: 设设 f 没有逆序，在没有逆序，在 f 中具有相同完成时间的客户中具有相同完成时间的客户i1, i2, , ik 必被连续安排必被连续安排. 在这在这k个客户中最大延迟是最后一个客个客户中最大延迟是最后一个客户，被延迟的时间是户，被延迟的时间是 与与 i1, i2, , ik 的排列次序无关的排列次序无关. dttkjij 1019交换论证交换论证证明思想：证明思想：从一个没有空闲时间的最优解出发，在不从一个没有空闲时间的最优解出发，在不改变最优性的条件下，转变成没有

15、逆序的解改变最优性的条件下，转变成没有逆序的解. 根据引理根据引理 1，这个解和算法的解具有相同的最大延迟这个解和算法的解具有相同的最大延迟. 证明要点证明要点(1) 相邻逆序的存在性：如果一个最优调度存在逆序，那么相邻逆序的存在性：如果一个最优调度存在逆序，那么存在存在 i n 使得使得 (i, i+1) 构成一个逆序构成一个逆序. (2) 交换相邻的逆序交换相邻的逆序 i 和和 j ，得到的解的调度仍旧最优，得到的解的调度仍旧最优. (3) 每次交换后逆序数减每次交换后逆序数减1，至多经过，至多经过 n(n 1)/2 次交换得到次交换得到一个没有逆序的最一个没有逆序的最 优调度优调度.定理

16、定理4.3 在一个没有空闲时间的最优解中，最大延迟是在一个没有空闲时间的最优解中，最大延迟是r，如果仅对具有相邻逆序的客户进行交换，得到的解的最大如果仅对具有相邻逆序的客户进行交换，得到的解的最大延迟不会超过延迟不会超过r。20delay(f,i)=stj+ti di delya(f,j) rdelay(f, j)s+ti+tjdj (1) 交换交换 i, j 对其他客户的延迟时间没影响对其他客户的延迟时间没影响(2) 交换后不增加交换后不增加 j 的延迟的延迟(3) i 在在 f 的延迟的延迟delay(f,i)小于小于 j 在在 f 的延迟的延迟 delay(f,j), 因此小于因此小于f

17、 的最大延迟的最大延迟 rdj di L2i 2得到最优解的判定条件得到最优解的判定条件定理定理4.6 对每个正整数对每个正整数k，假设对所有非负整数，假设对所有非负整数 y 有有Gk(y)=Fk(y)且存在且存在 p 和和 满足满足 vk+1=pvk , 其中其中0 pw3 v3=pv2 p=3, =1. w3+G2( )=1+1 = 2 pw2=31=3 w3+G2( ) p w2结论结论：G3(y)=F3(y), 对于对于y=pv3=28，G4(y)F4(y) 274.4 贪心法的典型应用贪心法的典型应用4.4.1 最优前缀码最优前缀码二元前缀码二元前缀码用用0-1字符串作为代码表示字符

18、，要求任何字符的代码都字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀不能作为其它字符代码的前缀非前缀码的例子非前缀码的例子 a: 001, b: 00, c: 010, d: 01解码的歧义，例如字符串解码的歧义，例如字符串 0100001 解码解码1: 01, 00, 001 d, b, a 解码解码2: 010, 00, 01 c, b, d 前缀码的二叉树及权值前缀码的二叉树及权值前缀码前缀码： 00000, 00001, 0001, 001, 01, 100, 101, 11频率频率: 00000: 5%, 000001: 5%, 0001: 10%, 001:

19、 15%, 01: 25%, 100: 10%, 101: 10%, 11: 20% 平均的二进制位数平均的二进制位数 B=(5+5)5+104 +(15+10+10)3 +(25+20)2/100 =2.85 最优前缀码最优前缀码 权值权值B最小最小 )()(1 niiixdxfB最优前缀码问题最优前缀码问题例例4.6 最优前缀码最优前缀码 给定字符集给定字符集 C=x1, x2, , xn和每个字符和每个字符的频率的频率f(xi), i=1,2,n, 求关于求关于C 的一个最优前缀码的一个最优前缀码. 算法算法4.4 Huffman(C) 输入：输入：C=x1, x2, , xn， f(x

20、i), i=1, 2, , n. 输出：输出：Q / /队列队列 1. n|C| 2. QC /按频率递增构成队列按频率递增构成队列Q 3. for i1 to n 1 do 4. zAllocate-Node() / 生成结点生成结点 z 5. z.leftQ中最小元中最小元 / 取出取出Q最小元作最小元作z的左儿子的左儿子 6. z.rightQ中最小元中最小元 / 取出取出Q最小元作最小元作z的右儿子的右儿子 7. f(z)f(x)+f(y) 8. Insert(Q,z) / 将将 z 插入插入Q 9. return Q30例如例如 a:45, b:13; c:12; d:16; e:9

21、; f:5 平均位数：平均位数：4 (0.05+0.09)+3 (0.16+0.12+0.13)+1 0.45= 2.24编码：编码：f-0000, e-0001, d-001, c-010, b011, a-1fe14dcb253055100a5916121345实例实例31则则T与与T 的权之差为的权之差为其中其中dT(i)为为i 在在T 中的层数（中的层数（i 到根的距离）到根的距离） CiCiTTidifidifTBTB0)()() ()(引理引理4.2 设设C是字符集，是字符集， c C, f(c)为频率，为频率，x, y C, f(x), f(y) 频率最小，那么存在最优二元前缀码

22、使得频率最小，那么存在最优二元前缀码使得 x, y 的码字等长，的码字等长，且仅在最后一位不同且仅在最后一位不同. TTfx fafy fba与与 x 交换交换b与与 y 交换交换yabxTbxyaT算法正确性证明算法正确性证明:引理引理4.232引理引理4.3引理引理4.3 设设 T 是二元前缀码所对应的二叉树，是二元前缀码所对应的二叉树， x, y T, x, y是是树叶兄弟，树叶兄弟，z 是是 x, y 的父亲，令的父亲，令T = T x, y, 且令且令 z 的频率的频率 f(z) = f(x)+f(y)，T是对应于二元前缀码是对应于二元前缀码 C = (C x, y) z 的二叉树，

23、那么的二叉树，那么 B(T)=B(T)+f(x)+f(y). )()() ()()()()()()()()()()()()()()()(, ,yfxfTByfxfzdzfidifydyfxdxfidifidifTBTziTiTTTyxiTiTTiT 证证 c C x,y,有有 dT(c) = dT (c) f(c)dT(c)=f(c)dT (c) dT(x) = dT(y) = dT (z) +1. 33定理定理4.7 Haffman 算法对任意规模为算法对任意规模为n（n 2）的字符集）的字符集C 都都得到关于得到关于C 的最优前缀码的二叉树的最优前缀码的二叉树. 证明：归纳法证明：归纳法归

24、纳基础归纳基础 n=2，字符集，字符集C=x1,x2，Huffman算法得到的代码算法得到的代码是是0和和1，是最优前缀码，是最优前缀码.归纳步骤归纳步骤 假设假设Huffman算法对于规模为算法对于规模为k 的字符集都得到最的字符集都得到最优前缀码优前缀码. 考虑规模为考虑规模为k+1的字符集的字符集C=x1, x2, ., xk+1, 其中其中x1, x2 C是频率最小的两个字符是频率最小的两个字符. 令令 C=(Cx1,x2) z， f(z)=f(x1)+f(x2)根据归纳假设，根据归纳假设，Huffman算法得到一棵关于字符集算法得到一棵关于字符集C 、频率、频率f(z)和和f(xi)

25、（i=3,4,.,k+1）的最优前缀码的二叉树）的最优前缀码的二叉树T.34把把x1和和 x2作为作为 z 的儿子附加到的儿子附加到T上，得到树上，得到树T，那么，那么T是关于是关于字符集字符集C=(Cz) x1,x2 的最优前缀码的二叉树的最优前缀码的二叉树. 如若不然，存在更优的树如若不然，存在更优的树T*. 根据引理根据引理1，其最深层树叶是，其最深层树叶是x1, x2，且，且B(T*)B(T). 去掉去掉T*中的中的x1和和x2，根据引理，根据引理2，所得，所得二叉树二叉树T*满足满足 B(T*)B(T*)(f(x1)+f(x2)B(T)(f(x1)+f(x2) =B(T)与与T是一棵

26、关于是一棵关于C的最优前缀码的二叉树矛盾的最优前缀码的二叉树矛盾. 证明：归纳法证明：归纳法(续续)zTx2x1Tz Huffman树应用树应用: :文件归并文件归并例例4.7 问题：给定一组不同长度的排好序文件构成的集合问题：给定一组不同长度的排好序文件构成的集合 S = f1, , fn 其中其中 fi 表示第表示第 i 个个文件含有的项数文件含有的项数. 使用二分归并将这些文件使用二分归并将这些文件归并成一个有序的文件归并成一个有序的文件. 归并过程对应于二叉树：文件为树叶归并过程对应于二叉树：文件为树叶. fi与与fj 归并的文件是它归并的文件是它们的父结点们的父结点. 归并代价归并代

27、价(最多的比较次数最多的比较次数)：结点：结点 fi与与 fj 归并代价为归并代价为 fi+fj 1. 总的代价：每个文件总的代价：每个文件(树叶树叶)的深度乘以文件大小之和再减掉的深度乘以文件大小之和再减掉归并次数归并次数 n 135)1()( nfidiSi36实例实例顺序归并顺序归并323110702141187388104192212818701032414973119192Huffman树归并树归并代价代价顺序归并：顺序归并： (21+10+32+41) 3+(18+70) 2 5=483Huffman树归并：树归并：(10+18) 4+21 3+(70+41+32) 2 5=456

28、实例：实例：S = 21,10,32,41,18,70 37无向连通带权图无向连通带权图G=(V,E,W)，w(e) W是边是边e的权的权. G的一棵的一棵生成树是包含了生成树是包含了G的所有顶点的树的所有顶点的树, 树中各边的权之和树中各边的权之和称为树的权，具有最小权的生成树称为称为树的权，具有最小权的生成树称为G的的最小生成树最小生成树. 命题命题4.1 设设G是是 n阶连通图，那么阶连通图，那么(1) T是是G 的生成树当且仅当的生成树当且仅当 T 有有n1条边条边. 如果如果T是是G的生成树，的生成树，e T，那么，那么T e含有一个圈含有一个圈 (回回 路路). 问题：给定连通带权

29、图问题：给定连通带权图G，求，求G的一棵最小生成树的一棵最小生成树. 算法：算法：Prim算法算法和和Kruskal算法算法 4.4.2 最小生成树最小生成树12435661556365421243566155636542364251Prim算法算法 算法算法4.5 Prim(G,E,W) 1S1；T 2while V S do 3 从从V S中选择中选择 j 使得使得 j 到到 S 中顶点的边中顶点的边e的权最小的权最小 4 SS j, T T e 39对步数归纳对步数归纳定理定理4.8 对于任意对于任意 k 1, 算法对算法对 n 阶图得到一棵最小生成树阶图得到一棵最小生成树.证明证明 n

30、=2, 只有一条边，命题显然为真只有一条边，命题显然为真. 假设对于假设对于n个顶点的图算法正确，考虑个顶点的图算法正确，考虑n+1个顶点的图个顶点的图G, G中最小权边中最小权边 e = i, j，从从G 中中短接短接 i 和和 j，得到图得到图G. 根根据归纳假设，由算法存在据归纳假设，由算法存在G 的最小生成树的最小生成树T.令令T=T e, 则则T 是关于是关于G 的最小生成树的最小生成树. 否则存在否则存在G 的含边的含边e 的最小生成树的最小生成树T*，W(T*)W(T). (如果如果 e T*, 在在T*中加边中加边e，形成回路，形成回路. 去掉回路中任意别的边去掉回路中任意别的

31、边所得生成树的权仍旧最小所得生成树的权仍旧最小). 在在T*中短接中短接 e 得到得到G 的生成的生成树树T* e, 且且 W(T* e)=W(T*) w(e)W(T) w(e )=W(T)， 与与T 的最优性矛盾的最优性矛盾. Kruskal算法正确性证明算法正确性证明算法的实现与时间复杂度算法的实现与时间复杂度数据结构：数据结构：建立建立FIND数组，数组，FINDi 是结点是结点 i 的连通分支标记的连通分支标记. (1) 初始初始FINDi=i. (2) 两个连通分支合并，则将较小分支结点的两个连通分支合并，则将较小分支结点的FIND值更新为值更新为 较大分支的标记较大分支的标记时间复

32、杂度：时间复杂度： 每个结点至多更新每个结点至多更新logn次，建立和更新次，建立和更新FIND数组的总时数组的总时 间为间为O(nlogn)(2) 算法时间为算法时间为 O(mlogm) + O(nlogn) + O(m) = O(mlogn) 边排序边排序 FIND数组数组 其他其他45给定带权有向网络给定带权有向网络G=(V,E,W),每条边每条边e=的权的权w(e)为非为非负实数，表示从负实数，表示从i到到j 的距离的距离. 源源点点s V，求从，求从 s 出发到达其出发到达其它结点的最短路径它结点的最短路径.Dijkstra算法：算法： x S x V 且从且从 s 到到 x 的最短

33、路径长度已知的最短路径长度已知初始：初始：S=s ，S=V 时算法结束时算法结束从从 s 到到 u 相对于相对于S 的最短路径：从的最短路径：从 s 到到 u且仅经过且仅经过S 中顶点中顶点的最短路径的最短路径distu：从：从 s 到到 u 的相对于的相对于S 的最短路径的长度的最短路径的长度shortu：从：从 s 到到 u 的最短路径的长的最短路径的长distu shortu 4.4.3 单源最短路径单源最短路径46 Dijkstra算法算法算法算法4.7 Dijkstra输入：带权有向图输入：带权有向图G=，源点，源点s V输出：从输出：从 s 到每个结点到每个结点 i 的最短路径的最

34、短路径 1. Ss 2. dists0 3. for i V s do 4. distiw(s,i) / 如果如果s到到i没有边没有边, w(s,i)= 5. while V S do 6. 从从V S中取出具有相对中取出具有相对S的最短路径的顶点的最短路径的顶点 j 7. SS j; 8. for i V S do 9. if distj+w(j,i)disti 10. then disti distj+w(j,i) / 更新更新disti47S=1, dist1=0 dist2=10, dist6=3 dist3=dist4=dist5= 实例实例104165433737612251041

35、6543373761225S=1,6, dist1=0, dist6=3 dist2=5, dist4=9, dist5=4 dist3= 输入：输入：G=，源点，源点 1V=1, 2, 3, 4, 5, 648S=1,6,5, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9, dist3= 实例（续）实例（续）1041654337376122510416543373761225S=1,6,5,2, dist1=0, dist6=3, dist5=4 dist2=5 dist3=12 dist4=9 49S=1,6,5,2,4, dist1=0, dist

36、6=3, dist5=4 dist2=5, dist4=9, dist3=12 实实 例（续）例（续）1041654337376122510416543373761225S=1,6,5,2,4,3, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9 dist3=12 解：解：short1=0, short2=5,short3=12, short4=9，short5=4, short6=3. 50 算法正确性证明算法正确性证明定理定理4.10 当算法进行到第当算法进行到第 k 步时，对于步时，对于S 中每个结点中每个结点 i， disti = shorti 归

37、纳基础归纳基础 k=1, S=s, dists=shorts=0, 命题为真命题为真.归纳步骤归纳步骤 假设命题对于假设命题对于k 为真为真. 考虑考虑 k+1步步, 选择顶点选择顶点v (边边u,v). 假若存在另一条假若存在另一条 s-v 路径路径 L (绿色绿色)，最后一次出，最后一次出S 的的顶点为顶点为 x, 在这次从在这次从S 中出来后中出来后经过经过V S 的第一个顶点为的第一个顶点为 y.时间复杂度时间复杂度 T(n)=O(n2)distv=shortvsuxyvLSdistv disty /v先被选先被选 disty+d(y,v) L 51 贪心法小结贪心法小结适用于组合优化

38、问题，适用于组合优化问题， 求解过程是多步判断求解过程是多步判断. 判断的依据判断的依据是局部最优策略，使目标值达到最大是局部最优策略，使目标值达到最大(或最小或最小)，与前面的，与前面的子问题计算结果无关子问题计算结果无关. (2) 局部最优策略的选择是算法正确性的关键局部最优策略的选择是算法正确性的关键. (3) 正确性证明方法：数学归纳法、交换论证正确性证明方法：数学归纳法、交换论证. 使用数学归纳使用数学归纳 法主要通过对算法步数或者问题规模进行归纳法主要通过对算法步数或者问题规模进行归纳. 如果要证如果要证 明贪心策略是错误的，只需举出反例明贪心策略是错误的，只需举出反例. (4)

39、自顶向下求解，通过选择将问题归约为小的子问题自顶向下求解，通过选择将问题归约为小的子问题. (5) 如果贪心法得不到最优解，可以对问题的输入进行分析如果贪心法得不到最优解，可以对问题的输入进行分析 或者估计算法的近似比或者估计算法的近似比. (6) 如果对原始数据排序之后，贪心法往往是一轮处理，时如果对原始数据排序之后，贪心法往往是一轮处理，时 间复杂度和空间复杂度低间复杂度和空间复杂度低. 52 不同算法策略特点不同算法策略特点贪心法：贪心法：通过局部最优决策到达全局最优决策通过局部最优决策到达全局最优决策 递推法：递推法：由当前问题的逐步解决从而得到整个问题的解，它依赖由当前问题的逐步解决

40、从而得到整个问题的解，它依赖信息间递推关系，由小到大。信息间递推关系，由小到大。(3) 递归法：递归法：利用大问题与其子问题间的递推关系。将大问题分解成规利用大问题与其子问题间的递推关系。将大问题分解成规模较小的问题，然后从小问题的解构造出大问题的解。模较小的问题，然后从小问题的解构造出大问题的解。 (4) 枚举法：枚举法：逐一尝试。逐一尝试。(5) 递归回溯法：递归回溯法：通过递归尝试遍历问题各个可能解的通路，不同时通过递归尝试遍历问题各个可能解的通路，不同时回溯上一步。回溯上一步。 (6) 分治法：分治法：复杂问题分解成独立子问题并解决，再将它们的解合成。复杂问题分解成独立子问题并解决，再

41、将它们的解合成。(7) 动态规划法：动态规划法：保留多个阶段的决策结果，为以后每个阶段提供决保留多个阶段的决策结果，为以后每个阶段提供决策；问题不能分为独立阶段，且符合最优化原理；解决子问题冗余策；问题不能分为独立阶段，且符合最优化原理；解决子问题冗余。53 算法策略间的关联算法策略间的关联对问题进行分解的算法策略：对问题进行分解的算法策略：分治法、动态规划分治法、动态规划多阶段逐步解决问题的策略：多阶段逐步解决问题的策略：贪心法、递推法、递贪心法、递推法、递归法、动态规划归法、动态规划全面逐一尝试：全面逐一尝试：枚举法、递归回溯法枚举法、递归回溯法整数的分划问题整数的分划问题( (较复杂的递

42、归设计较复杂的递归设计) )对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n写成一系列正整数之和的表达写成一系列正整数之和的表达式。例如，对于正整数式。例如，对于正整数n=6n=6，它可以分划为：，它可以分划为： 6 6 5+1 5+1 4+2, 4+1+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 3+3, 3+2+1, 3+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+11+1+1+1+1+1 根据例子发现根据例子发现“包括第一行以后的数据不超过包括第一行以后的数据不超过6

43、 6，包括，包括第二行的数据不超过第二行的数据不超过5 5，第六行的数据不超过，第六行的数据不超过1”1”。 因此，定义一个函数因此，定义一个函数Q(n,m)Q(n,m)，表示整数，表示整数n n的的“任何被加任何被加数都不超过数都不超过m”m”的分划的数目，的分划的数目，n n的所有分划的数目的所有分划的数目P(n)=Q(n,n)P(n)=Q(n,n)。模型建立模型建立 一般地一般地Q(n,m)Q(n,m)有以下递归关系：有以下递归关系： 1)Q(n,n)=1+Q(n,n-1) 1)Q(n,n)=1+Q(n,n-1) （m=nm=n）Q(n,n-1)Q(n,n-1)表示表示n n的所有其他分

44、划，即最大被加数的所有其他分划，即最大被加数m=n-1m=n-1的划分。的划分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn)2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (m1/27/81/2， 7/8-1/21/37/8-1/21/3， 7/8-1/2-1/3=1/247/8-1/2-1/3=1/24。过程如下：过程如下： 1)1)找最小的找最小的n n（也就是最大的埃及分数），使分数（也就是最大的埃及分数），使分数f1/nf1/n； 2)2)输出输出1/n1/n； 3)3)计算计算f=f-1/nf=f-1/n； 4)4)若此时的若此时的f f是埃及分数，输出是埃及

45、分数，输出f,f,算法结束算法结束, ,否则返回否则返回1 1）。）。 数学模型数学模型 记真分数记真分数F=A/BF=A/B；对；对B/AB/A进行整除运算进行整除运算, ,商为商为D, D, 余数为余数为0 0K KA A，它们之间的关系及导出关系如下：它们之间的关系及导出关系如下：( (例：例：A=7,B=8 = D=1,K=1)A=7,B=8 = D=1,K=1) B=AB=A* *D+KD+K，B/A=D+K/AB/A=D+K/AD+1D+1，A/BA/B1/(D+1)1/(D+1)，记，记C=D+1C=D+1。 这样我们就找到了分数这样我们就找到了分数F F所包含的所包含的“最大的

46、最大的”埃及分数就是埃及分数就是1/C1/C。进一步计算：进一步计算： A/B-1/C=A/B-1/C=（A A* *C-BC-B）/B/B* *C C 也就是说继续要解决的是有关也就是说继续要解决的是有关分子为分子为A=AA=A* *C-BC-B, ,分母为分母为B=BB=B* *C C的的问题。问题。 算法设计算法设计 由以上数学模型，真正的由以上数学模型，真正的算法过程算法过程如下：如下： 1)1)设某个真分数的分子为设某个真分数的分子为A(1A(1），分母为），分母为B B； 2)2)把把B B除以除以A A的商的整数部分加的商的整数部分加1 1后的值作为埃及后的值作为埃及 分数的一个

47、分母分数的一个分母C;C; 3) 3)输出输出1/C1/C； 4)4)将将A A乘以乘以C C减去减去B B作为新的作为新的A A； 5)5)将将B B乘以乘以C C作为新的作为新的B B； 6)6)如果如果A A大于大于1 1且能整除且能整除B,B,则最后一个分母为则最后一个分母为B/AB/A； 7)7)如果如果A A1,1,则最后一个分母为则最后一个分母为B;B;否则转步骤否则转步骤(2).(2). 例：例：7/8=1/2+1/3+1/247/8=1/2+1/3+1/24的解题步骤：的解题步骤： 同样用变量同样用变量A A表示分子，变量表示分子，变量B B表示分母；表示分母； C=8/7+

48、1=2 C=8/7+1=2 / /说明说明7/81/27/81/2， 打印打印1/21/2 A=7A=7* *2-8=62-8=6，B=BB=B* *C=16C=16/在计算在计算7/8-1/2=(77/8-1/2=(7* *2-8)/(72-8)/(7* *2)=6/16=A/B2)=6/16=A/B C=16/6+1=3 C=16/6+1=3 / /说明说明16/61/316/61/3，打印，打印1/31/3 A=6A=6* *3-16=2,B=B3-16=2,B=B* *C=16C=16* *3=483=48/在计算在计算6/16-1/3=(66/16-1/3=(6* *3-16)/(1

49、63-16)/(16* *3)=2/48=A/B3)=2/48=A/B A1 A1但但B/AB/A为整数为整数2424，打印，打印1/24 1/24 结束结束. .算法实现算法实现main（）（） int a,b,c; print(“input element”); input(a); print(“input denominator”); input(b); if(ab) print(“input error”); else if (a=1 or b mod a=0) print( a, /,b, = 1, /,b/a); else while(a1) c = b / a + 1 a = a

50、 * c b；b = b *c； print( 1/,c); if (b mod a =0 ) print (+1/; b / a); a=1; if( a 1) print(+); 取数游戏取数游戏 有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。 问题分析 算法设计 算法说明 算法分析 问题分析问题分析 这个游戏一般假设取数者只能看到这个游戏一般假设取数者只能看到2n2n个数中两边的数个数中两边的数, ,用贪婪算法的情况用贪婪算法的情况: : 若一组数据为：若一组数据为：6,16,27,6,12,9,2,11,6,56,16,27,6,12,9,

51、2,11,6,5。用贪婪策。用贪婪策略每次两人都取两边的数中较大的一个数略每次两人都取两边的数中较大的一个数, ,先取者胜先取者胜. .以以A先先取为例：取为例： 取数结果为：取数结果为： A 6,27,12,5,11=61 A 6,27,12,5,11=61 胜胜 B 16,6,9,6,2=39B 16,6,9,6,2=39 但若选另一组数据：但若选另一组数据：16,27,7,12,9,2,11,616,27,7,12,9,2,11,6。仍都用贪婪。仍都用贪婪算法，先取者算法，先取者A A败。败。 取数结果为：取数结果为： A 16,7,9,11=43A 16,7,9,11=43 B 27,

52、12,6,2=47 B 27,12,6,2=47 胜胜 其实，若我们只能看到两边的数据，则此题无论其实，若我们只能看到两边的数据，则此题无论先取还先取还是后取都无必胜的策略是后取都无必胜的策略。这时一般的策略是用近似贪婪算法。这时一般的策略是用近似贪婪算法。 但但若取数者能看到全部若取数者能看到全部2n2n个数个数，则此问题可有一些简单，则此问题可有一些简单的方法，有的虽不能保证所取数的和是最大，但确是一个先的方法，有的虽不能保证所取数的和是最大，但确是一个先取者必胜的策略。取者必胜的策略。 数学模型建立：数学模型建立：N个数排成一行，我们给这个数排成一行，我们给这N个数从左到右编号，个数从左

53、到右编号，依次为依次为1，2，N，因为，因为N为偶数，又因为是我们先取数，计为偶数，又因为是我们先取数，计算机后取数，所以一开始我们既可以取到一个奇编号的数（最算机后取数，所以一开始我们既可以取到一个奇编号的数（最左边编号为左边编号为1的数）又可以取到一个偶编号的数（最右边编号的数）又可以取到一个偶编号的数（最右边编号为为N的数）。的数）。 如果我们第一次取奇编号（编号为如果我们第一次取奇编号（编号为1）的数，则接着计算机）的数，则接着计算机只能取到偶编号（编号为只能取到偶编号（编号为2或或N）的数；）的数； 如果我们第一次取偶编号（编号为如果我们第一次取偶编号（编号为N）的数，则接着计算机）

54、的数，则接着计算机只能取到奇编号（编号为只能取到奇编号（编号为1或或N-1）的数；）的数； 即无论我们第一次是取奇编号的数还是取偶编号的数，接着即无论我们第一次是取奇编号的数还是取偶编号的数，接着计算机只能取到另一种编号（偶编号或奇编号）的数。计算机只能取到另一种编号（偶编号或奇编号）的数。 这是对第一个回合的分析，显然对以后整个取数过程都适这是对第一个回合的分析，显然对以后整个取数过程都适用。也就是说，我们能够控制让计算机自始自终只取一种编号用。也就是说，我们能够控制让计算机自始自终只取一种编号的数。这样，我们只要比较奇编号数之和与偶编号数之和谁大，的数。这样，我们只要比较奇编号数之和与偶编

55、号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇以决定最开始我们是取奇编号数还是偶编号数即可。（如果奇编号数之和与偶编号数之和同样大，我们第一次可以任意取数，编号数之和与偶编号数之和同样大，我们第一次可以任意取数，因为当两者所取数和相同时，先取者为胜。因为当两者所取数和相同时，先取者为胜。算法设计：算法设计：有了以上建立的高效数学模型，算法就很简单了，算有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就先了取数者就可以确定必胜的取数方式了。先了取数者就可以确定必胜的取

56、数方式了。以下面一排数为例：以下面一排数为例：1 2 3 10 5 6 7 8 9 4奇编号数之和为奇编号数之和为25（=1+3+5+7+9），小于偶编号数之和为），小于偶编号数之和为30（=2+10+6+8+4）。我们第一次取）。我们第一次取4，以后，计算机取哪边的数，以后，计算机取哪边的数我们就取哪边的数（如果计算机取我们就取哪边的数（如果计算机取1，我们就取，我们就取2；如果计算机取；如果计算机取9，我们就取，我们就取8）。这样可以保证我们自始自终取到偶编号的数，）。这样可以保证我们自始自终取到偶编号的数，而计算机自始自终取到奇编号的数。而计算机自始自终取到奇编号的数。背包问题背包问题

57、给定给定n种物品和一个容量为种物品和一个容量为C的背包，物的背包，物品品i的重量是的重量是wi，其价值为，其价值为vi，背包问题是如何，背包问题是如何选择装入背包的物品，使得装入背包中物品的选择装入背包的物品，使得装入背包中物品的总价值最大总价值最大? 于是，背包问题归结为寻找一个满足约束条于是，背包问题归结为寻找一个满足约束条件式件式1-1，并使目标函数式，并使目标函数式1-2达到最大的解向量达到最大的解向量X=(x1, x2, , xn)。设设xi表示物品表示物品i装入背包的情况，根据问题的要求，装入背包的情况，根据问题的要求，有如下约束条件和目标函数：有如下约束条件和目标函数： )1 (

58、101nixCxwiniii（式（式1-1）niiixv1max（式（式1-2）至少有三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。 （3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。 应用第三种贪心策略，每

59、次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。 120 50 背包 180 190 200(a) 三个物品及背包 (b) 贪心策略1 (c) 贪心策略2 (d) 贪心策略3 50 30 10 20 20 3020/30 20 1010/20 30 10例如，有3个物品，其重量分别是20, 30, 10，价值分别为60, 120, 50，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。 设背包

60、容量为C，共有n个物品，物品重量存放在数组wn中，价值存放在数组vn中，问题的解存放在数组xn中。 算法算法背包问题背包问题1改变数组改变数组w和和v的排列顺序，使其按单位重量价值的排列顺序，使其按单位重量价值vi/wi降序排列；降序排列；2将数组将数组xn初始化为初始化为0； /初始化解向量初始化解向量3i=1; 4循环直到循环直到(wiC) 4.1 xi=1; /将第将第i个物品放入背包个物品放入背包 4.2 C=C-wi; 4.3 i+;5. xi=C/wi;算法的时间主要消耗在将各种物品依其单位重量的价值从算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性