概要 Lecture 4 ·动态规划回顾 Greedy algorithm ·活动问题选择分析 ·贪婪算法要点 清华大学 ·拟阵概念 宋斌恒 动态规划要点回顾 最优子结构的关键步骤 ·最优子结构 1.关键过程(点)选择,例如 生产安排 装配问题选择经过的装配站 矩阵链乘 乘法问题选择括号分界线 -LCS LCS问题如何确定子问题 Print Neatly Print neatly问题选择在什么地方分行做完选 最优二叉搜索树 择后留下若干子问题 续 Greedy Algorithm 2.最优选择成立假设:只需要假设其中的关 Sample1.活动选择问题 键点假设成立即可,如何选择、先不管 Several competing activities that require 3.子问题空间:在上述选择决定后,留下什 exclusive use of common resources(Same 么样的子问题才能保证上述问题的选择是 place at a fixed period of time), with the goal 最优的 of selecting a maximum-size set of mutually compatible activities that wish to use a 4.证明你的方案是最优的,方法:" Cut-and resource(a period of time in the place)1 Lecture 4. Greedy Algorithm 清华大学 宋斌恒 清华大学 软件学院 宋斌恒 2 概要 •动态规划回顾 •活动问题选择分析 •贪婪算法要点 •拟阵概念 清华大学 软件学院 宋斌恒 3 动态规划要点回顾 •最优子结构 –生产安排 –矩阵链乘 –LCS –Print Neatly –最优二叉搜索树 清华大学 软件学院 宋斌恒 4 最优子结构的关键步骤 1. 关键过程（点）选择，例如 – 装配问题选择经过的装配站 – 乘法问题选择括号分界线 – LCS问题如何确定子问题 – Print neatly 问题选择在什么地方分行做完选 择后留下若干子问题 清华大学 软件学院 宋斌恒 5 续 2. 最优选择成立假设：只需要假设其中的关 键点假设成立即可，如何选择、先不管 3. 子问题空间：在上述选择决定后，留下什 么样的子问题才能保证上述问题的选择是 最优的 4. 证明你的方案是最优的，方法：“Cut-and￾paste” 清华大学 软件学院 宋斌恒 6 Greedy Algorithm •Sample 1. 活动选择问题 –Several competing activities that require exclusive use of common resources (Same place at a fixed period of time), with the goal is of selecting a maximum -size set of mutually compatible activities that wish to use a resource (a period of time in the place)