Greedy Algorithm
History of Greedy Algorithms
Here is an important landmark of greedy algorithms:
Greedy algorithms were conceptualized for many graph walk algorithms in the 1950s.
- In the same decade, Prim and Kruskal achieved optimization strategies that were based on minimizing path costs along weighed routes.
- In the ’70s, American researchers, Cormen, Rivest, and Stein proposed a recursive substructuring of greedy solutions in their classical introduction to algorithms book.
- The Greedy search paradigm was registered as a different type of optimization strategy in the NIST records in 2005.
- Till date, protocols that run the web, such as the open-shortest-path-first (OSPF) and many other network packet switching protocols use the greedy strategy to minimize time spent on a network.
What is a Greedy Algorithm?
In Greedy Algorithm a set of resources are recursively divided based on the maximum, immediate availability of that resource at any given stage of execution.
To solve a problem based on the greedy approach, there are two stages
- Scanning the list of items
- Optimization
Greedy algorithms may not always lead to the optimal global solution, because it does not consider the entire data.
The choice made by the greedy approach does not consider the future data and choices. In some cases making a decision that looks right at that moment gives the best solution (Greedy), but in other cases it doesn’t. The Greedy technique is best suited for looking at the immediate situation.
Architecture of the Greedy approach
STEP 1)Scan the list of activity costs, starting with index 0 as the considered Index.STEP 2)When more activities can be finished by the time, the considered activity finishes, start searching for one or more remaining activities.STEP 3)If there are no more remaining activities, the current remaining activity becomes the next considered activity. Repeat step 1 and step 2, with the new considered activity. If there are no remaining activities left, go to step 4.STEP 4 )Return the union of considered indices. These are the activity indices that will be used to maximize throughput.
Characteristics of Greedy approach
1. There is an ordered list of resources(profit, cost, value, etc.)
2. Maximum of all the resources(max profit, max value, etc.) are taken.
3. For example, in fractional knapsack problem, the maximum value/weight is taken first according to available capacity.
Advantages and Disadvantages of Greedy Approach
· Greedy approach is easy to implement.· Typically have less time complexities.
· Greedy algorithms can be used for optimization purposes or finding close to optimization in case of NP Hard problems.
Disadvantages
· The local optimal solution may not always be global optimal.
Examples
Most networking algorithms use the greedy approach. Here is a list of few of them −
- Travelling Salesman Problem
- Prim’s Minimal Spanning Tree Algorithm
- Graph — Map Coloring
- Graph — Vertex Cover
- Knapsack Problem
- Job Scheduling Problem
