归本程子末军 16贪心算法的步骤 SHANDONG UNIVERSITY OF TECINOLOGY 器会会的合会空会品条 ●优化解的结构分析 ·算法设计 ·算法复杂性分析 ●算法正确性证明 2025年4月3日 16
2025年4月3日 16 1.6 贪心算法的步骤 ⚫优化解的结构分析 ⚫算法设计 ⚫算法复杂性分析 ⚫算法正确性证明
G 归东程子太军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、 哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 2025年4月3日 17
2025年4月3日 17 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题
白东程子太程 2.1问题定义（An activity-arranging problem ANDO INIVERSITY OF TECHNOLOOY 会是3会公☆ ●活动 ■设E=1,2,n是n个活动的集合，各个活动使用同 一个资源，资源在同一时间只能为一个活动使用。 ■每个活动i有起始时间S,终止时间f,S<f ■如果选择了活动i,则它在时间[S,f)内占用资源。 ●相容活动 ■活动i和是相容的，若S≥或S≥，即 母90☑ 和不相容 2025年4月3日 18
2025年4月3日 18 2.1 问题定义（ An activity-arranging problem ） ⚫ 活动 ◼ 设E={1,2,.,n}是n个活动的集合，各个活动使用同 一个资源，资源在同一时间只能为一个活动使用。 ◼ 每个活动i有起始时间si，终止时间fi，si< fi ◼ 如果选择了活动i，则它在时间[si ，fi )内占用资源。 ⚫ 相容活动 ◼ 活动i和j是相容的，若sjfi或sifj，即 Si fi Sj f Sj j fj Si fi Si Sj fi fj i和j不相容
归本程子末军 2.1问题定义 SHANDONG UNIVERSITY OF TECHNOLOGY 会会是会会8会 ●问题定义： ■输入：E=L,2,n以，s=s,f孙，n≥≥l ■榆出：E的最大相容集合 2025年4月3日 19
2025年4月3日 19 2.1 问题定义 ⚫问题定义： ◼输入：E={1, 2, ., n}，s=[si ] ，f=[f i ] ，ni1 ◼输出：E的最大相容集合
白东程子太军 2.2贪心选择 HANDONG UNIVERSITY OF TECHNOLOGY 贪心法求解活动安排问题的关键是如何选择贪心策略，使 得按照一定的顺序选择相容活动，并能安排尽量多的活动。至 少有两种看似合理的贪心策略： (1)最早开始时间：可以增大资源的利用率。 (2)最早结束时间：可以使下一个活动尽早开始。 由于活动占用资源的时间没有限制，因此，后一种贪心选 择更为合理。 父心思想： 尚了这并最多的相客活动，每欧选民 小的洁动，使我的够选更多的洁动。 2025年4月3日 20
2025年4月3日 20 2.2 贪心选择 由于活动占用资源的时间没有限制，因此，后一种贪心选 择更为合理。 贪心法求解活动安排问题的关键是如何选择贪心策略，使 得按照一定的顺序选择相容活动，并能安排尽量多的活动。至 少有两种看似合理的贪心策略： （1）最早开始时间：可以增大资源的利用率。 （2）最早结束时间：可以使下一个活动尽早开始。 贪心思想: 为了选择最多的相容活动，每次选f i最 小的活动，使我们能够选更多的活动