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

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

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

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

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

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

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

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

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

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

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

活动选择问题 n活动 S={1,2,,n是n个活动的集合,活动共用同一资 源,同一时间只有一个活动使用。活动起始时 间s1,终止时间f,S≤f,表示为x=[s,f1 相容活动 口活动是相容的,若S2或S

活动选择问题 ◼ 活动  S={1,2,…,n}是n个活动的集合，活动共用同一资 源，同一时间只有一个活动使用。活动 i有起始时 间 si，终止时间 f i，si f i，表示为xi=[si， f i ] ◼ 相容活动  活动i和j是相容的，若 sjf i 或 sif j 6 si fi sj fj si sj fi fj

活动选择问题 问题定义 口输入:S={1,2,…,n},X=[s,印],1≤i≤n a输出:S的最大相容集合 贪心思想 口为了选择更多活动,每次选择f最小的活动

活动选择问题 ◼ 问题定义  输入：S={1, 2, …, n}，xi=[si， f i ]，1  i  n  输出：S的最大相容集合 ◼ 贪心思想  为了选择更多活动，每次选择 f i 最小的活动 7

活动选择问题 S按结束时间排序,f1f2≤ Greedy-Activity-Selector(s n= length(s) A={1}; T(n)=0(n+e(nlogn for i=2 to n do e(nlogn ifs≥ f then A=A∪{; return a

活动选择问题 8 S按结束时间排序，f 1 f 2 ….fn Greedy-Activity-Selector(S, F) n = length(S); A = {1}; j = 1; for i=2 to n do if si  f j then A = A∪{i}； j=i； return A T(n) = (n)+(nlogn) = (nlogn)

活动选择问题 最优子结构性质 口设活动S={1,2,…,m已按结束时间递增排序,即 f12≤…fn,设A是包括活动1的最优解,则 A=A-{1}是S’={i∈S|s≥f}的最优解 口证明 >显然A中的活动是相容的,只需证A是最大的。 若不然,假设B是最大的,且B|>|Al 那么B={1UB是最优解,但B=1+B>1+A|=|A >这与A是最大的(最优解)矛盾。 问题的最优解包含子问题的最优解

活动选择问题 ◼ 最优子结构性质  设活动S={1, 2, …, n}已按结束时间递增排序，即 f1f2….fn，设A是包括活动 1 的最优解，则 A’=A-{1} 是 S’={iS|sif1 }的最优解。  证明： ➢ 显然A’中的活动是相容的，只需证A’是最大的。 ➢ 若不然，假设B’是最大的，且|B’| > |A’|。 ➢ 那么B={1}∪B’是最优解，但|B| =1+|B’| > 1+|A’|=|A| ➢ 这与A是最大的（最优解）矛盾。 9 问题的最优解包含子问题的最优解

活动选择问题 贪心选择性 口设活动S={1,2,…,n已按结束时间递增排序,即 f1f2≤…fn。每次选结束时间最小的相容活动, 可得最优解A 口证明: 设贪心最优解A也按结束时间递增排序,设其第一个 活动为k,第二个活动为j 若k=1,则成立 >若k≠1,由于A中活动相容,有f≤S1,由于1≤f, 因此,可以用活动1代替活动k 10

活动选择问题 ◼ 贪心选择性  设活动S={1, 2, …, n}已按结束时间递增排序，即 f1f2….fn。每次选结束时间最小的相容活动， 可得最优解A。  证明： ➢ 设贪心最优解A 也按结束时间递增排序，设其第一个 活动为 k，第二个活动为j ➢ 若k=1，则成立 ➢ 若k1，由于 A 中活动相容，有fk  sj，由于f1  fk， 因此，可以用活动1 代替活动k 10