Greedy Algorithms
A greedy algorithm always makes the best choice at the moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution. Greedy algorithms work in stages. In each stage, a decision is made that is good at that point, without bothering about the future.
For example, you can greedily approach your life. You can always take the path that maximizes your happiness today. But that doesn’t mean you’ll be happier tomorrow.
In general, they are computationally cheaper than other families of algorithms like dynamic programming, or brute force. This is because they don’t explore the solution space too much. And, for the same reason, they don’t find the best solution to a lot of problems.
To solve a problem based on the greedy approach, there are two stages
- Scanning the list of items
- Optimization
How do you decide which choice is optimal?
Assume that you have a function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.
Advantages of Greedy Algorithm
- The main advantage of the Greedy method is that it is straightforward, easy to understand and easy to code. In Greedy algorithms, once we make a decision, we do not have to spend time re- examining the already computed values.
- Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer).
Disadvantages of Greedy Algorithm
- The main disadvantage of Greedy Algorithm is that there is no guarantee that making locally optimal improvements in a locally optimal solution gives the optimal global solution.
- It is not suitable for problems where a solution is required for every subproblem like sorting. In such problems, the greedy strategy can be wrong, in the worst case even lead to a non-optimal solution.
- Even with the correct algorithm, it is hard to prove why it is correct.
Problems best solved by Greedy Algorithm
- Travelling Salesman Problem
- Kruskal’s Minimal Spanning Tree Algorithm
- Dijkstra’s Minimal Spanning Tree Algorithm
- Knapsack Problem
- Job Scheduling Problem