Prerequisite: Sorting Algorithms

Greediness is natural - we inherently strive to achieve the maximum gain. But we tend to become impatient and myopic. What seems most beneficial in the immediate moment might not be the best choice for the long term.

Ultimately, greed is the driving force behind many problem-solving approaches. The key lies in being smart about how we apply it. Immediate gratification doesn’t always yield optimal results, because the environment we operate in is complex and does not conform to our whims at every step. Your previous actions constrain your future options. Taking a step back and examining the bigger picture proves to be a more insightful approach.

While it’s true that in some instances the strategy aiming for immediate gratification aligns with the whole picture, this isn’t a universal truth. Just because a person with myopia can see some objects doesn’t mean they don’t need glasses. What provably works is adopting a broader perspective - considering the larger context, planning ahead, and applying greediness only in scenarios where it is guaranteed to be the best strategy. In the real world, greedy strategies don’t always guarantee success.

The Robot Tour: A Case Study

Consider a robot tasked with visiting all points on a plane, returning to its starting point, while minimising total distance travelled. A naturally greedy, near-sighted approach is to always join the nearest unvisited point and continue until all points are joined.

flowchart TD A([Start at any point]) --> B[Find nearest unvisited point] B --> C[Move to it] C --> D{All points visited?} D -- No --> B D -- Yes --> E[Return to start] E --> F([Tour complete]) F --> G["⚠ Path may not be optimal - early choices lock in later ones"]

We can prove this is incorrect by contradiction. Starting from a point, always choosing the nearest neighbour can produce a wasteful back-and-forth movement - where a different ordering would have yielded a much shorter total path. The intuition behind the greedy choice was that “adding up small pieces gives a small total.” But this problem is not just about small pieces - at each step we don’t have all the choices. The set of available points depends entirely on which points we have already visited, so acting hastily early can lock us into a very poor sequence of choices later.

There is another flawed assumption worth naming: that directly joining two close points must be better than a path through intermediate points (which would be geometrically longer). The mistake here is comparing two things that don’t do the same job. The direct line ignores all other points; the indirect path is also visiting them. The extra distance isn’t purely a cost - it also handles other responsibilities that can balance things out.

If we had two ways to join the same two points, the shorter one is obviously better. But when two options are not doing exactly the same thing, evaluating only one aspect greedily leads to wrong conclusions.

Another Greedy Attempt

What if instead we join all pairs of closest points first until we have a complete loop? This also fails - and interestingly for exactly the same reasons: the same flawed assumptions and wrong comparisons re-appear.

The Exhaustive Alternative

The correct approach is to consider all possible orderings of points and take the minimum. This is provably correct - the actual optimal solution is somewhere in all possible orderings. However, for $n$ points there are $n!$ orderings, making this exhaustive search computationally explosive and impractical for large inputs.

The Takeaway

The issue is not with greedy thinking itself - it is with blindly accepting its correctness. A good practice is to first think of a simple greedy strategy, then actively look for loopholes. If you can prove the greedy strategy always works, great. If not, you need a smarter approach. Greediness is a powerful instinct; the discipline is in knowing when to trust it.

Read Next: Minimum Spanning Trees & Union-Find - where we prove a greedy algorithm actually works.