东南大学：《数据结构》课程教学资源（PPT课件讲稿）贪心算法

贪心算法 东南大学计算机学院方效林

东南大学计算机学院 方效林 贪心算法

本章内容 贪心算法要素 ■活动选择问题 哈夫曼编码问题 最小生成树问题 单源最短路径问题

本章内容 ◼ 贪心算法要素 ◼ 活动选择问题 ◼ 哈夫曼编码问题 ◼ 最小生成树问题 ◼ 单源最短路径问题 2

贪心算法要素 贪心算法的基本思想 口求解最优化问题的算法包含一系列步骤 每一步都有一组选择 n作出在当前看来最好的选择 口希望通过作出局部最优选择达到全局最优选择 贪心算法不一定总产生最优解 口贪心算法是否产生优化解,需严格证明 贪心算法产生最优解的条件 口最优子结构 贪心选择性

贪心算法要素 ◼ 贪心算法的基本思想  求解最优化问题的算法包含一系列步骤  每一步都有一组选择  作出在当前看来最好的选择  希望通过作出局部最优选择达到全局最优选择  贪心算法不一定总产生最优解  贪心算法是否产生优化解，需严格证明 ◼ 贪心算法产生最优解的条件  最优子结构  贪心选择性 3

贪心算法要素 最优子结构 当一个问题的最优解包含子问题的最优解时,称这 个问题具有最优子结构 贪心选择性 当一个问题的全局最优解可以通过局部最优解得到 称这个问题具有贪心选择性 口证明思路 假定首选元素不是贪心选择所要的元素,证明将首元 素替换成贪心选择所需元素,依然得到最优解 数学归纳法证明每一步均可通过贪心选择得到最优解

贪心算法要素 ◼ 最优子结构  当一个问题的最优解包含子问题的最优解时，称这 个问题具有最优子结构 ◼ 贪心选择性  当一个问题的全局最优解可以通过局部最优解得到 ，称这个问题具有贪心选择性  证明思路： ➢ 假定首选元素不是贪心选择所要的元素，证明将首元 素替换成贪心选择所需元素，依然得到最优解 ➢ 数学归纳法证明每一步均可通过贪心选择得到最优解 4

贪心算法要素 n动态规划方法可用的条件 口最优子结构 a子问题重叠性 贪心算法产生最优解的条件 口最优子结构 贪心选择性 适用贪心算法时,动态规划可能不适用 适用动态规划时,贪心算法可能不适用

贪心算法要素 ◼ 动态规划方法可用的条件  最优子结构  子问题重叠性 ◼ 贪心算法产生最优解的条件  最优子结构  贪心选择性 ◼ 适用贪心算法时，动态规划可能不适用 ◼ 适用动态规划时，贪心算法可能不适用 5