1. What is Greedy Algorithm?
A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution. However, generally greedy algorithms do not provide globally optimized solutions.
Formal Definition
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
In general, greedy algorithms have five components:
- A candidate set, from which a solution is created
- A selection function, which chooses the best candidate to be added to the solution
- A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
- An objective function, which assigns a value to a solution, or a partial solution, and
- A solution function, which will indicate when we have discovered a complete solution
2. Advantages and Disadvantages of Greedy Algorithm
- Finding solution is quite easy with a greedy algorithm for a problem.
- Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer).
- The difficult part is that for greedy algorithms you have to work much harder to understand correctness issues. Even with the correct algorithm, it is hard to prove why it is correct. Proving that a greedy algorithm is correct is more of an art than a science.
3. List of Algorithms based on Greedy Algorithm
The greedy algorithm is quite powerful and works well for a wide range of problems. Many algorithms can be viewed as applications of the Greedy algorithms, such as :
- Travelling Salesman Problem
- Prim's Minimal Spanning Tree Algorithm
- Kruskal's Minimal Spanning Tree Algorithm
- Dijkstra's Minimal Spanning Tree Algorithm
- Graph - Map Coloring
- Graph - Vertex Cover
- Knapsack Problem
- Job Scheduling Problem
4. Examples
4.1 Counting Coins
This problem is to count to a desired value by choosing the least possible coins and the greedy approach forces the algorithm to pick the largest possible coin. If we are provided coins of ₹1, ₹5, ₹10 and ₹20 (Yes, We've ₹20 coins :D) and we are asked to count ₹36 then the greedy procedure will be −
- Select one ₹20 coin, the remaining count is 16
- Then select one ₹10 coin, the remaining count is 6
- Then select one ₹5 coin, the remaining count is 1
- And finally, the selection of one ₹ 1 coins solves the problem
Though, it seems to be working fine, for this count we need to pick only 4 coins. But if we slightly change the problem then the same approach may not be able to produce the same optimum result.
For the currency system, where we have coins of ₹1, ₹6, ₹10 and ₹20 value, counting coins for value 36 will be absolutely optimum but for count like 32, it may use more coins than necessary. For example, the greedy approach will use 20 + 10 + 1 + 1, total 4 coins. Whereas the same problem could be solved by using only 3 coins (20 + 6 + 6)
4.2 Finding Largest Sum
If we've a goal of reaching the largest-sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.
Hence, we may conclude that the greedy approach picks an immediate optimized solution and may fail where global optimization is a major concern.
