Chapter twelve

Greedy algorithms make terrible life partners.

I owe Chapter 2 a debt, and this is the chapter in which I pay it.

In Chapter 2, I described, with some discomfort, a company I had founded, the excellent designers and the excellent programmer I had hired, and my complete inability to let any of them do the work they had been hired to do. I reviewed every line of code. I reviewed every design. I flagged errors. I suggested improvements. I hovered. I kept everyone, including myself, on a permanent low simmer of vigilance, on the unstated theory that if I was not personally involved in every decision, the quality would degrade.

I described this, in Chapter 2, as a single-point-of-failure architecture. That was the operating description. The deeper description, the one this chapter is named for, is that I was running a greedy algorithm. I did not know I was running a greedy algorithm, because nobody at the time had told me there was such a thing as a greedy algorithm, or that there were other algorithms one could run instead, or that running a greedy algorithm on the management of a company was, in technical terms, exactly the wrong move.

I want to fix that now. I want to give you, in this chapter, the piece of computer science that, had I known it at twenty-eight, would have saved me approximately a decade of being the most exhausted man in any given room.

A greedy algorithm is, in computer science, a procedure that makes the locally best choice at every step, without considering the future consequences of that choice. The word greedy is not, in this context, a moral judgment. It is technical, and it describes a specific strategy. At each decision point, take what looks best right now. Move on. Repeat.

Greedy algorithms are, much of the time, beautiful. They are simple. They are fast. They are often correct. There is a whole class of optimization problems for which a well-designed greedy algorithm produces the provably optimal answer, in the smallest possible amount of computation. The shortest-path algorithm that lives inside your phone's map application is, in part, a greedy algorithm. The scheduler that decides which task your computer's processor will run next is, in part, a greedy algorithm. Greedy is not the enemy. Greedy is, for many problems, the right answer.

The trouble is that there is a different class of problems, also enormous, on which greedy algorithms produce, with mathematical reliability, the wrong answer. The wrong answer is not the second-best answer. The wrong answer is, in many cases, the catastrophic answer. The greedy algorithm walks confidently toward the locally optimal choice, takes it, walks confidently toward the next locally optimal choice, takes it, and by step ten finds itself in a configuration from which there is no path to anything good. The locally optimal choices, in aggregate, have moved the system into a region where no good outcome is reachable.

Let me draw the simplest possible illustration.

Imagine you have to make change for fifteen rupees, using coins of denominations one, six, and ten. The greedy algorithm says: take the biggest coin that fits. So you take a ten, leaving five to make change for. Ten does not fit into five. Six does not fit into five. You are forced to take five ones. Total coins used: six. One ten and five ones.

The optimal answer is different. The optimal answer is two sixes and three ones, which is five coins. The greedy algorithm, by reaching for the biggest coin first, locked itself out of the better solution. It was not wrong at any individual step. Each step, taken in isolation, was the locally optimal step. The aggregate of locally optimal steps was a worse solution than a sequence of slightly less locally optimal steps would have produced.

This is the entire pattern. The greedy algorithm makes a small mistake that nobody can quite see in any individual step, but the small mistakes compound, and by the end the system is in a place that it would never have gotten to by deliberation.

Look at the picture. Both paths reach the target. The first move is the only one that meaningfully differs. The greedy algorithm grabs the biggest coin, ten. The dynamic programming approach takes a smaller coin, six, because it has, in technical terms, looked ahead. It has noticed that committing to the ten leaves no good options for finishing. It has accepted a slightly less satisfying first move in exchange for a much better final outcome.

This is, in one image, the entire chapter.

Dynamic programming is the official mathematical fix for greedy algorithms on problems where greedy fails. The idea is, on first encounter, almost comically modest. The idea is: before you commit to a move, consider what you will need to be able to do later, and choose the move that preserves the most useful future moves.

