文档详情

第5章-贪心算法.pdf

发布:2018-05-13约4.86万字共96页下载文档
文本预览下载声明
算法设计与分析 第5章 Algorithms Design and Analysis 算法设计与分析 Advanced Design and Analysis Techniques 高级、先进的设计与分析方法、技术 第5章 贪心法 Greedy Approach 武汉理工大学 信息工程学院 算法设计与分析 第5章 Greedy Approach  贪心法的设计思想  贪心法的正确性证明  对贪心法得不到最优解情况的处理  贪心法的典型应用  最优前缀码  最小生成树  单源最短路径 武汉理工大学 信息工程学院 算法设计与分析 第5章 贪心法的设计思想  举例:活动选择问题 输入:S ={1, 2, … , n}为n 项活动的集合,s , f 分别为活动i i i 的开始和结束时间, 活动i 与j 相容 s f 或 s f . i j j i 求:最大的两两相容的活动集A 实例 i 1 2 3 4 5 6 7 8 9 10 s 1 3 2 5 4 5 6 8 8 2 i f i 4 5 6 7 9 9 10 11 12 13 解:{1,4,8} 武汉理工大学 信息工程学院 算法设计与分析 第5章 贪心算法 i 1 2 3 4 5 6 7 8 9 10 s 1 3 2 5 4 5 6 8 8 2 i f i 4 5 6 7 9 9 10 11 12 13 挑选过程是多步判断,每步依据某种“短视”的策略进行活 动选择,选择时注意满足相容性条件。 策略1:开始时间早的优先 排序使得 s s …s ,从前向后挑选 1 2 n 策略2 :占用时间少的优先 排序使得f -s f -s  …f -s ,从前向后挑选 1 1 2 2 n n 策略3 :结束早的优先 排序使得f 1f 2…f n ,从前向后挑选 以上策略中的挑选都要注意满足相容性条件 武汉理工大学 信息工程学院 算法设计与分析 第5章  策略1的反例 开始早的优先 S={1,2,3} ,s =0, f =20, s =2, f =5, s =8, f
显示全部
相似文档