Read on Twitter
Greedy algorithms are a powerful weapon to solve a lot of problems
Unfortunately, they are not always the way to go because they can lead to wrong solutions
When do they work?
When do they are the worst option?
When do they yield an acceptable solution?
Unfortunately, they are not always the way to go because they can lead to wrong solutions
When do they work?
When do they are the worst option?
When do they yield an acceptable solution?
Well-known examples of problems that can be solved using greedy algorithms are:
Fractional Knapsack
Min cost path on a graph (Dijkstra's algorithm)
Min Spanning Tree of a graph (Prim's and Kruskal's)
Fractional Knapsack
Min cost path on a graph (Dijkstra's algorithm)
Min Spanning Tree of a graph (Prim's and Kruskal's)
In this kind of problem, we get the global optimal solution by choosing the local best option in each step
Is like if we could assure we'll be happier tomorrow if we take the option that makes us happier today.
Of course, life and problems are not that simple
Is like if we could assure we'll be happier tomorrow if we take the option that makes us happier today.
Of course, life and problems are not that simple
If a graph has negative edges, then Dijkstra's algorithm fails. Actually, we can build a graph for which that algorithm yields a solution as bad as we wanted.
The same happens with the 0-1 Knapsack Problem (not fractional)
In these cases, greedy algorithms are a bad choice
The same happens with the 0-1 Knapsack Problem (not fractional)
In these cases, greedy algorithms are a bad choice
But there are problems in which we can apply a greedy strategy even if this is not the way to obtain the best solution. That's because the greedy strategy can make good approximations in those problems
An example is finding the Vertex Cover of a graph
An example is finding the Vertex Cover of a graph
In these cases, the greedy strategy might be a good option because it tends to lead to cheaper and easier to implement algorithms.
If you want a more detailed explanation with more examples and code. You can read my post on this subject
https://jj.hashnode.dev/greedy-strategy-can-be-useful-even-when-it-doesnt-work
If you want a more detailed explanation with more examples and code. You can read my post on this subject
https://jj.hashnode.dev/greedy-strategy-can-be-useful-even-when-it-doesnt-work
Hope you find this post and the article useful 