That is the entire idea. The implementations get technical. The textbook treatments fill chapters. The fundamental insight is the one I just wrote, and it is one of the most beautiful pieces of computer science a person can learn at any age, because it is, on inspection, also a piece of practical philosophy. The right move at any moment depends on what you need to be able to do later. Most of the worst decisions you have made in your life were made by ignoring this principle. Most of the best decisions you have made in your life were made by, often without realizing it, applying it.

Here is what greedy and dynamic programming look like in code, on the change-making problem.

def make_change_greedy(target, coins):
    """
    Greedy: at each step, take the largest coin that fits.
    Fast. Often wrong.
    """
    coins = sorted(coins, reverse=True)
    used = []
    for coin in coins:
        while target >= coin:
            target -= coin
            used.append(coin)
    return used


def make_change_dp(target, coins):
    """
    Dynamic programming: compute the minimum number of coins
    needed for every amount from 0 to target, working upward,
    and reconstruct the actual coins used. Slower. Correct.
    """
    # best[i] = minimum coins to make amount i, or None if impossible
    best = [0] + [None] * target
    # choice[i] = the last coin we added to reach amount i
    choice = [None] * (target + 1)

    for amount in range(1, target + 1):
        for coin in coins:
            if coin <= amount and best[amount - coin] is not None:
                candidate = best[amount - coin] + 1
                if best[amount] is None or candidate < best[amount]:
                    best[amount] = candidate
                    choice[amount] = coin

    # Reconstruct the coins from the choice table
    used = []
    a = target
    while a > 0:
        used.append(choice[a])
        a -= choice[a]
    return used


# The change-making problem with non-standard denominations:
target = 15
coins = [1, 6, 10]

print("Greedy:           ", make_change_greedy(target, coins))
# -> [10, 1, 1, 1, 1, 1]  (six coins)

print("Dynamic programming:", make_change_dp(target, coins))
# -> [1, 1, 1, 6, 6]      (five coins, in reverse construction order)

The greedy function is short and elegant. It is also wrong on this input. The dynamic programming function is longer, slightly more complicated, and produces the optimal answer. The two functions are operating on the same problem with the same coins. The difference is entirely in their willingness to consider future consequences when making the current move.

I want to be honest about something. The dynamic programming code is more complex. It requires you to build a table of solutions for all the intermediate amounts. It is slower for any individual step. It feels, on first encounter, like overkill. The greedy algorithm feels, in contrast, brisk and decisive. It just does the thing. Why would anyone, given a choice, prefer the slow careful algorithm to the fast confident one?

The answer is on the page above. The fast confident algorithm produces six coins. The slow careful algorithm produces five. The slow careful algorithm is, by exactly one coin, less wrong, and in the corresponding human applications, that one coin is the marriage, the company, the friendship, or the decade.

Now I want to return to the founder, because the founder is the human face of this chapter and I owe him the careful treatment.

The founder, that is to say me, was running a greedy algorithm on the management of a company. At every decision point, I asked the locally optimal question. Will this designer's work be slightly better if I review it now? The answer was almost always yes. Reviewing the work caught small issues, suggested improvements, raised the quality of the immediate output. The local optimization was real. The local optimization was not, in any individual instance, wrong.

What I was failing to consider, because greedy algorithms do not consider it, was what my reviewing the work was doing to my ability to do other things, later. Each act of reviewing the designer's work cost me an hour. That hour was not available for the work I was, in principle, supposed to be doing as the founder, which was not designing or coding but building the company at the level only the founder could operate at. The hour was, in computer science terms, a future resource I was spending in the present.

It was also, less visibly, costing the designer. The designer, having been reviewed by me, learned that the final standard for her work was my standard, not hers. She began to optimize her work for my reactions rather than for the underlying problem. She began to stop trusting her own judgment, because her judgment was, by demonstration, not sufficient. She began to wait for my review before committing to a direction, which slowed everything down, which made me feel I needed to review more. The feedback loop closed. The locally optimal choice (review this work) had produced the globally catastrophic outcome (a designer who could no longer designed independently, and a founder who could no longer do anything else).

