How often do you make a choice that affects you in the short term but may hurt you in the long term? Eating ice-cream rather than going to the gym? Eating out rather than cooking at home? Is this a philosophical article? No. This is about greedy algorithms!
So let’s dive right in. Greedy algorithms are very very similar to what’s mentioned above. They favor local choices, choices they can make now that seem like the best, but in the long term may not always be the best.
Greed is good
Let’s take a look at an example where we’re starting at the root node of
node(7) and trying to find the maximum sum. With a greedy algorithm, we’ll examine all the local possible moves — either
node(12). We see that
node(12) is much bigger, so obviously we move there.
Once we reach
node(12), we examine our new local possible moves — either
node(6). We see that
node(6) is bigger, so obviously we move there.
This now adds up to
7 + 12 + 6 = 25.
Wait. Maybe greed isn’t that good?
But this isn’t the largest sum we can get. If we examined more than just our local positions, we’d see that there is a
node(99), which is huge!
An algorithm which wasn’t as greedy would see this
node(99) and travel from
node(7), to a worse local move,
node(3), to reach an awesome move at
This will add up to
7 + 3 + 99 = 109.
You: Well shit dude, why are greedy algorithms even a thing?
Me: Do not fear dear readers, the pros and cons sections are here!
Greedy algorithms can be really awesome.
- Simplicity. Greedy algorithms are generally easier to write as well as explain. Think of the previous gif — all you need to do is check your neighbors and move to the larger one until you’ve found the end.
- Efficiency. Now don’t confuse efficiency with accuracy. Greedy algorithms may not always be the most accurate, but they are generally very efficient, as you only observer local possible moves.
Cons are obvious. It’s not always the most optimal path.
- Greedy Best-First-Search
- Prim’s Algorithm
- Dijkstra’s Algorithm (more or less)
- Travelling Salesman Problem — Trying to calculate the perfect route takes an insane amount of steps and this problem is often solved through greedy optimizations.
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal…en.wikipedia.org
Data Structures Greedy Algorithms - Learn Data Structures and Algorithm using c, C++ and Java in simple and easy steps…www.tutorialspoint.com
Pathfinders let you plan ahead rather than waiting until the last moment to discover there's a problem. There's a…theory.stanford.edu