1
COMP 7270 ©Bo Liu
Computer Science & Software Engineering
Auburn University
Greedy Algorithm Design
Part I
Content
Activity-selection Problem
• Problem Analysis
• Algorithm Design
• Examples
2
• We will take activity-selection problem for
example.
3
• The activity-selection problem is to select the
maximum number of mutually compatible (i.e.,
non overlapping) activities that one can do from
a set of activities each with its own start and end
times.
Example: i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 9 9 10 11 12 14 16
The activity-selection problem
4
Compatible
5
Formal definition
• Suppose we have a set S = {a1, a2, ..., an} of n
proposed activities that with time to use a
resource. Each activity ai has a start time si and
a finish time fi, where 0 £ si < fi < ¥.
• If selected, activity ai take place during the half-
open time interval [si, fi). Activities ai and aj are
mutually compatible if the intervals [si, fi) and
[sj, fj) do not overlap (i.e., ai and aj are
compatible if si ³ fj or sj ³ fi).
6
Content
Activity-selection Problem
• Problem Analysis
• Algorithm Design
• Examples
7
Revision
• Divide-and-conquer Iterative: divide the problem into
smaller problems (that may overlap) and use iteration
(looping) to solve the smaller problems incrementally until the
whole problem is solved.
E.g., insertion sort, selection sort, bubble sort, radix sort
• Divide-and-conquer Recursive: divide the problem into non-
overlapping subproblems, solve the subproblems
recursively and then finish up by combining the subproblem
solutions into a solution of the overall problem. E.g., merge
sort
If the subproblems overlap, you may end up with an inefficient
algorithm. E.g., the recursive Fib algorithm
• Decrease-and-conquer Recursive: reduce the original
problem into one smaller problem whose solution will yield the
solution to the original problem and solve the smaller problem
through a recursive call
• We will solve this problem in several steps. We
start by formulating a dynamic programming
solution to this program in which we combine
optimal solutions to two subproblems to form an
optimal solution to the original problem.
• We will then observe that we can characterize
the solution recursively in a different way so that
after a choice is made, only one subproblem
needs to be solved recursively.
• Then we will further see that there is a particular
choice – called the greedy choice – that is
guaranteed to lead to an optimal solution, so we
do not have to consider all choices. 9
Content
Activity-selection Problem
• Problem Analysis
– Optimality problem structure
• Algorithm Design
• Examples
10
Dynamic Programming Review
• optimization problem?
• recursive formulation?
• subproblems? how many?
• optimal substructure?
• overlapping subproblems?
11
Dynamic Programming Solution
• optimization problem? Yes
• recursive formulation? yes
• subproblems? how many?
• optimal substructure? yes
• overlapping subproblems? yes
12
A recursive characterization of the
activity-selection problem’s optimal
solution
• S is the set of all available activities; activities ai are
sorted in the increasing order of finish times; i.e., if
i• Define Sij={akÎS : fi £ sk < fk £ sj},
So that Sij is the subset of activities in S that can start
after activity ai finishes and finish before activity aj starts,
i.e., the activities that can be done between the time
interval [fi , sj).
• Now suppose that Aij is the optimal solution to the
activity selection problem for Sij
• Aij can be written as Aik È{ak} ÈAkj where ak, the partial
solution chosen, is any one of the available activities. 13
Formalizing the characterization for
recursive algorithm design
++
=
=
<<
emptySjkckic
emptyS
jic
ijjki
ij
if}1],[],[{max
if0
],[
14
{
Thinking Assignments
• Consider the recursive formulation of the
problem
• Write the corresponding recursive algorithm
• Show that the subproblems overlap, i.e.,
your recursive algorithm duplicates work
• Develop a more efficient memoized
recursive algorithm
• Develop an iterative DP algorithm that builds
a table. What is its complexity?
15
Content
Activity-selection Problem
• Problem Analysis
– Optimality problem structure
– Only one subproblem
• Algorithm Design
• Examples
16
An alternate recursive characterization
of the activity-selection problem’s
optimal solution
• S is the set of all available activities; activities ai are
sorted in the increasing order of finish times; i.e., if ithen fi £ fj
• Define Sij={akÎS : fi £ sk < fk £ sj},
So that Sij is the subset of activities in S that can start
after activity ai finishes and finish before activity aj starts,
i.e., the activities that can be done between times fi and sj.
• Now suppose that Aij is the optimal solution to the
activity selection problem for Sij
• Aij can be written as {ak} ÈAkj where ak the partial solution is
chosen so that Sik is empty.
17
Content
Activity-selection Problem
• Problem Analysis
– Optimality problem structure
– Only one subproblem
– Greedy choice property
• Algorithm Design
• Examples
18
Identifying a greedy choice
• A greedy choice is one among the choices
available that has to be part of an optimal
solution, so you are safe in picking that choice
and thus constructing a partial solution with it,
and one which leaves only one subproblem to
be solved.
• I.e., identifying a greedy choice allows you to
construct a partial solution with confidence, and
to design a decrease-and-conquer recursive (or
iterative) algorithm!
19
Is the greedy choice
—in which we choose the first activity to finish—
always part of some optimal solution?
20
The greedy choice is part of the optimal
solution
• Theorem 16.1
(reading assignment: understand the proof in text)
Consider any nonempty subproblem Sk, and let am
be the activity in Sk with the earliest finish time.
Then
Activity am is used in some maximum-size subset of
mutually compatible activities of Sk. I.e., there is an
optimal solution that contains am.
21
The greedy choice is part of the
optimal solution
• Proof:
22
Construction Proof
Content
Activity-selection Problem
• Problem Analysis
• Algorithm Design
• Examples
23
An iterative greedy algorithm
• s: Array of start times
• f: Array of finish times sorted in the
ascending order
• n: # of activities
24
An iterative greedy algorithm
GREEDY-ACTIVITY-SELECTOR(s, f)
1 n =s.length
2 A ={a1} Initialization
3 k =1
4 for m =2 to n
5 if s[m] ³ f[k]
6 then A = A È {am} Greedy-Iterative
7 k = m
8 return A
Thinking Assignment: Work out this algorithm on the
previous example and understand how it works
25
Content
Activity-selection Problem
• Problem Analysis
• Algorithm Design
• Examples
26
27
Round 1: A1
# Rounds Candidate Selected
Abandoned (after
selection, which
are abandoned)
1 all A1 A2,A3,A5,A10
28
Round 1: A1
Round 2: A4
# Rounds Candidate Selected
Abandoned (after
selection, which are
abandoned)
1 all A1 A2,A3,A5,A10
2 all\{A1-3,A5,A10} A4 A6,A7
29
Round 1: A1
Round 2: A4
Round 3: A8
# Rounds Candidate Selected Abandoned
1 all A1 A2,A3,A5,A10
2 all\{A1-3,A5,A10} A4 A6,A7
3 all\{A1-7,A10} A8 A9
30
Round 1: A1
Round 2: A4
Round 3: A8
Round 4: A11
# Rounds Candidate Selected Abandoned
1 all A1 A2,A3,A5,A10
2 all\{A1-3,A5,A10} A4 A6,A7
3 all\{A1-7,A10} A8 A9
4 A11 A11 EMPTY
Reading Assignment
• Section 16.1
31
Thinking Assignments
• Try text problems 16.1-1:16.1-5
32
Take-home:
Greedy Algorithm Design
33
A general strategy:
1. Check if it has the optimality problem structure
2. If yes, check if it has the following specific
properties:
• Only one subproblem
• Greedy choice property.
3. Decrease-and-Conquer algorithm design:
• Decrease-and-Conquer iterative solution (for
better efficiency)

欢迎咨询51作业君