Greedy Algorithms

Overview

Some years ago, I read about an interesting approach to delivery logistics.
The people driving the delivery trucks were instructed to try to always take right turns. Supposedly, the idea was that right turns are quicker, less dangerous and when taking that into account, - that would supposedly take you to the desired destination in an overall quicker way with less downtime for accidents.
In short - right turns were considered the optimal solution on each crossroad/roundabout.

Did that work out well for that company - unfortunately I don't remember the outcome.
But this is fantastic example for a 'greedy' algorithmic apporach - always taking the most optimal decision at each step. Then, the end goal would 'supposedly' be reached.

But why I have used 'supposedly' more than once?

Because taking the right decision without considering the bigger picture doesn't always lead to the most optimal result for the whole problem. If it were, all people would've been taking only right turns...

If we apply that to greedy algorithms, it's obvious that they are not always the best approach.
For some problems, a greedy algorithm would take a decision too early or not use enough context which could lead to an inferior overall outcome compared to other approaches.
In contrast, for specific problems, a greedy algorithm could be a great solution if it happens to lead to an optimal outcome.

Also, greedy algorithms are fantastic for quick to make solutions or approximatations.

And in the next section, we will take a look at the famous Dijkstra's algorithm that is considered 'greedy'.