Dynamic programming, applied to that situation, would have asked a different question at each review decision. The question would have been: given that I need this designer to be able to operate independently three months from now, is reviewing this particular piece of work the move that gets me there, or is it the move that prevents me from getting there? The answer, in almost every case, would have been the latter. The locally suboptimal choice (let this design ship even though it has a flaw I would have caught) was the globally optimal choice, because it preserved the designer's capacity to be the kind of designer I needed her to be. The flaw I would have caught, ten times out of ten, was a smaller cost than the ongoing dependence I was building.

I did not know this at the time. I want to be precise. I did not have the framework. I had the intuition that something was wrong, in the vague way one has the intuition that one is exhausted for no good reason. I did not have the vocabulary to identify what was happening as a class of mathematical error with a known fix. The vocabulary, which is now sitting on this page, would have made an enormous difference. The framework would have told me, in technical terms, that I was solving the wrong optimization problem. I was optimizing for the quality of this week's work, when I should have been optimizing for the quality of the company a year from now, and those two optimizations require different moves at almost every decision point.

The man I would now be, had I known this in my late twenties, would not be the man who is writing this paragraph. The man writing this paragraph is the man who learned it the slow way, by living through the consequences. The reader who is reading this paragraph at the age I was then is being offered, free of the cost I paid, the framework that I did not have. Take it. Apply it to your own decisions. Notice when you are reaching for the biggest coin. Notice when the biggest coin is going to leave you with a problem you cannot solve later. Take a smaller coin sometimes. The total cost will be lower.

I want to extend the argument, briefly, beyond the founder, because the chapter title says greedy algorithms make terrible life partners, and the application is not limited to companies.

Consider the argument. Every disagreement is, in technical terms, a small optimization problem. The greedy move is to win the argument. The argument is on the table. The argument has a winner and a loser. The win is locally optimal. The loss is locally suboptimal. The greedy algorithm reaches for the win.

Dynamic programming applied to the same situation asks a different question. Given that I will, almost certainly, have many more disagreements with this person over the next ten years, is winning this particular argument the move that produces the best ten-year outcome, or is it the move that destroys the conditions under which the next nine years of disagreements can productively occur? The answer, in many cases, is that the locally suboptimal choice (let this argument end without a clear winner, accept that the other person is sometimes right even when you are also right, allow the matter to remain partially unresolved) is the globally optimal choice. The argument-winner has won. The relationship-tender has, by a slightly less greedy move, preserved the conditions under which much larger goods are reachable.

This is, in some sense, what wisdom is. Wisdom is the habit of not taking the biggest coin every time. Wisdom is the recognition that the current move's quality depends not only on its local payoff but on the future moves it makes possible. Wisdom is, in computer science terms, dynamic programming as a personality trait.

The young, the ambitious, and the anxious are, all of them, structurally inclined toward greedy algorithms. The young because they have not yet observed the consequences of compounding local decisions. The ambitious because the local payoff is the metric they are scored on. The anxious because the future feels more uncertain than the present, and the present is where the visible problem lives, so the present is where they reach for the visible coin. All three groups have to learn, often the hard way, that the optimization problem they are solving is not, in fact, the optimization problem they have been given.

Chapter 13 takes a different turn, into thermodynamics, and into the question of why a tidy life requires energy to maintain. The chapter introduces entropy as a model of why everything, left alone, drifts toward disorder, and why the anxious mind's habit of treating any current disorder as evidence of moral failure is, in physics terms, a misunderstanding of how the universe works at its most fundamental level.

For now, the page closes here. The biggest coin is not always the right coin. The right coin is the one that leaves you with the best future moves. The fast confident algorithm is, on a surprising number of problems, the wrong one. The slow careful algorithm is, on those same problems, the difference between five coins and six, between a marriage and an argument, between a company and a cage.