Greedy algorithm makes the locally optimal choice at each step to find the overall optimal way to solve the entire problem. If both of the properties below are true, a greedy algorithm can be used to solve the problem.
- Greedy choice property: A global optimal solution can be reached by choosing the optimal choice at each step.
- Optimal substructure: A problem has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.
Critical Ideas to Think
- In many problems, a greedy strategy does not produce an optimal solution.
- Proving that a greedy algorithm is correct is more of an art than a science. Usually, coming up with an algorithm might seem to be trivial, but proving that it is actually correct, is a whole different problem.
Applications of greedy algorithms: Huffman Encoding, Shortest Path Algorithms, Minimum Spanning Tree, Travelling Salesman Problem, Job Scheduling Problem, Graph Vertex Cover etc .
