Greedy algorithms are not confined to textbook exercises. They sit inside compression formats, graph algorithms, and the schedulers of operating systems and clusters. Even where they cannot guarantee an optimum, they are widely used as approximation algorithms that produce a good answer quickly.
Greedy inside real systems
DEFLATE first removes repetition with LZ77, then writes the remaining literals and lengths with Huffman codes. The format (RFC 1951) stores only code lengths and rebuilds the bit strings with canonical Huffman rules, so a function like huffman_code_lengths from the implementation chapter fits right in. Real encoders add a step that adjusts lengths to respect the 15-bit maximum.
Greedy as an approximation algorithm
For NP-hard problems no fast exact method is known, so greedy rules with proven approximation ratios become the practical default.
The LPT (Longest Processing Time) rule assigns jobs to machines longest first, each to the least loaded machine. Its makespan is known to be at most 4/3 of the optimum.
import heapq
def lpt_assign(jobs, machines):
heap = [(0, m) for m in range(machines)] # (load, machine id)
plan = [[] for _ in range(machines)]
for job in sorted(jobs, reverse=True):
load, m = heapq.heappop(heap)
plan[m].append(job)
heapq.heappush(heap, (load + job, m))
return plan, max(sum(p) for p in plan)
print(lpt_assign([7, 5, 4, 4, 3, 3, 2], 3)) # ([[7, 3], [5, 3, 2], [4, 4]], 10)
For set cover, repeatedly pick the set that covers the most still-uncovered elements. This greedy stays within about ln n of the optimum, and if P ≠ NP no polynomial-time algorithm can do substantially better. It is a common tool for choosing test cases or siting base stations and warehouses.
def greedy_set_cover(universe, subsets):
uncovered, picked = set(universe), []
while uncovered:
best = max(subsets, key=lambda name: len(subsets[name] & uncovered))
if not subsets[best] & uncovered:
return None # some element cannot be covered
picked.append(best)
uncovered -= subsets[best]
return picked
regions = {"A": {1, 2, 3, 4}, "B": {4, 5, 6}, "C": {6, 7}, "D": {1, 5, 7}}
print(greedy_set_cover(range(1, 8), regions)) # ['A', 'B', 'C']
Common pitfalls
- Choosing a rule without a proof: passing a few examples proves nothing. Keep a randomized test against brute force on small inputs.
- Interval boundaries: half-open versus closed intervals flips
< and <=. Put boundary cases in the statement and in the tests. - Incomparable heap entries: on equal weights Python compares the next tuple field, so dicts or custom objects raise
TypeError. Insert an increasing counter in between. - Floating-point ratios: sorting value/weight as floats can make ties unstable. Use cross-multiplication or
Fraction. - Missing a problem variant: once weights appear or items become indivisible, the same greedy rule is wrong.
Here is the skeleton of a randomized test that checks a greedy answer against brute force.
import itertools
import random
def brute_force(intervals):
for k in range(len(intervals), 0, -1):
for combo in itertools.combinations(sorted(intervals), k):
if all(a[1] <= b[0] for a, b in zip(combo, combo[1:])):
return k
return 0
def greedy_count(intervals):
count, last_end = 0, float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]):
if start >= last_end:
count, last_end = count + 1, end
return count
for _ in range(500):
data = [(s, s + random.randint(1, 5)) for s in random.choices(range(10), k=6)]
assert greedy_count(data) == brute_force(data), data
print("all passed")
Further reading
Summary
- Huffman codes power DEFLATE and JPEG, and Dijkstra, Prim and Kruskal are greedy algorithms at the heart of graph processing.
- Even where optimality is out of reach, as with LPT scheduling and set cover, greedy is a practical default with proven approximation ratios.
- In production code, watch boundary conditions, heap tie-breaking, floating-point comparisons and problem variants.
- Before shipping greedy code, keep a test that compares it with brute force on small inputs.
コメント 0件
ログイン · ログインするとコメントできます。