To solve a problem, we use that algorithm which provides more efficiency and takes less time to run the program, in short, we try to get the optimal solution for a given problem. Greedy Algorithm is a concept or pattern that we follow to design an algorithm. In Greedy Algorithms, we build a solution piece by piece and every piece we chose based on the optimal solution. We use a set of different optimal solutions to make it a global solution. Greedy algorithms always try to provide the optimal solution by grabbing those elements first, which they think is nearest to that solution. In the real world, we often use greedy paradigm algorithms to solve many problems such as Travelling Salesman problems, Counting Coins, etc.
Counting Coins using Greedy Algorithm
In Counting Coins problem, we have given an amount and we have to select the least numbers of coins to make that amount. For example, if we have to make ? 7 and we can only use ? 1, ?2, ?5, and ? 10 coins for that, so what would be the optimal solution. For this we can use the greedy algorithm, as algorithm say choose the closest element to the solution so we will choose ? 5 first, once we have chosen 5 ? coin, now we require a coin which is near to 2?, then we will choose the 2? coin and hence we will get our answer. If we try to solve this problem using other algorithms there could be many other solutions but here greedy algorithm provides the optimal solution.
Application of Greedy Algorithm
There are many applications of the Greedy algorithm:
- Travelling Salesman Problem
- Prim's Minimal Spanning Tree Algorithm
- Kruskal's Minimal Spanning Tree Algorithm
- Dijkstra's Minimal Spanning Tree Algorithm
- Graph - Map Colouring
- Graph - Vertex Cover
- Knapsack Problem
- Job Scheduling Problem
People are also reading: