清华大学出版社 TSINGHUA UNIVERSITY PRESS 第4章贪心算法
1 第4章 贪心算法
清华大学出版社 TSINGHUA UNIVERSITY PRESS 第4章贪心算法 顾名思义,贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑,它所作出的 选择只是在某种意乂上的局部最伉选择。当然,希望 贪心算法得到的最终结果也是整体最优的。虽然贪心 算法不能对所有问题都得到整体最优解,但对许多问 题它能产生整体最优解。如单源最短路经问题,最小 生成树问题等。在一些情况下,即使贪心算法不能得 到整体最优解,其最终结果却是最优解的很好近似。 2
2 第4章 贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的 选择只是在某种意义上的局部最优选择。当然，希望 贪心算法得到的最终结果也是整体最优的。虽然贪心 算法不能对所有问题都得到整体最优解，但对许多问 题它能产生整体最优解。如单源最短路经问题，最小 生成树问题等。在一些情况下，即使贪心算法不能得 到整体最优解，其最终结果却是最优解的很好近似
清华大学出版社 TSINGHUA UNIVERSITY PRESS 第4章贪心算法 本章主要知识点: 4.1活动安排问题 ·4.2贪心算法的基本要素 ·4.3最优装载 4.4哈夫曼编码 ·4.5单源最短路径 4.6最小生成树 ·4.7多机调度问题 ·4.8贪心算法的理论基础
3 第4章 贪心算法 本章主要知识点： • 4.1 活动安排问题 • 4.2 贪心算法的基本要素 • 4.3 最优装载 • 4.4 哈夫曼编码 • 4.5 单源最短路径 • 4.6 最小生成树 • 4.7 多机调度问题 • 4.8 贪心算法的理论基础
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 活动安排问题就是要在所给的活动集合中选出最 大的相容活动子集合,是可以用贪心算法有效求解的 很好例子。该问题要求高效地安排一系列争用某一公 共资源的活动。贪心算法提供了一个简单、漂亮的方 法使得尽可能多的活动能兼容地使用公共资源。 4
4 4.1 活动安排问题 活动安排问题就是要在所给的活动集合中选出最 大的相容活动子集合，是可以用贪心算法有效求解的 很好例子。该问题要求高效地安排一系列争用某一公 共资源的活动。贪心算法提供了一个简单、漂亮的方 法使得尽可能多的活动能兼容地使用公共资源
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 设有n个活动的集合E={1,2…,n,其中每个活动都要 求使用同一资源,如演讲会场等,而在同一时间内只有 个活动能使用这一资源。每个活动都有一个要求使用该资 源的起始时间si和一个结束时间f,且si<fi。如果选择了活 动,则它在半开时间区间[sf内占用资源。若区间[si,f) 与区间[Sj,f)不相交,则称活动与活动是相容的。也就是 说,当sif或jf时,活动与活动相容
5 4.1 活动安排问题 设有n个活动的集合E={1,2,…,n}，其中每个活动都要 求使用同一资源，如演讲会场等，而在同一时间内只有一 个活动能使用这一资源。每个活动i都有一个要求使用该资 源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活 动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi) 与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是 说，当si≥fj或sj≥fi时，活动i与活动j相容
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 在下面所给出的解活动安排问题的贪心算法 greedySelector public static int greedySelector(int [s, int[ f, boolean aD) int n=s length-1 all-true for(int 1=2; K=fDi 束时间存储于数组s和f all-true 中且按结束时间的非减 序排列 count++ else ai]=false return count
6 4.1 活动安排问题 在下面所给出的解活动安排问题的贪心算法greedySelector : • public static int greedySelector(int [] s, int [] f, boolean a[]) • { • int n=s.length-1; • a[1]=true; • int j=1; • int count=1; • for (int i=2;i=f[j]) { • a[i]=true; • j=i; • count++; • } • else a[i]=false; • } • return count; • } 各活动的起始时间和结 束时间存储于数组s和f 中且按结束时间的非减 序排列
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 由于输入的活动以其完成时间的非减序排列,所 以算法 greedySelector每次总是选择具有最早完成 时间的和容活动加入集合A中。直观上,按这种方法 选择相容活动为未安排活动留下尽可能多的时间。也 就是说,该算法的贪心选择的意义是使剩余的可安排 时间段极大化,以便安排尽可能多的相容活动 算法 greedySelector的效率极高。当输入的活 动已按结束时间的非减序排列,算法只需O(n)的时间 安排n个活动,使最多的活动能相容地使用公共资源。 如果所给出的活动未按非减序排列,可以用 o(nlogn) 的时间重排
7 4.1 活动安排问题 由于输入的活动以其完成时间的非减序排列，所 以算法greedySelector每次总是选择具有最早完成 时间的相容活动加入集合A中。直观上，按这种方法 选择相容活动为未安排活动留下尽可能多的时间。也 就是说，该算法的贪心选择的意义是使剩余的可安排 时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活 动已按结束时间的非减序排列，算法只需O(n)的时间 安排n个活动，使最多的活动能相容地使用公共资源。 如果所给出的活动未按非减序排列，可以用O(nlogn) 的时间重排
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 例:设待安排的11个活动的开始时间和结束时间按结 束时间的非减序排列如下 i123|4 67891011 Si1305 538 5688212 f4567 91011121314
8 4.1 活动安排问题 例：设待安排的11个活动的开始时间和结束时间按结 束时间的非减序排列如下： i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 算法 greedySelector的 计算过程如左图所示。 图中每行相应于算法的 次迭代。阴影长条表 示的活动是已选入集合A 的活动,而空白长条表 示的活动是当前正在检 查相容性的活动 01234567891011121314
9 4.1 活动安排问题 算法greedySelector 的 计算过程如左图所示。 图中每行相应于算法的 一次迭代。阴影长条表 示的活动是已选入集合A 的活动，而空白长条表 示的活动是当前正在检 查相容性的活动
清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 若被检查的活动的开始时间Si小于最近选择的活动j 的结束时间f,则不选择活动i,否则选择活动i加入集 合A中。 贪心算法并不总能求得问题的整体最优解。但对 于活动安排问题,贪心算法 greedy Selecto却总能求 得的整体最优解,即它最终所确定的相容活动集合A的 规模最大。这个结论可以用数学归纳法证明
10 4.1 活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j 的结束时间fi，则不选择活动i，否则选择活动i加入集 合A中。 贪心算法并不总能求得问题的整体最优解。但对 于活动安排问题，贪心算法greedySelector却总能求 得的整体最优解，即它最终所确定的相容活动集合A的 规模最大。这个结论可以用数学归纳法证明