Of greedy algorithms


One of the main things you learn in theoretical computer science, is that some problems are hard: it is impossible to find the best solution for them in a reasonable time using the types of computers we currently have access to, and reasonable time means something shorter than the age of the universe.

One example of such a problem is the traveling salesman: finding the shortest path that visits all cities of a country, say France. France has 440 cities (places with more than 20’000 people), this approximates to 5.63 × 10973 possible itineraries, the generally admitted age of the universe is 4.3 × 1017 seconds. So even if we had a trillion processors 1012 , capable each of evaluating a trillion itineraries per seconds (say running at a terahertz frequency), running since the beginning of the universe, we would only have computed around 4.3 × 1041 itineraries, a tiny fraction of total set (less than 1 / 10900). So this can really not be solved in a reasonable time.

While it is very hard to find the best solution, life goes on with acceptable solutions: it is possible to visit all cities of France, just not in the perfect sequence. One approach to solve the problems in practice are called greedy algorithms, they are called like this because they typically solve the problem one step at the time, consuming always the easiest available next step. For instance for the traveling salesman problem, that would be, after visiting each city, look for the closest unvisited city and go there.

Such an approach is not optimal and can be trapped by its own greed: the traveler might end up drifting to one corner of France only to realise that the next un-visited city is on the other side of the country, that he needs to traverse a large territory of visited cities to find his next step. This is called a local minima, getting trapped there is bad and a greedy algorithm might get stuck there, unable to pay the price to get out. On the other hand, greedy algorithm tolerate the chaos of reality pretty well, the roads between cities change length all the time, it might be impossible to visit some because of some event (be it a strike or a festival), and while you are touring the country, one place might get the new inhabitant that makes it a city. A greedy algorithm adapts instantly, because it has no real strategy.

Often, the best one can do is couple greed and smarts, that is among the cheapest options, not choose the one cheapest, but one cheap one that is compatible with a long term strategy. If the strategy fails, greed is always here as a backup-plan. This will never find the optimal solution, but the art is to get as close as possible to it while adapting to the changes and randomness of reality.

Unsurprisingly, the way nature works seem to follow a similar strategy: greed, with a lot of smarts bolted on top of it, evolve and adapt, but keep around enough variation and richness to avoid being trapped in some corner of the evolutionary landscape. That does not mean that there are no local minima, are a typical example.

Politics, at the core is just about solving a problem: what rules to set up, how to distribute resources to make people thrive and be happy. The underlying problem is much more complex than just travelling around the country, probably in the same ballpark that evolution and life in general. Yet, I think the same considerations apply: finding the optimal solution is not reasonable, because of the complexity of the model and the chaos of reality, but unfettered greed means the system is quickly stuck in a local minima, like for instance high-frequency trading.

The political system seems dominated by people whose projected ideology is either to suggest theoretical solutions that cannot work in practice, or proponent of unsupervised greed, yet at the same time, the way they act on the problem is either by always optimising the next vote, the next political item (greedy approach) or they want a complete revolution of everything (theoretical model), they are particularly consistent between their ideology and behaviour.

3 thoughts on “Of greedy algorithms

  1. 1) Seems that the “greediness” and the local minimum trap changes with outside pressure.

    If you’re free to travel a long time and dedicate brain time to plan your travel, you’ll have less chances to be stuck in a local minimum, or a less suboptimal one.

    Works at work too: some changes must be done, all of them RIGHT NOW! You’ll have much more chances to add so much bandaids and dirty tricks on the first changes that it will make the last ones impossible. Add some time, invest in cleaning, accept some delay, the resulting product will be much better.

    2) And this pressure comes from the outside: this is not a salesman going through all towns, but two salesmen both trying to suck the available money before the other. The greediest and quickest wins.

    Same in nature. Even if animals could make plans to direct their own evolution, the hard rule would prevail: the immediate next generation must survive, we’ll care about next ones later.

    Our own future evolution (cyborgs, genetically improved humans…) could be decided by the next greedy moves of Google or Apple, not a conscious and planned decision of the whole mankind.

  2. In nature, there are limiting mechanisms all over the place: predators have to leave some pool of preys alive, or they die off, herbivore cannot grow in number to much, or they eat all the vegetation, etc…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: