[Introduction to Algorithm] Greedy Algorithm

Greedy Algorithm always makes the choice that looks best at the moment, which can solve many optimal problems effectively. However, local optimum does not necessarily result in the global optimum, and we need to take care of it.

Many algorithms can be viewed as application of the greedy method, including minimum-spanning-tree algorithm, Dijkstra's algorithm and Chvátal's greedy set-covering heuristic.

Activity Selection

Problem: Given a set \(A=\{A_1,A_2,...A_n\}\) of n activities, \(s_i=\) start time of activity \(i\), \(f_i=\) finish time of activity \(i\), \(1\le i\le n\), select maximal set S of "non-overlapping" activities.

For example, consider the following set S of activities:

1542194824499

1542194824499

In this case, we can determine that the subset \(\{a_1,a_4,a_8,a_{11}\}\) is the largest subset; another largest subset is \(\{a_2,a_4,a_9,a_{11}\}\).

Recursive Solution

If we denote the size of an optimal solution for the set \(S_{ij}\) by \(c[i,j]\), then we would have the recurrence: \[ c[i,j]=c[i,k]+c[k,j]+1 \] Then we can simply find out the optimal solution: \[ c[i,j]=max_{a_k \in S_{ij}}\{c[i,k]+c[k,j]+1 \} \] Then we formulate a DP problem and solve it recursively.

Greedy Solution

Find the first non-overlapped subset \(s_i\).

  • This choice leases as much opportunity as possible for the remaining activities to be scheduled
def GREEDY_ACTIVITY_SELECTOR(s,f):
    n = s.length
    A = {a[1]}
    k = 1
    for m in range(2, n):
        if s[m] >= f[k]:
            A = A and {a[m]}
            k = m
    return A

Elements of the Greedy Strategy

We can go through the following steps:

  1. Determine the optimal substructure of the problem.
  2. Develop a recursive solution.
  3. Consider if it is safe to make the greedy choice
  4. Develop a recursive algorithm that implement the greedy strategy

Greedy-Choice Property

The greedy-choice property is that we can assemble a globally optimal solution by making locally optimal choices. In other word, we consider the choice that looks best in the current problem, without considering results from subproblems.

In dynamic programming, we make a choice at each step, but the choice usually depends on the solutions to subproblems. Consequently, we typically solve DP problem from small to large (bottom up).

In greedy programming, we only care about the solution that works best at the moment. Therefore, usually greedy programming algorithm works from top to bottom.

Greedy vs Dynamic Programming

Typically, greedy programming problem could be solved by DP, but greedy programming is more effective than DP.

algorithm