Greedy algorithm paradigm that follows the problem solving approach of making the locally optimal choice at each stage with the hope of finding the global optimum. In other words, at each step of the algorithm, it chooses the best available option without considering the consequences of that choice in the future steps.
Consider the blow tree, find a path from root to leaf that all the nodes adds up results in the maximum:
we can use greedy method. We start from the root, which branches out into 4 and 7. We pick the greater between the two, 7. We continue on 7 and discovered two nodes 9 and 11, and we choose the greater number 11. Now we ended up at the end with solution
The greedy method uses the local optimal choice where each time encountered a branch the algorithm always choose the node that has greater value. However, this is not the best solution overall. The most optimal solution is
Greedy algorithm VS dynamic programming
Greedy algorithm makes irrevocable decisions in every its criterion.
| Feature | Greedy Approach | Dynamic Programming |
|---|---|---|
| Optimality | May not always provide an optimal solution. | Guarantees an optimal solution if the problem exhibits the principle of optimality. |
| Subproblem Reuse | Does not reuse solutions to subproblems. | Reuses solutions to overlapping subproblems. |
| Backtracking | Does not involve backtracking. | May involve backtracking, especially in top-down implementations. |
| Complexity | Typically simpler and faster to implement. | May be more complex and slower to implement. |
| Application | Suitable for problems where local optimization leads to global optimization. | Suitable for problems with overlapping subproblems and optimal substructure. |
| Examples | Minimum Spanning Tree, Shortest Path algorithms. | Fibonacci sequence, Longest Common Subsequence. |
Back to parent page: Data Structures and Algorithms
Reference: