Greedy algorithms

A greedy algorithm builds a solution one piece at a time, always taking the choice that looks best right now and never reconsidering it. Dijkstra's, Kruskal's and Prim's algorithms are all greedy, and their correctness depended on careful arguments. This lesson studies the greedy method in general: when it works, how to prove that it works, and how to recognize problems where it fails. The examples, scheduling activities, assigning rooms, meeting deadlines, compressing data with Huffman codes and making change, are each solved by a short algorithm whose real content is the proof.

What makes a problem greedy-friendly

Two properties together make a greedy algorithm correct. The greedy-choice property says that some optimal solution begins with the greedy choice, so committing to it never rules out an optimum. Optimal substructure says that after making the choice, what remains is a smaller instance of the same problem, and an optimal solution to it combines with the choice to give an optimal solution overall. Many tempting greedy rules lack the first property, so the honest workflow is: propose a rule, look hard for a counterexample, and if none appears, prove the rule correct.

Two proof styles cover most greedy algorithms. In a greedy-stays-ahead proof, you show that after each step the greedy partial solution is at least as good as any other algorithm's partial solution after the same number of steps, measured in the right way. In an exchange argument, you take any optimal solution and transform it step by step into the greedy solution, showing that each exchange keeps it optimal. You saw an exchange argument in lesson 10's proof of the cut property.

Activity selection

Given \(n\) activities, each with a start time \(s_i\) and a finish time \(f_i\), select as many as possible so that no two overlap. Think of booking the most talks into a single lecture hall. Several greedy rules come to mind: choose the shortest activity, the one that starts earliest, the one with the fewest conflicts, or the one that finishes earliest. Only the last rule always works.

Here is a greedy-stays-ahead proof for earliest finish first. Let the greedy choices, in order, finish at times \(g_1 \le g_2 \le \cdots \le g_k\), and let any optimal solution, sorted by finish time, finish at \(o_1 \le o_2 \le \cdots \le o_j\). Claim: \(g_r \le o_r\) for every \(r \le k\). For \(r = 1\) this holds because greedy picks the earliest finish of all. If \(g_r \le o_r\), then the optimal solution's \((r+1)\)-th activity starts after \(o_r \ge g_r\), so it was available to greedy, and greedy chose something finishing no later: \(g_{r+1} \le o_{r+1}\). If the optimum had more activities, \(j > k\), its activity \(k + 1\) would start after \(o_k \ge g_k\) and greedy would not have stopped. So \(k = j\), and greedy is optimal. Sorting by finish time costs \(\Theta(n \log n)\) and the selection is a single linear scan.

from itertools import combinations
import random

def greedy(acts, key):
    chosen, last_end = [], float('-inf')
    for s, f in sorted(acts, key=key):
        if s >= last_end:
            chosen.append((s, f)); last_end = f
    return chosen

def compatible(sel):
    sel = sorted(sel, key=lambda a: a[1])
    return all(sel[i][1] <= sel[i + 1][0] for i in range(len(sel) - 1))

def best(acts):                              # brute force over subsets, small n only
    for r in range(len(acts), 0, -1):
        for sel in combinations(acts, r):
            if compatible(sel):
                return r
    return 0

rules = {'earliest finish': lambda a: a[1], 'earliest start': lambda a: a[0],
         'shortest': lambda a: a[1] - a[0]}
random.seed(11)
fails = {name: 0 for name in rules}
for trial in range(300):
    acts = []
    for _ in range(9):
        s = random.randint(0, 20); acts.append((s, s + random.randint(1, 8)))
    opt = best(acts)
    for name, key in rules.items():
        if len(greedy(acts, key)) < opt:
            fails[name] += 1
print('instances where the rule is not optimal (out of 300):', fails)

instances where the rule is not optimal (out of 300): {'earliest finish': 0, 'earliest start': 118, 'shortest': 282}

Random testing finds failures of the earliest-start and shortest-first rules quickly and never finds one for earliest finish, which matches the proof. Testing like this is a cheap way to kill bad ideas; it cannot prove a good one, which is why the argument above matters.

Interval partitioning

A related problem asks for the minimum number of rooms needed to schedule all the activities, with no overlaps within a room. The depth of a set of intervals, the largest number that overlap at any single time, is an obvious lower bound: those activities need different rooms. A greedy algorithm meets the bound. Process activities in order of start time, and put each one in any room that has become free, opening a new room only when every existing room is busy. A min-heap of room finish times finds a free room in \(O(\log n)\), so the algorithm runs in \(O(n \log n)\). Whenever it opens room \(d\), the \(d - 1\) other rooms are all busy at that start time, so at least \(d\) activities overlap; the number of rooms never exceeds the depth.

import heapq

def rooms_needed(acts):
    ends = []                               # min-heap of finish times, one per room
    for s, f in sorted(acts):               # by start time
        if ends and ends[0] <= s:
            heapq.heapreplace(ends, f)      # reuse the room that frees up earliest
        else:
            heapq.heappush(ends, f)         # open a new room
    return len(ends)

def depth(acts):
    events = sorted([(s, 1) for s, f in acts] + [(f, -1) for s, f in acts])
    cur = best = 0
    for t, d in events:                     # finishes (-1) sort before starts at equal times
        cur += d; best = max(best, cur)
    return best

