ALGO·III Algorithms Chapter 23 of 65
Greed and electricity
Moravia in the 1920s: power lines are reaching the villages, and every kilometer of wire costs money. You are an engineer at the power company. First you lay the lines by hand, then you prove that the recipe “shortest wire first” never goes wrong. Along the way: a cashier who does go wrong, a repair crew with a schedule, and a code invented by a student who would rather not take an exam.
Algorithms
Builds on: 22 · Remember instead of recomputing 19 · Six handshakes 18 · Who is next
What you will take away
- tell the problems where a greedy step leads to the best answer, and prove it with an exchange argument
- build a minimum spanning tree with Kruskal’s and Prim’s algorithms, and write a union-find structure
- compress text with a Huffman code built on a heap
The last chapter ended at the till. Dynamic programming finds the fewest coins for any amount, but the person at the till fills in no tables. The cashier takes the largest coin that fits into the change, then the largest again, and with American coins this somehow always comes out as the fewest coins possible. Is it luck, or does it have to be so? A step that looks best right now, with no thought for what comes later, is called greedy. Sometimes greed leads straight to the best answer, sometimes into a dead end. The difference is easiest to see in an engineer’s job: power lines are being run to Moravian villages, and every kilometer of wire costs money.
Brno, 1926. Work order one: the wires
Here is your first work order. On the map are thirteen villages and small towns around Slavkov. In German the town is called Austerlitz, and near it Napoleon defeated the Russian and Austrian armies. A wire can run straight between any two places, and a kilometer costs the same everywhere. Current flows along the wires in any direction, so you don’t need to connect every village with every other: it is enough that a path along the wires leads from any village to any other, even if it goes through the neighbors. Connect them all with as little wire as possible. Tap one village, then another, and a wire will run between them; tap a wire and it is gone.
How did you go about it? Almost certainly you started with short wires between neighbors and ran long ones only when there was no way around them. And you probably didn’t run a wire between villages that were already connected: such a wire closes a cycle, and the current gains nothing from it. This is the recipe that the American Joseph Kruskal would publish in 1956: go through the possible wires from shortest to longest, and take each one unless it closes a cycle. If your network came out longer than Kruskal’s, find the place where you strayed from the recipe.
At every step Kruskal takes the cheapest of the allowed wires and never changes his mind. That is how a greedy algorithm works: the answer grows step by step, each step takes whatever is best by a simple local rule, and a choice once made is never revisited. Such algorithms are short and fast. The trouble is that “best now” needn’t lead to best in the end, and a couple of lucky examples guarantee nothing; you need a proof. The till shows why the bar is set so high.
The till: where greed goes wrong
American coins are worth 1, 5, 10 and 25 cents. A greedy cashier gives 41 cents in change as a quarter, a dime, a nickel and a penny: four coins. You can’t do it with fewer; check for yourself. Now imagine a country with coins of 1, 3 and 4. For change of 6, the greedy cashier takes the largest coin, the 4, and makes up the remaining 2 with two 1s: three coins. Yet two 3s make the same 6 with two coins. The 4 looked like the best move and turned out to be a mistake that can’t be undone afterward.
Compare the greedy cashier with the dynamic programming of Chapter 22, which remembers the fewest coins for every amount from 1 up to the one you need. For which coin systems does greed ever go wrong? We won’t have to try every amount up to infinity. In 1994 Dexter Kozen and Shmuel Zaks proved that if the greedy cashier goes wrong anywhere at all, the smallest failure comes at an amount below the two largest coins added together. So the check is finite.
From 1961 the Soviet Union used coins of 1, 2, 3, 5, 10, 15, 20 and 50 kopecks. Did a greedy cashier always give change in the fewest coins?
Always: the check below tries every amount up to 69 kopecks and finds no failures. The 3 and the 15 look suspicious, but they do no harm. British coins before 1971, on the other hand, defeat greed. In use were the penny, coins of 3 and 6 pence, the shilling (12 pence), the florin (24) and the half crown (30), and for 48 pence the greedy cashier hands over a half crown, a shilling and a sixpence instead of two florins.
American cents, tenge, Soviet kopecks and euros are arranged so that greed never fails; coin systems like these are called canonical. British coins before decimalization and the set 1, 3, 4 are not. Britain was not the only one: India had coins of 5, 10, 20 and 25 paise, and a greedy cashier gave 40 paise as three coins (25, 10, 5) instead of two 20s. Try any set that comes to mind.
The lesson is an uncomfortable one: a greedy rule is no more than a hypothesis. “Take the best now” finds the optimum on some data and misses on other data, and from the outside you can’t tell which is which. We need a way to prove that a greedy step is safe. There is one, and it is easiest to show on a problem simpler than the wires.
Work order two: one crew
The power is on, and now the network needs maintenance. The district has one line crew and one bucket truck. The villages send in requests: “cut our line from 9 to 12, we’re replacing poles.” Each request has its own window, the work can’t start earlier or end later, and the crew can be in only one place at a time. The windows overlap, so not every request can be met. How do you choose so as to meet as many as possible?
Several greedy rules suggest themselves. Take the shortest request, since it ties up the crew the least. Take the one that starts first, so as not to waste the morning. Take the one that clashes with the fewest others. Or the one that ends first. Try them out.
Three of the four rules break, and for two of them the bad examples are simple. The shortest request can overlap two long ones that didn’t get in each other’s way. The earliest one can take up the whole day. “Fewest conflicts” is harder to catch: our bad example for it takes eleven requests, but even this rule can be fooled. And “ends first” breaks on no example at all. That needs proving, and the proof is worth remembering, because it will come back more than once.
Sort the requests by their end time and take each one that doesn’t overlap the ones already taken. The result is the largest possible number of requests.
Let $g$ be the request that ends first. Take any best schedule and put its requests in time order: $o_1, o_2, \ldots, o_k$. Request $g$ ends no later than $o_1$, since it is the first of all requests to end. Replace $o_1$ in the schedule with $g$. There is no clash: $g$ ends no later than $o_1$, and $o_1$ ended no later than $o_2$ began. There are still $k$ requests, so this is a best schedule too, and it begins with the greedy choice.
The remaining requests of that schedule, $o_2, \ldots, o_k$, start after $g$ ends, and they form a best schedule for all the requests that start after $g$ ends: if those requests allowed a longer schedule, it would beat the best one once $g$ was added in front. After choosing $g$, the greedy algorithm uses the same rule on that problem, which is smaller than the original. By induction on the number of requests it finds $k - 1$ of them there, and $k$ in all.
This technique is called the exchange argument. You take any optimal solution and show that it can be reworked, by swapping a piece of it for the greedy choice, without becoming worse. So the greedy step never closes off the road to the optimum, and what is left after it is the same problem, only smaller. Think back to the till: for coins 1, 3, 4 and the amount 6 the exchange fails. The only best answer is two 3s, and the 4 that greed grabbed first can’t be fitted into it.
The program is shorter than the proof. Press “Steps” and watch the variable free_at: it marks the hour from which the crew is free.
Five requests out of eleven, and no schedule does better. Sorting costs $O(n \log n)$, the pass over the requests $O(n)$. The non-strict >= is there on purpose: a request that starts in the hour when the previous one ended is allowed, because we assume the crew moves from village to village instantly. The windows in the program are half-open, like range: a request from 9 to 10 takes up the hour $[9, 10)$.
The spanning tree
Back to the wires, this time with a precise statement of what we are after. The villages are the vertices of a graph from Chapter 19, the possible wires are its edges, and every edge has a weight: its length in kilometers. We need to choose some of the edges so that they lead from any vertex to any other, and so that their total weight is as small as possible.
A best answer never contains a cycle. If some wires form a cycle, throw out any one of them: the current still gets everywhere, going the other way round along the rest of the cycle, and less wire is used. A connected graph without cycles is a tree, a relative of the trees from Chapter 17, only without a root and without left and right. So the answer is called a spanning tree, a tree that spans every vertex and holds them all together, and the lightest such tree is a minimum spanning tree. A tree on $n$ vertices always has $n - 1$ edges: at first every village is a network of its own, and there are $n$ of them; each wire that doesn’t close a cycle merges two networks into one; at the end a single network is left.
Kruskal, Prim and Borůvka from the widget work in different ways, but they rest on one fact. Split the villages into two groups however you like, say, those west of the river and those east of it. Such a split is called a cut, and the wires that join the two groups are the edges of the cut. The network must contain at least one edge of the cut, or the groups wouldn’t be connected. The question is which one.
For any cut, the shortest edge of the cut belongs to at least one minimum spanning tree.
Let $e$ be the shortest edge of the cut, and let $T$ be a minimum spanning tree that doesn’t contain $e$. Add $e$ to $T$. The tree already had a path between the ends of $e$, so we get a cycle, and only one: that path plus $e$. The path starts on one side of the cut and ends on the other, so one of its edges, $f$, also crosses the cut, and by the choice of $e$ the edge $f$ is no shorter than $e$. Throw out $f$. The cycle is broken and nothing is disconnected: whatever used to go through $f$ can now go around through $e$. There are $n - 1$ edges again, so $T + e - f$ is a spanning tree, and it is no longer than $T$. It is a minimum spanning tree too, and it contains $e$.
It is the exchange argument again, this time for wires, and it proves Kruskal right. When he takes a wire between villages $u$ and $v$, they lie in different networks. Cut the region like this: the network that contains $u$ against all the other villages. Every shorter wire has already been considered, and none of them crosses this cut. If one did, its ends would lie in different networks, both now and back when its turn came, because networks only ever grow. Kruskal would have taken that wire, and its ends would now be in one network. So the wire $u$–$v$ is the shortest edge of the cut, and by the cut property it is safe to take.
Who is already connected to whom
Kruskal’s recipe has a question in it that we answered by eye on the map: will this wire close a cycle? Put another way, are both villages already in the same network? You could walk the network breadth-first every time, as in Chapter 19, but that is $O(n)$ per wire, and the region has more than two hundred thousand possible wires. We need a data structure that can do two things: say which network a village is in, and merge two networks into one.
Picture an army. Each network has a head village, and every village remembers its commander; the head village is its own commander. To find out which network a village is in, follow the commanders up until you reach the head. Two villages are in the same network if they have the same head. To merge two networks, the head of one becomes a subordinate of the head of the other, which is a single assignment. This is a disjoint-set structure, also called union-find after its two operations. It lives in a single list, parent, as the heap from Chapter 18 lived in a single array.
The chains of command must not grow long, and there are two patches for that. When merging networks, put the smaller one under the larger: then the path from a village to its head gets longer only when the village’s network at least doubles, so it is never longer than $\log_2 n$. And on the way up to the head, shorten the road for next time: every village along the path is reassigned to its commander’s commander. Press “Steps” and watch the list parent.
Wire 0—2 turned out to be redundant: villages 0 and 2 were already connected through 1 and 3. The last wire, 3—7, merges two networks of four villages each, and on the way to the head the path of village 3 got shorter: it was 3 → 2 → 0, and now it is 3 → 0. With both patches, any sequence of $m$ operations on $n$ villages costs $O(m\,\alpha(n))$, where $\alpha$ is the inverse Ackermann function. Robert Tarjan proved this for full path compression in 1975, and for our variant, the one that skips every other step, he did it together with Jan van Leeuwen in 1984. The function $\alpha$ grows so slowly that for any number of villages that would fit in the memory of any computer it is at most 4. The structure itself was described by Bernard Galler and Michael Fischer in 1964.
All of South Moravia
Now we can assemble Kruskal from these parts and run it on the whole region. The file /data/greedy/moravia.csv holds 675 towns and villages of the South Moravian Region with their coordinates and populations, taken from the open gazetteer GeoNames (license CC BY 4.0). Every possible wire, each place with each, makes 227,475 wires. We measure distances in straight lines; at this scale the earth may be taken as flat, as long as we remember that at the latitude of Brno a degree of longitude is only $\cos 49^\circ \approx 0.66$ of a degree of latitude in length.
The minimum spanning tree of the whole region is 1,570.5 km long. If every village got its own wire from Brno, like the rays of a star, it would take 23,364 km, almost fifteen times as much. The longest wire in the best network is 5.6 km, from the center of Brno to Moravany: the city’s own districts aren’t in the file, so the center has nothing closer to connect to. The whole job took less than a second, and most of that time Python spent computing and sorting two hundred thousand distances.
Prim: the network grows from the power station
Kruskal builds the network in pieces scattered across the region and stitches them together only at the end. An engineer is more used to another way: there is a power station, and the network grows out of it. At each step we connect the village closest to the network built so far. This is greedy too, and it is right for the same reason, the cut property: the cut is “connected against the rest,” and we take its shortest edge.
The closest village is easy to get from a heap, once more the priority queue of Chapter 18. The heap holds candidate wires from the network to villages not yet connected. Once a village is connected, other, longer wires to it may remain in the heap. Finding and removing them from the middle of the heap is slow, so we leave them where they are and throw a stale wire away when it comes up to the top. We will need this device again in the next chapter.
The same length, 1,570.5 km. When all the lengths are different, the minimum spanning tree is unique, and both algorithms find the same tree, only in a different order. Prim starts with the villages nearest Brno (Moravany, Nebovidy, Ostopovice) and spreads across the region like a stain. Here every newly connected village pushes wires to all the others into the heap, which makes $O(n^2 \log n)$. If lines are allowed only along roads and there are $m$ of them, then Prim with a heap and Kruskal with sorting both run in $O(m \log n)$.
Borůvka’s own algorithm works in rounds. In each round every piece of the network picks, all at the same time, the shortest wire leading out of it, and all those wires are laid at once. Every piece merges with at least one neighbor, so the number of pieces at least halves each round, and there are at most $\log_2 n$ rounds. Its correctness is once more the cut property, with one cut for each piece. Within a round the pieces don’t depend on each other, which suits computers with many processors: many parallel algorithms for spanning trees are built on Borůvka’s idea. You can watch the rounds in the widget at the start of the chapter, with the “Borůvka” button.
Why Borůvka required all the distances to be different
He posed the problem from the start so that all the distances between the points were different, and without that condition his algorithm breaks. Suppose three pieces of the network sit at the corners of an equilateral triangle. Each picks its shortest wire out, and those wires are all the same length: the first piece may pick the wire to the second, the second the wire to the third, the third the wire to the first. Lay all three at once and you get a cycle. The cure is the same as for ties in the heap of Chapter 18: when lengths are equal, compare the wires by their numbers, and then “the shortest” is always unambiguous. Equal lengths don’t bother Kruskal and Prim: they take one wire at a time and check every time whether it would close a cycle.
Work order three: telegrams
Once the network is built, people have to talk over it: the dispatcher with the substations, the substations with each other. Every bit on the line costs time, and time costs money. In Chapter 8 we counted how many units Morse code spends on War and Peace and gave short codes to frequent letters, and we promised to build the most economical code for given frequencies here. It was invented by a student who very much wanted to get out of an exam.
First, which codes will do. Morse code separates letters with pauses, but a binary code has no pauses, only zeros and ones. To read it without separators, one rule is enough: no code may be the beginning of another. Such a code is called a prefix code. You read the bits one by one; as soon as they spell out a codeword, that is a letter, and you start on the next. A prefix code is convenient to draw as a tree: at every fork the left branch is 0 and the right one 1, the letters sit in the leaves, and the code of a letter is the road to it from the root. Since letters sit only in leaves, no road continues another.
The cost of a code is a sum over all the letters: how many times the letter occurs, times the length of its code, which is the depth of its leaf. Huffman saw where you cannot go wrong: at the bottom. Let $x$ and $y$ be the two rarest letters. There is a best tree in which they are siblings on the deepest level. This is the exchange once again: if the rare letter $x$ sits higher than a more frequent letter $a$, swap them, and the cost changes by $(f_a - f_x)(\ell_x - \ell_a) \le 0$, where $f$ stands for frequencies and $\ell$ for depths. Now glue the siblings into one “letter” with frequency $f_x + f_y$: what remains is the same problem with one letter fewer. Repeat until a single tree is left. The result is a Huffman code. The full proof that it is optimal, and of why the average code length can never be less than the entropy, is in “Mathematics, the Queen of the Sciences,” in the chapter on measuring information; here we care about how the code is built and what it gives in practice.
Before Huffman, the best method was the top-down one now known as Shannon–Fano coding: sort the letters by frequency and cut the list into two parts with totals as close as possible; the left part gets 0, the right part 1, and the same goes on within each part until single letters are left. That is greedy too, but it makes the most consequential decision, the one at the top, first, and a mistake there can never be repaired. Suppose the letters occur 15, 7, 6, 6 and 5 times. Top-down gives the parts $\{15, 7\}$ and $\{6, 6, 5\}$ and the codes 00, 01, 10, 110, 111: 89 bits in all. Huffman merges $5 + 6$, then $6 + 7$, then $11 + 13$, then $15 + 24$: the frequent letter gets a one-bit code and the others three bits each, 87 in all. Huffman started from the end where a greedy step can be proved, and that made all the difference. The “Where top-down loses” button in the widget loads these frequencies.
The two rarest letters, again and again: a job for the heap from Chapter 18. We put triples into the heap: frequency, number, tree. The number breaks ties, so that heapq never tries to compare trees. A tree is either a letter or a pair of subtrees.
The English translation of the novel has 3,187,950 characters, 97 of them distinct. To tell 97 symbols apart, a fixed-length code needs 7 bits; a plain text file spends a byte, 8 bits, on each character, and UTF-8 a little more, because curly quotes, dashes and accented letters take two or three bytes. The Huffman code needs 4.45 bits per character: 44% shorter than a byte per character and 45% shorter than UTF-8. The space, the most frequent character, gets a three-bit code, and so does “e”; “z” gets ten bits, and “æ”, which turns up only once in the whole book, in the Latin phrase vis inertiæ, gets twenty-one. Among codes that encode each letter separately, none does better, and the limit is close: Shannon proved that such a code can’t spend less than the entropy, and for this translation of War and Peace it is 4.42 bits per character. To compress further, you have to encode words and repetitions, which is the subject of Chapter 47. The Huffman code will be there too: it works inside ZIP, PNG, JPEG and MP3, usually paired with other techniques.
When greed is right
What do the crew, the wires and the code have in common, and what sets them apart from the till with coins 1, 3, 4? A greedy algorithm is right when two conditions hold. First, the greedy step is safe: some best solution begins with it. This is proved by an exchange: take any best solution and rework it around the greedy choice without losing anything. Second, after the greedy step a smaller problem of the same kind remains, and its best answer together with the greedy step makes a best answer to the whole. This is the same optimal substructure on which the dynamic programming of Chapter 22 rests.
The two approaches differ in how many options they try. Dynamic programming tries every option at every step and remembers the best answers to the subproblems. Greed picks one option and never looks back. When greed is right, it is simpler and faster: the requests are chosen in one pass, without a table. When it isn’t, you need dynamic programming. With coins 1, 3, 4 the first condition fails: no best solution for the amount 6 begins with the 4.
The knapsack shows the border well. In Chapter 22 the thief took items whole, and the rule “most valuable per kilogram first” goes wrong there. But if the goods can be poured (grain, sand, spices), the same rule is right: pour in the most valuable per kilogram until it runs out or the knapsack is full, then the next. The exchange proves it in one line: any kilogram of a cheaper good in the knapsack can be swapped for a kilogram of a more valuable one still left outside, and the knapsack will not lose value.
In which of these problems does a greedy algorithm always find the best answer?
Gas stations are the crew problem again. Take any best plan of stops and compare its first stop with the greedy one. The greedy stop is no closer to the start, since you can’t get any farther on one tank. Replace the plan’s first stop with the greedy one: from there to the plan’s second stop is no farther than it was, so the tank will last. The number of stops is the same, and what is left is the same problem from a new starting point.
Matroids: when greed is right for any weights
There is a theory that answers “when is greed right” for a whole class of problems at once. Call a set of wires independent if it contains no cycle. Independent sets have two properties. Any part of an independent set is independent. And a smaller independent set can always be extended with something from a larger one: if one cycle-free set has fewer wires than another, some wire of the second can be added to the first without closing a cycle. In 1935 Hassler Whitney named the structures with these properties matroids. A theorem associated with the names of Richard Rado and Jack Edmonds says that the greedy algorithm “take the most valuable element as long as the set stays independent” finds the best set for any weights if and only if the independent sets form a matroid. Kruskal is a special case. Request selection is not a matroid, and there greed is right only with a particular order: by end time.
One last point. Even when greed doesn’t find the optimum, it often gives a decent answer fast. A traveling salesman who always drives to the nearest unvisited city covers more distance than the best route, but usually by tens of percent, not by a factor of several. How much more, and why the exact answer is so hard to get, is a story for Chapter 58.
Tasks
Four tasks for the chapter’s four greedy algorithms. Each has a big test with a stopwatch, and every other one has a catch at the edges.
Requests are given as pairs (start, end), half-open windows $[start, end)$, and always start < end. Write max_requests(requests), which returns a list of the chosen requests (the pairs themselves) in time order: the chosen windows don’t overlap, and the list holds as many requests as possible. A request that starts at the moment another ends doesn’t overlap it. Times can be any numbers, negative and fractional ones included. Identical requests do occur, and only one of them can be done. The tests have up to 200,000 requests.
Sort the requests by end time: sorted(requests, key=lambda r: r[1]).
Keep track of the moment from which the crew is free. A request fits if it starts no earlier than that moment.
The starting value is float("-inf") rather than 0, because times in the tests can be negative. The chosen requests already come in time order: sorted by their ends, and therefore by their starts too, since they don’t overlap. The proof of correctness is the theorem from the section about the crew.
Write a class DisjointSets: DisjointSets(n) creates $n$ villages numbered 0 to $n - 1$, each in a network of its own. Methods: find(x) returns the head village of the network that contains x (the same one for all the villages of a network); union(a, b) merges the networks of villages a and b and returns True, or, if they are already in one network, changes nothing and returns False. The attribute groups holds the current number of separate networks. The tests run hundreds of thousands of operations, and without the patches the chain of command will stretch out into a line.
Take find and union from the cell networks.py and turn them into methods: parent and size become attributes of the object.
Don’t forget to decrease groups on every successful merge. A recursive find on a chain of 200,000 villages will run into the recursion depth limit, so write it as a loop.
One patch would be enough on its own: union by size alone gives $O(\log n)$ per operation, and path compression alone gives, amortized, $O(\log n)$ as well. Together they give almost a constant.
The villages are numbered 0 to $n - 1$ ($n \ge 1$), and the possible wires are triples (u, v, w): a wire between villages u and v of length w (which can be negative, say, when the government subsidizes the line). Write kruskal(n, edges), which returns a pair: the total length of a minimum spanning tree and the list of its wires, as the same triples as in the input. If the villages can’t all be connected, return None. There may be several wires between two villages, and even a “wire” from a village to itself.
Sort the triples by length: sorted(edges, key=lambda e: e[2]). To check whether a wire would close a cycle, you need a disjoint-set structure, either the one from the previous task or a simpler one on a single list.
A wire from a village to itself always closes a cycle, and find will catch that by itself. All the villages are connected once the tree has collected $n - 1$ wires.
There is only path compression here, without union by size, and for Kruskal that is plenty. Negative lengths don’t bother the algorithm: nothing in the cut property relies on lengths being positive.
Write huffman_code(text), which returns a dictionary that gives each character of the text its code, a string of '0' and '1'. The code must be a prefix code, and the encoded text must be as short as possible. If the text has only one distinct character, its code is one bit. For an empty text, return an empty dictionary. The tests will also run the whole of War and Peace through it.
Put triples (frequency, number, tree) into a heap, where at first each tree is a single character. While the heap holds more than one tree, take out two and push back their pair, with the sum of their frequencies and a new number.
Hand out the codes by walking the finished tree: left is '0', right is '1'. If the whole tree is a single character, give it the code '0', or it will get an empty string.
The number in the triple is there so that, when frequencies are equal, heapq doesn’t compare a character with a tuple, which would be a TypeError. The codes are handed out by a walk with a stack, as in Chapter 15, though recursion would do too: the tree is never deep. For it to stretch into a line of $k$ forks, the frequencies would have to grow like the Fibonacci numbers, and already for $k = 40$ the text would need hundreds of millions of characters.
What next
In 1959 Dijkstra sent a three-page note to the new journal Numerische Mathematik, “A note on two problems in connexion with graphs.” The first problem in it is ours: connect the points so that the total length of the connections is as small as possible. The second is to find the shortest path between two points. The wires in Moravia are up, but now the engineer has to drive around: from Brno to a fault in Mikulov, from there to a substation. Trying every road is hopeless, there are far too many, and the BFS of Chapter 19 counts intersections, not kilometers. We need the shortest path from A to B. The next chapter builds a navigation app and plots routes across the graph of the Moscow metro. And Dijkstra, by his own account, invented the algorithm for it in twenty minutes, over a cup of coffee on the terrace of an Amsterdam café.