算法——贪心算法II.pptx

算法设计与分析
2018年9月3日
讲授内容:动态规划II教师:胡学钢、吴共庆
纲要
活动选择问题
背包问题
哈夫曼编码
9/3/2018
算法设计与分析-贪心算法II
2
贪心算法: 顶点覆盖
9/3/2018
算法设计与分析-贪心算法II
3
无向图 G=(V, E)的一个顶点覆盖为一个子集V‘ V ,使得如果(u, v)  E, 那么 u  V’或者v  V‘, 或者两者都是.
顶点覆盖的集合包括所有的边.
一个顶点覆盖的大小就是这个覆盖着定点的数目。
顶点覆盖问题就是找到一个图纸最小的顶点覆盖。
贪婪试探: 每次覆盖尽量多的边(有最大度的边) 然后删除所有被覆盖的边。
贪婪试探并不能总是找到最优解!
顶点覆盖问题是 NP完全的.
活动选择问题: 给定一个集合 S = {1, 2, …, n} n 个计划的活动,对每个活动 i,开始时间为 si 结束时间为 fi, 选择出相互兼容的活动最大集合.
如果被选中,活动 i 在半开放的区间[si, fi)中进行.
活动 i 和j 兼容如果[si, fi) 和[sj, fj) 不重叠(., si  fj or sj  fi).
9/3/2018
算法设计与分析-贪心算法II
4
活动选择问题
活动选择问题的分析
9/3/2018
算法设计与分析-贪心算法II
5
活动选择问题-一个递归解
9/3/2018
算法设计与分析-贪心算法II
6
9/3/2018
算法设计与分析-贪心算法II
7
活动选择-贪心选择
活动选择问题-递归贪心算法
9/3/2018
算法设计与分析-贪心算法II
8
初始调用RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)
Greedy-Activity-Selector(s,f)
/* Assume f1  f2 … fn. */
1. n  length[s];
2. A {1};
3. j  1;
4. for i  2 to n
5. if si  fj
6. A  A {i};
7. j  i;
8. return A.
如果不考虑排序,算法的时间复杂度为: O(n)
9/3/2018
算法设计与分析-贪心算法II
9
活动选择问题-迭代贪心算法
什么时候使用贪婪算法?
贪心选择特性: A全局的最优解可以通过局部的最优(贪婪)选择得到.
动态规划需要检查子问题的解。
最优子结构: 问题的最优解包含了其子问题的最优解.
例如, 如果 A 是S的最优解, 那么 A‘= A - {1} 是 S' = {i  S: si  f1}的最优解.
贪心算法(试探) 并不能总是得到最优解.
谈论算法和动态规划(DP)对比
相同: 最优子结构
差别: 贪婪选择特性
如果贪婪算法不是最优的,可以使用DP 。
9/3/2018
算法设计与分析-贪心算法II
10
贪心策略中的要素