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

活动选择问题 算法 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 <sifi>|1<==n} Y有穷的值集合—相容活动集A的规模{1,…n} f(×)目标函数—max|A G约束条件集合一s>=f或5>=f(1<=<j<=n) 个组合优化问题的解是对变量集Ⅹ的一组赋值g:X >Y,并且在满足G中约束条件的前提下使得目标函 数f(×)取得最大(小)值

贪心法适用范围 „ 满足优化原则 的组合优化问题 „ 若满足贪心选择性质 得最优解，否则得近似解 „ 什么是组合优化问题 „ X 有穷的变量集合 —活动集合S = {<si,fi>|1<=i<=n} „ Y 有穷的值集合 —相容活动集 A的规模{1, …,n} „ f(x) 目标函数 —max |A| „ G 约束条件集合 —si>=fj 或sj>=fi (1<=i<j<=n) „ 一个组合优化问题的解是对变量集 X的一组赋值g:X- >Y，并且在满足 G中约束条件的前提下使得目标函 数f(x)取得最大（小）值

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

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