南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）贪心算法

计算机问题求解一论题3-2 贪心算法 2022年09月14日

计算机问题求解 – 论题3-2 - 贪心算法 2022年09月14日

间题1： 你还记得什么是“Optimal Substructure”吗？该结构特 性对求解最优解间题有什么启 发？

Activity Selection Problem Activities: 口S={a1;a2;…an} wish to use a resource,which can serve only one activity at a time. oa has a start time s and a finish time fi, Compatible Activities a and a: the intervals [si;fi)and [sj;fj)do not overlap. activity-selection problem: select a maximum-size subset of mutually compatible activities

Activity Selection Problem ◼ Activities: ❑ S={a1 ; a2 ;…;an } ❑ wish to use a resource, which can serve only one activity at a time. ❑ ai has a start time si and a finish time fi, ❑ Compatible Activities ai and aj : ◼ the intervals [si; fi) and [sj; fj) do not overlap. ◼ activity-selection problem: ❑ select a maximum-size subset of mutually compatible activities

Activity Selection Problem The activities are sorted in monotonically increasing order of finish time: 一个样本输入： 00 110 11 2 26 a;ag;a:mutually compatible activities. a;a;ag;a:a largest subset of mutually compatible activities;

Activity Selection Problem 一个样本输入： The activities are sorted in monotonically increasing order of finish time: {a3 ; a9 ; a11}: mutually compatible activities. {a1 ; a4 ; a8 ; a11}: a largest subset of mutually compatible activities;

问题2： 这是一个优化问题，动态规划？ Activity Selection问题是否具有“最优 子结构”？ 构想一个最优解的结构！

构想一个最优解的结构！

最优解型构、子问题、最优子结构特性 .i1234 67891011 3 6 88212 09 10 11121416 非平凡最优解中一定包含一个活动ak:So,12问题从ak处被分解为两 个子问题，如何建模这两个子问题？ 假设k为4：a1,a2,a3构成第一个子问题？a5,a6,..,a11构成第二个子问题？ 简单的子问题建模，将一 无法阐明问题的最优子 结构特性！ Si:the set of activities that start after activity a finishes and that finish before activity a starts

最优解型构、子问题、最优子结构特性 S0,12： Sij: the set of activities that start after activity ai finishes and that finish before activity ajstarts. 非平凡最优解中一定包含一个活动ak：Sij/0,12问题从ak处被分解为两 个子问题，如何建模这两个子问题？ 假设k为4：a1,a2,a3构成第一个子问题？a5,a6,…,a11构成第二个子问题？ 简单的子问题建模，将 无法阐明问题的最优子 结构特性！

最优解型构、子问题、最优子结构特性 23 567 8 9 10 一个样本输入： Si 3 5 8 8 f 9910 1. 1214 S:the set of activities that start after activity afinishes and that finish before activity a starts. Ai:maximum set of mutually compatible activities in S Ao,12:ta a4 as/9;a11 is a solution of So.12

最优解型构、子问题、最优子结构特性 一个样本输入： Sij: the set of activities that start after activity ai finishes and that finish before activity ajstarts. Aij: maximum set of mutually compatible activities in Sij A0,12: {a1 ; a4 ; a8/9; a11} is a solution of S0,12

非平凡最优解中一定包含一个活动ak:Sjj问题被分解为Sk和 Sk两个子问题 If we denote the size of an optimal solution for the set Si;by c[i,j],then we would have the recurrence g]=ci,个+ck+1. S,中最多相互兼容的活动数 我们知道其中包含某活动ak c,={ if Sij=0 max {c[i,k]+c[k,j]+1 if Si 这里的k怎么表达？

Sij中最多相互兼容的活动数 我们知道其中包含某活动ak 这里的k怎么表达？ 非平凡最优解中一定包含一个活动ak：Sij问题被分解为Sik和 Skj两个子问题

动态规划解法 在上述递归关系中，4，可以是S中任一活动，每选定一个特 定的α，则确定特定的子问题。动态规划方法按照合适的次序 解所有的子问题。 问题3：是否有可能不必解所有的子问题？ 0 是否一定要解当k为6时的 8 8 12 11 14 S0.6和S6,12两个子问题

动态规划解法 在上述递归关系中，ak可以是Sij中任一活动，每选定一个特 定的ak , 则确定特定的子问题。动态规划方法按照合适的次序 解所有的子问题。 是否一定要解当k为6时的 S0,6和S6,12两个子问题

问题4： 所谓“GREEDY”是指什么？