第4章：贪心算法 (Greedy Algorithm)
第4章：贪心算法 （Greedy Algorithm）
知识要点 ⑧理解贪心算法的概念和基本要素 Φ最优子结构性质和贪心选择性质 Φ理解贪心算法与动态规划算法的差异 3贪心设计策略的典型例子 Φ活动安排问题 Φ最优装载问题 Φ单源最短路径 Φ多机调度问题
知识要点 理解贪心算法的概念和基本要素 最优子结构性质和贪心选择性质 理解贪心算法与动态规划算法的差异 贪心设计策略的典型例子 活动安排问题 最优装载问题 单源最短路径 多机调度问题
贪心算法的例子 @3 找零钱问题 假设有4种硬币，面值分别为：二角五分、一角、五分和一分 现在要找给顾客六角三分钱，如何找使得给出的硬币个数最少？ @3 问题的求解 Φ正解：选择2个两角五分的硬币、1个一角的硬币、3个一分的 硬币。和其它找法相比，所拿出的硬币个数最少。 Φ求解过程 首先选出1个面值不超过六角三分的最大硬币，即两角五分 然后从六角三分中减去两角五分，剩下三角八分 再选出1个面值不超过三角八分的最大硬币 即又一个两角五分。如此一直做下去.… 这里用到的方法就是贪心算法
贪心算法的例子 找零钱问题 假设有4种硬币，面值分别为：二角五分、一角、五分和一分 现在要找给顾客六角三分钱，如何找使得给出的硬币个数最少？ 问题的求解 正解：选择2个两角五分的硬币、1个一角的硬币、3个一分的 硬币。和其它找法相比，所拿出的硬币个数最少。 求解过程 • 首先选出1个面值不超过六角三分的最大硬币，即两角五分 • 然后从六角三分中减去两角五分，剩下三角八分 • 再选出1个面值不超过三角八分的最大硬币 • 即又一个两角五分。如此一直做下去…… • 这里用到的方法就是贪心算法
贪心算法的例子 3 找零钱问题 在这个例子中，找硬币算法得到的结果是整体最优解 ·问题本身具有最优子结构性质，可以用动态规划算法求解 Φ用贪心算法更简单、更直接、且解题效率更高分 R 贪心算法不能保证全局最优 找硬币问题和硬币面值的特殊性有关 如果将硬币面值改为：一分、五分和一角一分， 假设要找给顾客的是一角五分 Φ利用贪心算法，将找给顾客1个一角一分的硬币和4个一分硬币 Φ显然，3个五分硬币是最优的解法
贪心算法的例子 找零钱问题 在这个例子中，找硬币算法得到的结果是整体最优解 问题本身具有最优子结构性质，可以用动态规划算法求解 用贪心算法更简单、更直接、且解题效率更高分 贪心算法不能保证全局最优 找硬币问题和硬币面值的特殊性有关 如果将硬币面值改为：一分、五分和一角一分， 假设要找给顾客的是一角五分 利用贪心算法，将找给顾客1个一角一分的硬币和4个一分硬币 显然，3个五分硬币是最优的解法
贪心算法的基本思想 R 贪心算法的基本思想 Φ优化问题的算法往往包含一系列步骤，每一步都有一组选择 Φ贪心算法在每一步选择中都采取在当前状态下最优的选择 目的是希望由此导出的果是最优的 简言之：贪心算法在求解问题时并不着眼于整体最优 它所作出的选择仅仅是当前看来是最优的 Φ贪心算法能否得到整体最优解？…具体问题，具体分析 R 贪心算法在有最优子结构的问题中尤为有效 Φ 最优子结构的意思是：局部最优解能决定全局最优解 。问题能够分解成子问题来解决 子问题的最优解能递推到最终问题的最优解
贪心算法的基本思想 贪心算法的基本思想 优化问题的算法往往包含一系列步骤，每一步都有一组选择 贪心算法在每一步选择中都采取在当前状态下最优的选择 • 目的是希望由此导出的果是最优的 简言之：贪心算法在求解问题时并不着眼于整体最优 • 它所作出的选择仅仅是当前看来是最优的 贪心算法能否得到整体最优解？……具体问题，具体分析 贪心算法在有最优子结构的问题中尤为有效 最优子结构的意思是：局部最优解能决定全局最优解 • 问题能够分解成子问题来解决 • 子问题的最优解能递推到最终问题的最优解
贪心算法与动态规划的区别 @R 动态规划算法 Φ每一步的最优解是由上一步的局部最优解进行选择得到的 因此需要保存（之前求解的)所有子问题的最优解备查 3 贪心算法 贪心策略：下一步的最优解是由上一步的最优解推导得到的 当前最优解包含上一步的最优解，之前的最优解则不作保留 因此在贪心算法中作出的每步决策都无法改变（不能回退） 3 二者关系 贪心算法本质上是一种（更快的） 动态规划算法 贪心法正确的条件：每一步的最优解一定包含上一步的最优解 如果可以证明：在递归求解的每一步，按贪心选择策略选出的 局部最优解，最终可导致全局最优解，则二者是等价的
贪心算法与动态规划的区别 动态规划算法 每一步的最优解是由上一步的局部最优解进行选择得到的 因此需要保存（之前求解的）所有子问题的最优解备查 贪心算法 贪心策略：下一步的最优解是由上一步的最优解推导得到的 当前最优解包含上一步的最优解，之前的最优解则不作保留 因此在贪心算法中作出的每步决策都无法改变（不能回退） 二者关系 贪心算法本质上是一种（更快的）动态规划算法 贪心法正确的条件：每一步的最优解一定包含上一步的最优解 如果可以证明：在递归求解的每一步，按贪心选择策略选出的 局部最优解，最终可导致全局最优解，则二者是等价的
贪心算法的基本思想 C8 需要再次强调的是：贪心算法得到的结果不能保证全局最优 虽然贪心算法不能对所有问题都得到全局最优解 但对许多问题它能产生整体最优解 。1 如单源最短路径和最小生成树问题等 在另一些情况下，贪心算法的结果是最优解的良好近似 在科研和工程实践中被广泛应用（在学习和实践中总结规律） 解空间 10 全局最优解 8 局部最优解 2 解1解2 解3 解4 解5 解6解7 解8 解9解10
贪心算法的基本思想 需要再次强调的是：贪心算法得到的结果不能保证全局最优 虽然贪心算法不能对所有问题都得到全局最优解 • 但对许多问题它能产生整体最优解 • 如单源最短路径和最小生成树问题等 在另一些情况下，贪心算法的结果是最优解的良好近似 在科研和工程实践中被广泛应用（在学习和实践中总结规律） 0 2 4 6 8 10 解空间 解1 解2 解3 解4 解5 解6 解7 解8 解9 解10 局部最优解 全局最优解
4.1活动安排问题 Activity-Selection Problem)
4.1 活动安排问题 （ Activity-Selection Problem）
活动安排问题 0R 问题定义 Φ设：有n个活动的集合E={1,2,.,n} Φ其中：每个活动都要求竞争使用同一资源 (如演讲会场等)， 而在同一时间内只有一个活动能使用这一资源 每个活动1都有一个请求使用该资源的起始时间S: 每个活动i都有一个使用资源的结束时间f,且s,<f: 如果选择了活动i,则它在半开时间区间[s,f)内占用资源 若区间[S,f)与S,f)不相交，则称活动i与活动是相容的 也就是说，当S;≥f或S≥f时，活动i与活动j相容 活动安排问题就是要在所给的活动集合中，选出最大的相容活 动子集合，即使得尽可能多的活动能兼容地使用公共资源
活动安排问题 问题定义 设：有n个活动的集合E={1,2,…,n} 其中：每个活动都要求竞争使用同一资源（如演讲会场等）， 而在同一时间内只有一个活动能使用这一资源 • 每个活动 i 都有一个请求使用该资源的起始时间 si • 每个活动 i 都有一个使用资源的结束时间 fi，且 si < fi • 如果选择了活动 i，则它在半开时间区间[si , fi)内占用资源 • 若区间[si , fi )与[sj , fj )不相交，则称活动i与活动j是相容的 • 也就是说，当 si ≥ fj 或 sj≥fi 时，活动i与活动j相容 活动安排问题就是要在所给的活动集合中，选出最大的相容活 动子集合，即使得尽可能多的活动能兼容地使用公共资源
求解活动安排问题 例：设待安排的11个活动如下： i 1 2 3 4 5 6 7 8 9 10 11 S[i] 0 1 2 3 3 5 5 6 8 8 12 Fti] 6 4 13 5 8 7 9 10 11 12 14 按开始时间非减序排序： 01234567891011121314 1 2 3 4 5 6 7 8 9 10
求解活动安排问题 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 3 4 5 6 7 8 9 10 11 例：设待安排的11个活动如下： i 1 2 3 4 5 6 7 8 9 10 11 S[i] 0 1 2 3 3 5 5 6 8 8 12 F[i] 6 4 13 5 8 7 9 10 11 12 14 按开始时间非减序排序：