四、贪心算法

四、贪心算法 2．3 贪心法 (Greedy Approach) 一、基本思想适用问题：组合优化问题，适合优化原则。设计方法：多步判断。在每步判断时在满足约束条件的情况下根据某个局部的优化测度(可能是目标函数,也可能不是)考虑部分解中一个变量的选择。使用贪心法要解决的问题: 是否可以得到最优解? 不能得到最优解, 解与最优解的误差估计。例 1 活动选择问题 S ={1, 2, …, n}为 n 项活动的集合。si, fi 分别为活动 i 的开始和结束时间。活动 i 与 j 相容当且仅...

2．3 贪心法 (Greedy Approach) 一、基本思想适用问题：组合优化问题，适合优化原则。设计方法：多步判断。在每步判断时在满足约束条件的情况下根据某个局部的优化测度(可能是目标函数,也可能不是)考虑部分解中一个变量的选择。使用贪心法要解决的问题: 是否可以得到最优解? 不能得到最优解, 解与最优解的误差估计。例 1 活动选择问题 S ={1, 2, …, n}为 n 项活动的集合。si, fi 分别为活动 i 的开始和结束时间。活动 i 与 j 相容当且仅当 si ≥ fj, 或 fi ≥ sj , 求最大的两两相容的活动集。解：按照结束时间的递增顺序将活动排列为 1, 2, …, n, 使得 f1 ≤ f2 ≤… ≤ fn 算法 Greedy Select 1. n ← length[S]; 2. A←{1}; 3. j ← 1; 4. for i ← 2 to n 5. do if si ≥ fj 6. then A ← A∪{i}; 7. j ← i; 8. return A. 最后完成时间为 max {fk : k ∈A}. 例如下述输入 I 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12 13 14 解为 A = {1, 4, 8, 11} t=14 下面证明贪心法得到最优解。定理 1 算法 Select 执行到第 k 步, 选择 k 项活动 i1= 1, i2, …, ik, 那么存在最优解 A 包含 i1= 1, i2, …, ik 证明：对 k 归纳。 k=1, 设 S = {1, 2, …, n}是活动集，活动按截止时间递增顺序排序，则存在最优解含有活动 1。任取最优解 A, A 中的活动按照截止时间递增的顺序排列。如果 A 的第一个活动为 j，j ≠ 1, 令 A’= (A−{j})∪{1}, 由于 f1 ≤ fj, A’也是最优解，且含有 1. 假设命题对 k 为真。算法执行到第 k 步, 选择了活动 i1= 1, i2, …, ik, 根据归纳假设存在最优解 A 包含 i1= 1, i2, …, ik, A 中剩下的活动选自集合 S’ = {i | i ∈ S, si ≥ fk}。且 B=A-{ i1, i2, …, ik}是 S’的最优解。若不然，S’的最优解为 B’，B’的活动比 B 多，那么 B’∪{1, i2, …, ik}是 S 的最优解，且比 A 的活动多，与 A 的最优性矛盾。根据归纳基础，存在 S’的最优解 B 含有 S’中的第一个活动，设为 ik+1, 则 }){(},,...,{},...,,{ 112121 ++ −∪=∪ kkkk iBiiiiBiii 包含了算法 k+1 步的选择，也是原问题的最优解，命题对 k+1 为真。二、贪心算法的设计： 1. 贪心算法的设计要素 z 适用于满足优化原则的组合优化问题，将问题表示成多步判断。整个判断序列对应问题的最优解；而它的子序列对应子问题的最优解。 z 确定一个优化测度（不考虑以前各步的选择，只与当前状态有关），以优化测度的极大(或极小)作为贪心选择的依据 z 确定是否满足贪心选择性质——每步贪心选择都导致最优解。一般采用归纳法加以证明 z 自顶向下计算，通过贪心选择，将原问题规约为子问题。动态规划和贪心法比较：性质动态规划贪心法适用问题组合优化组合优化求解过程多步判断多步判断使用条件优化原则优化原则解的性质最优解有贪心选择性质下得到最优解否则为近似解求解关键列递推方程贪心选择性质的证明子问题形成先解子问题然后选择先选择然后构成子问题求解顺序自底向上自顶向下数据结构数值表记录优化函数值标记表记录子问题划分无特殊要求时间复杂性依赖子问题重叠程度不高空间复杂性高不高 2．贪心算法的正确性证明不是所有优化问题都具有贪心选择性质，证明贪心选择性质的方法---数学归纳法，可以对算法步数或问题规模进行归纳。例 2 部分装入背包问题 (Fractional Knapsack Problem) 一个旅行者准备随身携带一个背包. 可以放入背包的物品有 n 个, 每个物品的重量和价值分别为 wj, vj. j=1, 2, …, n, 旅行者可以选择物品 i 的全部，也可以选择物品 i 的 xi部分，0≤xi≤1。如果背包的最大重量限制是 c, 怎样选择放入背包的物品以使得背包的价值最大? 输入：c>0, wi>0, vi>0, i=1,…n. 输出： nix cxw xv i n i ii i n i i ,...,2,110 max 1 1 =≤≤ ≤∑ ∑ = = 设计贪心法如下：按照单位重量的价值从高到低对物品排序，尽量装入单位重量价值最高的物品，直到不能装入一个整物品为止，最后根据背包重量极限装入部分物品。通过对步数归纳可以证明部分装入背包问题满足贪心选择性质，且时间为 T(n)=O(nlogn)。一般背包问题不具有贪心选择性质，不能使用贪心法，因为对于某些输入不能得到最优解。0-1 背包问题也不具有贪心选择性质。下面是 0-1 背包问题的描述。 nix cxw xv i n i ii i n i i ,...,2,1,1,0 max 1 1 == ≤∑ ∑ = = 例 3 最优装载 n 个集装箱 1, 2, …, n 装上轮船，集装箱 i 的重量 wi, 轮船装载重量限制为 c，无体积限制。问如何装使得上船的集装箱最多？不妨设 wi≤c. nix cxw x i i n i i n i i ,...,2,11,0 max 1 1 == ≤∑ ∑ = = 贪心法设计：将集装箱按照从轻到重排序，轻者先装。正确性证明：对于任何输入规模 n, 贪心算法得到装载问题的最优解。设贪心法的解为 I 1．n=1, 只有一个集装箱，I={1}就是最优解。 2．假设对于 n-1 个集装箱的输入，贪心法都可以得到最优解。考虑 n 个集装箱的输入N={1, 2, …, n}, 其中w1≤w2≤…≤wn, 由归纳假设，对于N’={2, 3, …, n-1}，c’=c-w1, 贪心法得到最优解 I’. 令 I={1}∪I’，则 I 是关于 N 的最优解。若不然，存在包含 1 的关于 N 的最优解 I*（如果 I*中没有 1，用 1 替换 I*中的第一个元素得到的解也是最优解），且|I*|>|I|；那么 I*-{1} 是 N’的解且 |I*-{1}|>|I-{1}|=|I’| 与 I’的最优性矛盾。复杂性 T(n)=O(nlogn) 装载问题是 0-1 背包问题的特例，即 vi=1, i=1, 2, …,n. 该问题是 O(nlogn)时间可解的，但 0-1 背包问题是 NP 难(NP-hard)的。 3．对于得不到最优解的贪心法的分析工作 z 讨论对于哪些输入贪心选择能够得到最优解---例 4 z 讨论贪心法的解最坏情况下与最优解的误差---例 5 例 4 找零钱问题设有 n 种零钱, 其重量分别为 w1, w2, ... , wn, 价值分别为 v1=1, v2, ... , vn. 若要付的总钱数是 y, 如何付钱使得所付钱的总重最轻? Nx yxv xw i n i ii n i ii ∈ =∑ ∑ = = 1 1 min 实际上是整数规划问题, 使用动态规划算法可以求得最优解。Greedy 算法如下：为了描述的方便, 假设 n n v w v w v w ≥≥≥ ... 2 2 1 1 在使用前 k种零钱总钱数为 y时求得最优解的算法的总重为Fk(y), 贪心法的总重为 Gk(y)，则有如下递推方程。动态规划算法 yw v ywyF xwxvyFyF kkkkk v yx k k k 1 1 11 1111 0 1 )( })({min)( 1 1 =  = +−= ++++   ≤≤ + + + 贪心法 yw v ywyG vyG v ywyG kk k kk 1 1 11 1 1 11 )( )mod()( =  = +  = + + ++ 易见 F1(y)=G1(y). 不难验证 x2 的值越大则 F2(y)的值就越小，从而有 F2(y)=G2(y).下面定理给出了当 k>2 时贪心法是否得到最优解的条件，可以用这个条件判断对哪些输入贪心法能够得到最优解。定理 2 假定Gk(y) = Fk (y), v k+1 > vk 且 v k+1 = p vk－δ, 0 ≤ δ < vk, p∈ Z+, 则以下命题等价. kkk kkkk kk kk pwGw pvFpvG yFyG yGyG ≤+ = = ≤ + ++ ++ + )()4( )()()3( )()()2( )()()1( 1 11 11 1 δ 该定理给出验证 G k+1(y) = F k+1(y)是否成立的条件。计算 Gk(y)的复杂性是 O(k), 与 y 无关。利用条件(4), 只需 O(k)时间就可以作出验证。如果需要对所有 n 种零钱的系统作出验证, 可在 O(n2)时间内完成. 例如零钱系统 v1 = 1, v2 = 5, v3 = 14, v4 = 18, wi = 1, i = 1, 2, 3, 4. 对一切 y 有 G1(y) = F1 (y), G2(y) = F2 (y). v3 = 14 = 3 v2－1, 即 p =3, δ = 1. w3 + G2 (δ) = 1 + G2 (1) = 1 + 1 = 2 p w2 = 3×1 = 3 由(4)式, 有 G3(y) = F3 (y). v4 = 18 = 2 v3－10, 即 p = 2, δ = 10. w4 + G3 (δ) = 1 + G3 (10) = 1 + 2 = 3 p w3 = 2×1 = 2 由(4)式, G4(y) 不是最优解. G4 (p v3) > F4(p v3). 即 G4 (28) = 28 / 18 + 10 / 5 = 1 + 2 = 3 F4 (28) = 28 / 14 = 2. 不难验证对国际上使用的钱币系统通常用 Greedy 算法都可以得到最优解. 例 5 装箱问题有 n 个物体, 长度分别为 a1, a2, ... , an. ai≤1, i=1, 2, …, n. 要把它们装入长为 1 的箱子, 如果只考虑长度的限制, 问至少需要多少只箱子? mjBCBCa m j n i m j ji ,...,2,1,1)()( min 1 1 =≤=∑ ∑ = = ，其中 C(Bj)称为箱子 Bj的装入量，1—C(Bj)称为箱子 Bj的空隙。算法 1 下次适合法 NF 贪心法设计：初始箱子号 j=1, 物体号 i=1, 将物体 i 装入箱子 j, 如果下一个物体能够装入 j，就装，否则装入 j+1 号箱子。误差估计: 设输入为 L, L*是最优算法得到的箱子数, NF(L)是 NF 算法得到的箱子数. ] * )(max[lim)( * L LNFNFr kLk =∞→ = 表示 NF 算法相对于最优算法的误差. 下面计算 r(NF)的上界. 由于任两个相邻箱子的装入量>1, 因此必有 C(B1) + C(B2) + ... + C(Bm) > m-1 2 这说明物体总体积大于m-12 , 因此最优的算法满足 L* > m-1 2 . 从而有 NF(L) = m < 2L* + 1, 令 L*→ ∞得 r(NF) ≤ 2. 另一方面, 可以设计某个输入使得 NF 算法所用的箱子数恰好就是最优算法所用箱子数的 2 倍. 令 44444 344444 21 2N 11-2N 2 12 } 2 1, 2 1, 2 1,..., 2 1, 2 1, 2 1, 2 1{ 个，个N NNN L = 最优装法用 N+1 个箱子，而 NF 算法要 2N 个箱子。这就证明对于任意大的 L* 都存在某个输入使得 2L*－2 ≤ NF(L)，所以 2 * 2*2lim)( * =−≥ ∞→ L LNF L r 综合上述有 r(NF) = 2. 算法 2 首次适合法 FF 对于物体 ak, 依次检查 B1, B2, ... 的空隙, 找到第一个空隙大于等于 ak 的箱子 Bj, 就把 ak 放入. 可以证明对于 FF 算法有 2* 10 17)(2* 10 +≤≤− LLFFL17 即 r(FF) = 1.7. 算法 3 递降首次适合法 FFD 首先排序 L 中的物体使得 a1 ≥ a2 ≥ ... ≥ an. 然后使用 FF 算法. 可以证明对于 FFD 算法有 4* 9 11)(* 9 11 +≤≤ LLFFDL 即 r(FFD) = 1.2. 三、实例例 6 最优二元前缀码问题前缀码：用 0-1 字符串最为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀。前缀码的存储采用二叉树的结构。每个字符作为树叶，每个前缀码对应一条根到树叶的路径。给定 n 个字符 x1, x2, …, xn，每个字符传输概率 f(x1), f(x2), …, f(xn), 使用二进制串对字符编码，设计一个前缀码使得平均传输一个字符的位数达到最小。利用 Huffman 树可以得到最优解。算法 Huffman(C) 1．n←|C|; 2．Q←C; 3．for i←1 to n-1 do 4． z←Allocate-Node(); 5． z.left←Q 中最小元； 6． z.right←Q 中最小元； 7． f[z]←f[x]+f[y] 8． Insert(Q,z); 9．Return Q 时间：T(n)=O(nlogn) 例如 a: 45, b: 13; c: 12; d: 16: e: 9; f: 5, Huffman 树为编码：f---0000, e---0001, d---001, c---010, b—011, a---1 平均传输位数：4*5%+4*9%+3*16%+3*12%+3*13%+1*45%= 2.24 引理 1 设 C 是字符集，∀c∈C, f[c]为频率， x, y∈C, f[x], f[y]频率最小，那么存在最优二元前缀码使得 x, y 的码字等长，且仅在最后一位不同。证明：假定树 T 是任意二元前缀码对应的树，如下修改 T 为 T’，使得 T’中的 x,y 作为最深的兄弟的树叶。设 b,c 是 T 中最深的兄弟树叶对应的字符，不妨设 f[y]≤ f[c], f[x] ≤ f[b]. 将 x 与 b 交换，y 与 c 交换，则 T 与 T’的权之差为 ∑ ∑ ∈ ∈ ≥−=− Ci Ci TT idifidifTBTB 0)(][)(][)'()( ' 其中 dT(i)为 i 在 T 中的层数（i 到根的距离）。引理 2 设 T 是最优解对应的树，∀x,y ∈T, x, y 是树叶兄弟，z 是 x,y 的父亲， z 的频率 f[z]=f[x]+f[y], 令 T’ = T−{x,y}, 则 T’是对应于最优前缀码 C’ =(C−{x,y})∪{z}的树。证明：∀c ∈ C−{x,y}, 有 dT(c) = dT’(c) ⇒ f[c]dT(c) = f[c]dT’(c) 因为 dT(x) = dT(y) = dT’(z) +1 所以有 f[x] dT(x) + f[y] dT(y) = (f[x] + f[y]) (dT’(z) + 1) = f[z]dT’(z ) + (f[x] + f[y]) 从而证明了 B(T) = B(T’) + f[x] + f[y] 如果 T’不是关于 C’的最优树，那么存在 T”使得 B(T”)1，Kruskal 算法得到 n个顶点图 G的最小生成树。证明： 1．n=2, 只有一条边，命题显然为真。 2．假设对于 n 个顶点的图算法正确，考虑 n+1 个顶点的图 G , G 中最小权边 e={i,j}。从 G 中短接 i 和 j，得到图 G’为 n 个顶点的图。根据归纳假设，由算法存在一棵 G’的最小生成树 T’。令 T=T’∪{e}, 则 T 是关于 G 的最小生成树。若不然，存在一棵 G 的最小生成树 T*，W(T*)

                    本文档为【四、贪心算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

四、贪心算法

你可能还喜欢