贪心法 刘培 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)取得最大（小）值
贪心法适用范围 优化原则 个最优决策序列的任何子序列本身一定是 相对于子序列的初始和结束状态的最优的决 策序列 例:从北京经过广州到海南的最短距离,肯定包 括北京到广州的最短距离,以及广州到海南的最 短距离 ■活动选择问题
贪心法适用范围 优化原则 一个最优决策序列的任何子序列本身一定是 相对于子序列的初始和结束状态的最优的决 策序列 例：从北京经过广州到海南的最短距离，肯定包 括北京到广州的最短距离，以及广州到海南的最 短距离 活动选择问题