Greedy Algorithm
Greedy algorithms solve problems by making the choice that seems best at the particular moment. Many optimization problems can be solved using a greedy algorithm.
Some problems have no efficient solution, but a greedy algorithm may provide a solution that is close to optimal.
Unfortunately, greedy algorithms do not always give the optimal solution, but they frequently give good (approximate) solutions.
To give a correct greedy algorithm one must first identify optimal substructure (as in dynamic programming), and then argue that at each step, you only need to consider one subproblem.
That is, even though there may be many possible subproblems to recurse on, given our selection of subproblem, there is always an optimal solution that contains the optimal solution to the selected subproblem.
A greedy algorithm works if a problem exhibits the following two properties:
1. Greedy Choice Property
Globally optimal solution can be arrived by making a locally optimal solution (greedy). The greedy choice property is preferred since then the greedy algorithm will lead to the optimal, but this is not always the case the greedy algorithm may lead to a suboptimal solution.
Similar to dynamic programming, but does not solve subproblems. Greedy strategy more top-down, making one greedy choice after another without regard to subsolutions.
2. Optimal Substructure
Optimal solution to the problem contains within it optimal solutions to subproblems. This implies we can solve subproblems and build up the solutions to solve larger problems.
Characteristics of Greedy
- These algorithms are simple and straightforward and easy to implement.
- They take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future.
- They work in stages and never reconsider any decision.
Advantages of Greedy Algorithms
- Usually (too) easy to design greedy algorithms.
- Easy to implement and often run fast since they are simple.
- Several important cases where they are effective/optimal.
- Lead to first-cut heuristic when problem not well understood.
Disadvantages of Greedy Algorithms
- Very often greedy algorithms don’t work.
- Easy to lull oneself into believing they work.
- Many greedy algorithms possible for a problem and no structured way to find effective ones.
Greedy Algorithms Analysis Pattern
Like all families of algorithms, greedy algorithms tend to follow a similar analysis pattern.
Greedy Correctness
Correctness is usually proved through some form of induction. For example, assume their is an optimal solution that agrees with the first k choices of the algorithm.
Then show that there is an optimal solution that agrees with the first k + 1 choices.
Greedy Complexity
The running time of a greedy algorithm is determined by the ease in maintaining an ordering of the candidate choices in each round.
This is usually accomplished via a static or dynamic sorting of the candidate choices.
Greedy Implementation
Greedy algorithms are usually implemented with the help of a static sorting algorithm, such as Quicksort, or with a dynamic sorting structure, such as a heap.
Additional data structures may be needed to efficiently update the candidate choices during each round.
Different Types of Greedy Algorithm
- Activity Selection (Interval Scheduling) Problem
- Huffman Codes
- Knapsack Problem
- Coin Changing
- Minimum Spanning Tree (MST)
- Prim's Minimal Spanning Tree Algorithm
- Kruskal's Minimal Spanning Tree Algorithm
- Dijkstra's Minimal Spanning Tree Algorithm
- Ford-Fulkerson Algorithm
- Single Source Shortest Path
- Interval Coloring