北京大学：《数据结构与算法》课程教学资源（实习课件PPT）贪心法

贪心法 刘培 liupei@pku.edu.cn

贪心法 刘 培 liupei@pku.edu.cn

Outline 引入:活动选择问题 什么是贪心法 贪心法的适用范围 贪心法证明 几道习题

Outline „ 引入：活动选择问题 „ 什么是贪心法 „ 贪心法的适用范围 „ 贪心法证明 „ 几道习题

活动选择问题 S={1,2,n}为n项活动的集合 s和f分别表示活动开始和结束时间 (1=f或 SJ>=fi 求两两相容的最大活动集

活动选择问题 „ S={1,2, …,n} 为 n项活动的集合 „ si 和fi分别表示活动i开始和结束时间 (1=fj 或 sj>=fi „ 求两两相容的最大活动集

活动选择问题 思路: 按照结束时间递增序列将活动排序,使得 f<=f2<=.<=fn 满足相容关系后,按照标号从小到大选择

活动选择问题 „ 思路： „ 按照结束时间递增序列将活动排序，使得 f 1<=f 2<= …<=f n „ 满足相容关系后，按照标号从小到大选择 1 2 3 4 5 6

活动选择问题

活动选择问题 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

活动选择问题 算法 Greedy select a 1.n+lengths 2.A-{1 3.产1; 4 for i2 to n 567 dos≥ then a←A∪{ 7←G 8. return A

活动选择问题 算法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

贪心法定义 a greedy algorithm always makes the choice that looks best at the moment That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution 《算法导 论》 贪心法在每一步都做出一个局部最优的 选择,以期在总体上仍然达到最优

贪心法定义 „ A greedy algorithm always makes the choice that looks best at the moment. That is , it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. --《算法导 论》 „ 贪心法在每一步都做出一个局部最优的 选择，以期在总体上仍然达到最优

贪心法适用范围 考虑这样一类问题: 会有一个最优的目标一最大/最小 求最大活动集 会有一个或者多个约束条件 求两两相容的最大活动集 n需要一系列的步骤去完成一多步判断 每步选择一个任务 不需要考虑之前或者之后的步骤一贪心选择 ■按完成时间排序,从左向右扫描,不回溯

贪心法适用范围 „ 考虑这样一类问题： „ 会有一个最优的目标 —最大 /最小 „ 求最大活动集 „ 会有一个或者多个约束条件 „ 求两两相容的最大活动集 „ 需要一系列的步骤去完成 —多步判断 „ 每步选择一个任务 „ 不需要考虑之前或者之后的步骤 —贪心选择 „ 按完成时间排序，从左向右扫描，不回溯

贪心法适用范围 ■满足优化原则的组合优化问题 若满足贪心选择性质得最优解,否则得近似解 什么是组合优化问题 Ⅹ有穷的变量集合一活动集合S |1=f或5>=f(1Y,并且在满足G中约束条件的前提下使得目标函 数f(×)取得最大(小)值

贪心法适用范围 „ 满足优化原则 的组合优化问题 „ 若满足贪心选择性质 得最优解，否则得近似解 „ 什么是组合优化问题 „ X 有穷的变量集合 —活动集合S = {|1=fj 或sj>=fi (1Y，并且在满足 G中约束条件的前提下使得目标函 数f(x)取得最大（小）值

贪心法适用范围 优化原则 个最优决策序列的任何子序列本身一定是 相对于子序列的初始和结束状态的最优的决 策序列 例:从北京经过广州到海南的最短距离,肯定包 括北京到广州的最短距离,以及广州到海南的最 短距离 ■活动选择问题

贪心法适用范围 „ 优化原则 „ 一个最优决策序列的任何子序列本身一定是 相对于子序列的初始和结束状态的最优的决 策序列 „ 例：从北京经过广州到海南的最短距离，肯定包 括北京到广州的最短距离，以及广州到海南的最 短距离 „ 活动选择问题