Menu
What is the use of greedy algorithms? An real example?
707
Applications of Greedy Algorithm Used to Solve Optimization Problems: Graph - Map Coloring, Graph - Vertex Cover, Knapsack Problem, Job Scheduling Problem, and activity selection problem are classic optimization problems solved using a greedy algorithmic paradigm.
Greedy algorithms are simple instinctive algorithms used for optimization (either maximized or minimized) problems. This algorithm makes the best choice at every step and attempts to find the optimal way to solve the whole problem.
Minimum Spanning Tree - Prim's algorithm and Kruskal's algorithm
Shortest Path Calculation - Dijkstra's algorithm
More: (Fractional Knapsack Problem, Huffman Coding, Optimal Merging, Topological Sort).
70
answered Oct 22 '22 20:10
Some problems are such that a greedy solution will actually be optimal, and sometimes they're engineered that way. A fun example is that many countries' coin values are such that a greedy approach to returning change (i.e. always returning the largest-possible coin until you're done) works.
38
Anything where an optimal solution would be impossible - or very very hard.
Greedy algorithms take the best solution at the current point, even if that's not the best solution if you examined all aternatives
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
