复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 09 Greedy algorithms

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

Activity-selection problem Suppose we have a set s= ·· of n proposed activities that wish to use a resource which can be used by only one activity at a time Consider the following set s of activities i12345678910 130535688212 f i 4 67891011121314 Activities a, and a, are compatible if the intervals [s;,A) and si, fi do not overlap

Activity-selection problem Suppose we have a set S = { a 1, a 2, …, a n } of n proposed activities that wish to use a resource which can be used by only one activity at a time. f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Consider the following set S of activities Activities ai and aj are compatible if the intervals [ si, fi ) and [ sj, fj ) do not overlap

Activity-selection problem 1234567891011 s13053|5688|212 f|4567891011121314 Subset (a3, a9, a1 It is not a maximal subset of' mutually compatible activities

Activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Subset { a 3, a 9, a11 } It is not a maximal subset of mutually compatible activities!

Activity-selection problem 1234567891011 s13053|5688|2 12 f i 4 67891011121314 Subset (a1, a4, ag,a11) It is a largest subset of mutually compatible activities

Activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Subset { a 1, a 4, a 8, a11 } It is a largest subset of mutually compatible activities

Activity-selection problem 1234567891011 s13053|5688|212 f4567891011121314 Subset (a2, a4, ag,a11) It is a largest subset of mutuall compatible activities too

Activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Subset { a 2, a 4, a 9, a11 } It is a largest subset of mutually compatible activities too

Brute-force Activity-selection problem is to select a maximum-size subset of mutually compatible activities Analysis Checking =O(n) time per subset of s 2n subset of s Worst-case running time =O(n2 exponential time It is infeasible!

Brute-force Analysis y Checking = O(n) time per subset of S. y 2n subset of S. y Worst-case running time = O(n2n) = exponential time. It is infeasible! Activity-selection problem is to select a maximum-size subset of mutually compatible activities

Structure of Activity-selection problem itakES: fisK<fks s, denote the subset of activities in S that can start after activity a; finishes and finish before activity a, start Suppose now that an optimal solution ai to Si includes activity ak. Then the solutions Aik to Sik and Ak to Sk used within this optimal solution to s must be optimal as we A,=Ak URakjUAk

Structure of Activity-selection problem Sij = { a k ∈ S: fi ≤ s k < fk ≤ sj} denote the subset of activities in S that can start after activity ai finishes and finish before activity aj start. Suppose now that an optimal solution Aij to Sij includes activity a k. Then the solutions Aik to Sik and Akj to Skj used within this optimal solution to Sij must be optimal as well. { } Aij ik k kj = Aa A ∪ ∪

Recursive solution Let cli, i be the number of activities in maximum-size subset of mutually compatible activities in S Recursive definition of c[i,j becomes if s =0 maxi, k]+ck,j+l ifS,*0 i<k<j We add fictitious activities ao and an+ and adopt the conventions that fo=0 and Sn+i=oo, then our goal is c[0,n+1

Recursive solution Let c [ i, j ] be the number of activities in maximum-size subset of mutually compatible activities in Sij. Recursive definition of c [ i, j ] becomes 0 max { [, ] [ , ] 1 } ik j cik ck j < < + + c [ i, j] = if Sij = 0 if Sij ≠ 0 We add fictitious activities a 0 and a n+1 and adopt the conventions that f0 = 0 and s n+1 = ∞, then our goal is: c[0, n + 1]

Greedy solution Theorem Consider any nonempty subproblem Si, and let am be the activity in S; with earliest finish time min ak∈S Then activity a is used in some maximum-size subset of mutually compatible activities of The subproblem Sim is empty, so that choosing a leaves the subproblem Smi as the only one that may be nonempty

Greedy solution Theorem. Consider any nonempty subproblem Sij, and let a m be the activity in Sij with earliest finish time: fm = min{fk: a k ∈ S }. Then y Activity a m is used in some maximum-size subset of mutually compatible activities of Sij. y The subproblem Sim is empty, so that choosing a m leaves the subproblem Smj as the only one that may be nonempty

Computing activity-selection problem 2|3 567891011 s;130535688212 f4567891011121314 k Sk fk i 01234567891011121314

Computing activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 k s k fk 1 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a1