Greedy Algorithms

!

Dynamic programming

Let’s review the structure of dynamic programming.

Top down formulation

! An naive recursive implementation will likely lead to an exponential time complexity.

___________________

Bottom up computation

  • We start by solving the smallest cases of the subproblems.

  • Based on multiple small solutions, we build up larger solutions.

$$\{\mathrm{solution}(Q_1), \mathrm{solution}(Q_2), \dots, \mathrm{solution}(Q_k)\} \Rightarrow \mathrm{solution}(P)$$

  • Keep going until the instance $P$ is solved.

Memoization

  • During the recursion, we memorize the solutions of subproblems $Q_i$, so that we only perform the computation for the first time we encounter $Q_i$, but not subsequent calls.

!

! For many problems, bottom-up computation and memoization lead to polynomial time complexity.

_______________________

Greedy Algorithms

Example: activity selection

Consider the activity selection problem:

The problem is:

Given a collection of activities $A = \{a_1, a_2, \dots, a_n\}$ find the most number of mutually compatible activities.

_______________________

Consider the following instance of the activity selection problem:

i 1 2 3 4 5 6 7 8 9 10 11
$s_i$ 1 3 0 5 3 5 6 8 8 2 12
$f_i$ 4 5 6 7 9 9 10 11 12 14 16

Here are some examples of mutually compatible selections:


It turns out that the maximal number of mutually compatible activities is 4.

_________________________

Let $P$ be the overall problem instance:

i 1 2 3 4 5 6 7 8 9 10 11
$s_i$ 1 3 0 5 3 5 6 8 8 2 12
$f_i$ 4 5 6 7 9 9 10 11 12 14 16

We want to reduce $P\Rightarrow Q^*$.

We want to pick the first activity greedily. Do we pick $a_1$ or $a_2$ or $a_3$ to leave the most number of remaining activities?

!

!

So, the activity to select as the first should be either $a_1$ or $a_2$, so that we leave the most number of compatible activities.

________________________

Pick the first activity (with earliest finish time), and the subproblem is all remaining compatible activities.

def subproblem(A):
    "assume A is sorted by finish time"
    activity = A[0]
    B = [a for a in A if a.start >= activity.finish]
    return activity, B

Keep generating subproblems until no more activities are left.

def greedy_selection(A, selection):
    while len(A) > = 0:
        a, B = subproblem(A)
        selection.append(a)
        A = B

___________________________

Theorem

back
© KEN PU, 2016