四、贪心算法.pdf

2．3 贪心法 (Greedy Approach) 一、基本思想 适用问题：组合优化问题，适合优化原则。 设计方法：多步判断。在每步判断时在满足约束条件的情况下根据某个局部 的优化测度(可能是目标函数,也可能不是)考虑部分解中一个变量的选择。 使用贪心法要解决的问题: 是否可以得到最优解? 不能得到最优解, 解与 最优解的误差估计。 例 1 活动选择问题 S ={1, 2, …, n}为 n 项活动的集合。si, fi 分别为活动 i 的开始和结束时间。活 动 i 与j 相容当且仅当 s ≥ f , 或 f ≥ s , 求最大的两两相容的活动集。 i j i j 解：按照结束时间的递增顺序将活动排列为 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 项活动 i = 1, i , …, i , 那么存在最 1 2 k 优解 A 包含 i = 1, i , …, i 1 2 k 证明：对 k 归纳。 k=1, 设 S = {1, 2, …, n}是活动集，活动按截止时间递增顺序排序，则存在最 优解含有活动 1。任取最优解 A, A 中的活动按照截止时间递增的顺序排列。如 果 A 的第一个活动为j ，j ≠ 1, 令 A’= (A−{j})∪{1}, 由于f ≤ f , A’也是最优解，且含有 1. 1 j 假设命题对 k 为真。算法执行到第 k 步, 选择了活动 i = 1, i , …, i , 根据归 1 2 k 纳假设存在最优解 A 包含 i = 1, i , …, i , A 中剩下的活动选自集合 S’ = {i | i ∈ S, 1 2 k s ≥ f }。且B=A-{ i , i , …, i }是 S’的最优解。若不然，S’的最优解为B’ ，B’ 的 i k 1 2 k 活动比 B 多，那么 B’∪{1, i , …, i }是 S 的最优解，且比 A 的活动多，与 A 的最 2 k 优性矛盾。 根据归纳基础，存在 S’的最优解B 含有 S’中的第一个活动，设为ik+1, 则 {i , i ,..., i }∪B {i , i ,...i ,i }∪(B −{i }) 1 2