Greedy Algorithms
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(3) or 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(5) or 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 node(99).
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!
Pros
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
Cons are obvious. It’s not always the most optimal path.
Uses
- 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.
