# 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.

#### Resources

**Greedy algorithm - Wikipedia**

*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**

*Data Structures Greedy Algorithms - Learn Data Structures and Algorithm using c, C++ and Java in simple and easy steps…*www.tutorialspoint.com