第5章-贪心算法.pdf
文本预览下载声明
算法设计与分析 第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 1f 2…f n ,从前向后挑选
以上策略中的挑选都要注意满足相容性条件
武汉理工大学 信息工程学院
算法设计与分析 第5章
策略1的反例 开始早的优先
S={1,2,3} ,s =0, f =20, s =2, f =5, s =8, f
显示全部