talks = [(9, 10.5), (9, 12.5), (9, 10.5), (11, 12.5), (11, 14), (13, 14.5), (13, 14.5), (14, 16.5), (15, 16.5), (15, 16.5)]
print('rooms used by greedy:', rooms_needed(talks), ' depth:', depth(talks))

rooms used by greedy: 3  depth: 3

Scheduling to minimize maximum lateness

Now suppose one machine must process \(n\) jobs, each with a processing time \(t_i\) and a deadline \(d_i\). If job \(i\) finishes at time \(C_i\), its lateness is \(\max(0, C_i - d_i)\), and we want to minimize the largest lateness. The greedy rule is earliest deadline first: sort the jobs by deadline and run them back to back. The proof is an exchange argument. Call a pair of jobs an inversion if the one with the later deadline is scheduled first. Any schedule with an inversion has an adjacent inversion, and swapping that adjacent pair never increases the maximum lateness: the job that moves later now finishes when the other used to, but its deadline is later, so its lateness is no worse than the other job's was. Repeatedly swapping removes all inversions without increasing the maximum lateness, turning any optimal schedule into the greedy one.

Huffman coding

Text is usually stored with a fixed number of bits per character, but if some characters are much more common than others, a variable-length code saves space by giving common characters short codewords. To decode unambiguously, the code must be a prefix code: no codeword is a prefix of another. A prefix code corresponds to a binary tree whose leaves are the characters, with each left branch read as 0 and each right branch as 1. The cost of the code is the average codeword length, \(\sum_c p(c) \cdot \text{depth}(c)\), where \(p(c)\) is the frequency of character \(c\).

David Huffman's 1952 algorithm, devised as a student, builds an optimal tree greedily. Start with each character as a one-node tree weighted by its frequency. Repeatedly remove the two lightest trees from a priority queue, join them under a new root whose weight is their sum, and insert the result. When one tree remains, it is an optimal prefix code. The exchange argument shows that some optimal tree has the two least frequent characters as sibling leaves at the deepest level; merging them reduces the problem to a smaller one with the same structure. With a heap, Huffman's algorithm takes \(O(k \log k)\) for an alphabet of \(k\) characters.

import heapq
from itertools import count

def huffman(freq):
    tick = count()                           # tie-breaker keeps heap entries comparable
    heap = [(f, next(tick), ch) for ch, f in sorted(freq.items())]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)
        f2, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tick), (a, b)))
    codes = {}
    def walk(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or '0'
        else:
            walk(node[0], prefix + '0'); walk(node[1], prefix + '1')
    walk(heap[0][2], '')
    return codes

freq = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}      # per 100 characters
codes = huffman(freq)
for ch in sorted(codes):
    print(ch, freq[ch], codes[ch])
avg = sum(freq[c] * len(codes[c]) for c in freq) / sum(freq.values())
print('average bits per character:', avg, ' fixed-length code needs 3')

a 45 0
b 13 101
c 12 100
d 16 111
e 9 1101
f 5 1100
average bits per character: 2.24  fixed-length code needs 3

With these frequencies, the Huffman code averages 2.24 bits per character instead of 3, a 25 per cent saving. Huffman coding is a stage in DEFLATE, the method inside ZIP files and PNG images, and in JPEG and MP3 compression, usually combined with other techniques.

When greedy fails

Greedy algorithms fail whenever an early commitment can block a better overall solution. Two classic examples make the point. In the fractional knapsack problem, a thief may take fractions of items, each with a weight and a value, up to a weight limit; taking items in decreasing order of value per kilogram is optimal. In the 0/1 knapsack problem, items must be taken whole, and the same rule can fail badly. With capacity 50 and items of weight and value (10, 60), (20, 100) and (30, 120), the ratio rule takes the first two for a value of 160, but the last two give 220. The 0/1 knapsack problem needs dynamic programming, in CMPUT-304.

Making change is the other standard example. With Canadian or US coins of 1, 5, 10 and 25 cents, giving the largest coin that fits at each step always uses the fewest coins. But with coins of 1, 3 and 4, the greedy method makes 6 as 4 + 1 + 1, three coins, while 3 + 3 uses two. Whether greedy works depends on the coin system, and coin systems where it works are called canonical. A greedy algorithm is never correct just because it seems natural.

from functools import lru_cache

def greedy_change(amount, coins):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c; used.append(c)
    return used

def optimal_count(amount, coins):
    @lru_cache(maxsize=None)
    def best(a):
        if a == 0:
            return 0
        return 1 + min(best(a - c) for c in coins if c <= a)
    return best(amount)

for coins in ((1, 5, 10, 25), (1, 3, 4)):
    bad = [a for a in range(1, 100) if len(greedy_change(a, coins)) > optimal_count(a, coins)]
    print(coins, 'amounts below 100 where greedy is not optimal:', len(bad), bad[:5])
print('greedy for 6 with (1, 3, 4):', greedy_change(6, (1, 3, 4)))

(1, 5, 10, 25) amounts below 100 where greedy is not optimal: 0 []
(1, 3, 4) amounts below 100 where greedy is not optimal: 24 [6, 10, 14, 18, 22]
greedy for 6 with (1, 3, 4): [4, 1, 1]