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

活动选择问题 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