Why can nearest-stop greedy routing, taking the closest undelivered address each time, produce a poor total route?
answer
- think about what the first hop costs later
- cheapest move now, stranded stops afterwards
- each pick reshapes the remaining problem
- one address left on the wrong side
- locally best moves need not compose
basics
~20 sEach nearest-stop pick is cheapest right now but reshapes what remains. Cheap early hops strand far-apart addresses for the end, so a chain of locally best moves need not add up to the best route.
solid answer
~40 sA greedy rule commits to whatever looks best at the current step and never reconsiders it. Nearest-stop routing optimizes one hop at a time, but every hop changes the set of stops that remain and where you stand when you face them, so the cheap decision now can force an expensive one later. Concretely, with a depot at kilometre 0 and parcels at +1, -2 and +4 on one avenue, nearest-first drives 0 to +1 to -2 to +4 for 10 km, while going 0 to -2 to +1 to +4 costs 8 km. Nothing is wrong with the distance arithmetic — the rule simply lacks the property that would make committing safe, namely that some optimal route begins with the nearest stop. It is a reasonable heuristic, not an optimal algorithm.
go deeper
Be ready to state in plain words that a greedy rule optimizes one step at a time and that this need not add up to the best total. Having one tiny counterexample memorised, with actual numbers, is worth more than any definition.
Explain the mechanism: each committed choice changes both your position and the remaining set, so a saving now can force a larger cost later. Name the missing ingredient — a safe-move argument that some optimal solution starts with your pick.
Show the judgment of shipping such a rule anyway: call it a heuristic in the code and the docs, bound how bad it can get on your real inputs, and decide whether a refinement pass fits the latency budget.
Own the framing for the team: decide when an approximate-but-cheap answer is the right product choice, what quality bar the output must meet, and how a claim of optimality gets reviewed before it reaches a customer-facing promise.
## What a greedy rule actually promises A greedy algorithm builds a solution one decision at a time. At each step it applies a fixed local rule — take the smallest, the nearest, the earliest, the densest — commits to that choice, and never revisits it. Its appeal is exactly this lack of backtracking: no search tree, no memo table, usually one pass over the data. Its danger is the same thing: a choice you never revisit had better not be the one that ruins you. The promise a greedy rule makes is small and local: *this single step is the cheapest available from where I stand right now*. It says nothing at all about the total. Turning the local promise into a global one requires an extra property that has to be argued separately, and for nearest-stop routing that property is simply false. ## The counterexample, in full Put a depot at kilometre 0 on a straight avenue and three parcels at +1, -2 and +4. Distance is just the difference between marks. - **Nearest-first.** From 0, the candidates are 1 km, 2 km and 4 km away, so the courier drives to +1. From +1, both -2 and +4 are 3 km away; either tie-break leads to the same total. Say -2: that is 3 km, then -2 to +4 is 6 km. Total **10 km**. - **A better order.** 0 to -2 is 2 km, -2 to +1 is 3 km, +1 to +4 is 3 km. Total **8 km**. The greedy rule saved 1 km on the very first hop and paid 3 km for it later. That is the whole phenomenon in miniature: the first pick left a stop stranded on the wrong side, and crossing back was more expensive than the saving. ## Local optimum versus global optimum A *local* optimum is the best choice within the current step's options. A *global* optimum is the best complete solution. The two coincide only when a specific structural fact holds — informally, when there is always some optimal complete solution that begins with the move your rule makes. That is called the greedy-choice property, and it is what licenses the phrase "safe move". When it holds, committing costs you nothing: you may have thrown away *other* optimal solutions, but never *every* optimal solution. When it fails, as here, the very first commitment can already have excluded all of them. Notice how little the failure has to do with the data being weird. Three parcels on one straight street is about as tame as an input gets. Beginners often conclude that a counterexample means the input was adversarial or the implementation buggy; neither is true. One counterexample is enough to demote a greedy rule from *algorithm* to *heuristic*, permanently. ## Why nearest-first still gets used Calling it a heuristic is not calling it worthless. Nearest-first is trivial to implement, runs fast, produces a route that is often close to good, and makes an excellent starting point that a later improvement pass can refine. Plenty of production systems ship exactly this: a greedy first pass to get a workable answer, then a bounded refinement step if the latency budget allows. What you must not do is *claim* optimality for it, or be surprised by the occasional route that looks silly on a map. The honest framing in an interview is two sentences: "the rule is locally optimal by construction; it is globally optimal only if a safe-move argument exists, and here it does not — here is a three-stop counterexample." ## The habit to build When you propose any greedy rule, immediately ask two questions. First: *after I make this choice, what problem is left?* (For routing, it is the same problem from a new starting point with one fewer stop — the structure recurses cleanly.) Second: *can I argue that some best-possible complete answer starts with my choice?* If the second question has no answer, you have written a heuristic, and you should say so out loud before an interviewer says it for you.
- Does nearest-stop routing ever produce the optimal route?Often, on friendly inputs — and that is exactly what makes it dangerous. Producing the optimum on the cases you tried is not a guarantee; on adversarial layouts it can be far off. Without a safe-move argument covering every input, it stays a heuristic no matter how many examples come out right.
- What would have to be true for always taking the nearest stop to be provably optimal?You would need the greedy-choice property: for every input, at least one optimal route begins with the nearest stop. Then committing to it can never discard all optimal solutions, and the same argument applies to the smaller problem that remains. A single counterexample refutes it, and routing has easy ones.
- Is a greedy rule that is not optimal still worth writing?Yes. A fast greedy pass is a fine heuristic, a good seed for a later improvement step, and a useful baseline to measure a slower exact method against. The requirement is honesty: document it as approximate, and do not let a caller assume the answer is minimal.
It is like always taking the shortest queue at a checkout: right now it is the fastest line available, but the trolley in front of it may be enormous, and you cannot unmake the choice.
saying these in an interview costs you the question
- Greedy algorithms always return the optimal answer
- The locally cheapest hop must belong to the best route
- A bad route means the distances were computed wrong
- A counterexample just means that input was unusual
- Greedy is brute force made faster, with the same result