算法——贪心算法II

《算法——贪心算法II》由会员分享，可在线阅读，更多相关《算法——贪心算法II（19页珍藏版）》请在文档大全上搜索。

1、算法设计与分析算法设计与分析2022年6月1日讲授内容：动态规划动态规划II教师：胡学钢胡学钢、吴共庆吴共庆纲要纲要 活动选择问题 背包问题 哈夫曼编码6/1/2022算法设计与分析-贪心算法II2贪心算法贪心算法: : 顶点覆盖顶点覆盖6/1/2022算法设计与分析-贪心算法II3无向图 G=(V, E)的一个顶点覆盖顶点覆盖为一个子集V V ，使得如果 (u, v) E, 那么 u V 或者v V, 或者两者都是. 顶点覆盖的集合包括所有的边. 一个顶点覆盖的大小大小就是这个覆盖着定点的数目。顶顶点覆盖问题点覆盖问题就是找到一个图纸最小的顶点覆盖。贪婪试探贪婪试探: 每次覆盖尽量多的边 (

2、有最大度的边) 然后删除所有被覆盖的边。贪婪试探并不能总是找到最优解贪婪试探并不能总是找到最优解! 顶点覆盖问题是 NP完全的. 活动活动选择问题选择问题: 给定一个集合 S = 1, 2, , n n 个计划的活动,对每个活动 i，开始时间为 si 结束时间为 fi, 选择出相互兼容的活动最大集合. 如果被选中,活动 i 在半开放的区间 si, fi)中进行. 活动 i 和j 兼容兼容 如果 si, fi) 和 sj, fj) 不重叠 (i.e., si fj or sj fi).6/1/2022算法设计与分析-贪心算法II4活动选择问题活动选择问题活动选择活动选择问题的分析问题的分析6/1

3、/2022算法设计与分析-贪心算法II5活动选择活动选择问题问题- -一个递归解一个递归解6/1/2022算法设计与分析-贪心算法II66/1/2022算法设计与分析-贪心算法II7活动活动选择选择- -贪心选择贪心选择活动选择问题活动选择问题- -递归贪心算法递归贪心算法6/1/2022算法设计与分析-贪心算法II8初始调用RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)Greedy-Activity-Selector(s,f)/* Assume f1 f2 fn. */ 1. n lengths;2. A 1;3. j 1;4. for i 2 to n5.

4、if si fj6. A A i;7. j i;8. return A.如果不考虑排序，算法的时间复杂度为: O(n)6/1/2022算法设计与分析-贪心算法II9活动选择问题活动选择问题- -迭代贪心迭代贪心算法算法 什么时候使用贪婪算法? 贪心选择贪心选择特性特性: A全局的最优解可以通过局部的最优（贪婪）选择得到. 动态规划需要检查子问题的解。 最优子结构最优子结构: 问题的最优解包含了其子问题的最优解. 例如, 如果 A 是S的最优解, 那么 A = A - 1 是 S = i S: si f1的最优解. 贪心算法 (试探) 并不能总是得到最优解. 谈论算法和动态规划 (DP)对比 相