GREEDY ALGORITHMS FOR DUMMIES BY A DUMMY
Algorithms for optimization problems typically go through a sequence of steps, with a set of choices at each step. Using dynamic programming for choosing the best choice is excessive, more efficient and simpler algorithms will do. This is where Greedy algorithms come in.
Greedy Algorithms are algorithms that always make the choice that looks best at the moment. That is , it makes a locally optimal choice in the hope that the choice will lead to the globally optimal solution. Even if a greedy algorithm chooses a less optimal solution, it will not backtrack to find the optimal solution.
General recipe for a Greedy Algorithm:-
1.Start off with an empty solution set.
2.An item is added at each step until a solution is reached.
3.If the solution set is feasible, the current item is kept.
4. Else the item is rejected and never considered again.
We can determine if the algorithm can be used with any problem if the problem has these following properties :-
1.Optimal Substructure
If a problem’s optimal overall solution corresponds to the optimal solution to the subproblems , the problem can be solved using greedy algorithms.
2.Greedy Choice property
If an optimal choice can be found by making the best decisions at each step without giving a second thought to the previous decision, the problem can be solved using a greedy algorithm.
Greedy algortihms do not always provide the optimal solution but in most cases they do.
Some Basic Greedy algorithms are :-
PRIM’S ALGORITHM
Prim’s Algorithm is a minimal spanning tree algorithm that takes a graph data structure input and finds the subset of the edges of that graph which:-
1. Form a tree that includes every vertex.
2. Has the minimum sum of weights among all the trees that can be formed from the graph.
Steps to execute Prim’s Algorithm:
1. Start from the source vertex or choosing a random vertex as the starting point.2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree.3. Repeat step 2 until minimum spanning tree is obtained.
The following diagram will make the mechanics of the algorithm more clear.
KRUSKAL’S ALGORITHM
Kruskal’s algorithm has the exact same purpose as the Prim’s algorithm, couldn’t hurt to have multiple routes to the same destination.
Kruskal’s algorithm is a minimum spanning tree algorithm that takes a graph input and finds the subset of the edges of that graph which :-
1. Form a tree that includes every vertex
2. Has the minimum sum of weights among all the trees that can be formed from the graph
Steps to execute Kruskal’s algorithm:
1. Sort all the edges from low weight to high2. Take the edge with the lowest weight and add it to the spanning tree. If adding an edge created a cycle, then reject the edge.3. Repeat step 2 until minimum spanning tree is obtained.
The following diagram will make the mechanics of the algorithm more clear.
DIJKSTRA’S ALGORITHM
The Dijkstra’s (enunciated as Dike-straw) algorithm is used to find the shortest path between any two vertices of a graph. It differs from minimal spanning tree algorithms as it is used to find the shortest path between two vertices and might not include all the vertices of the graph.
Google maps uses Dijkstra’s algorithm to find the shortest path to the destination.That’s probably why it makes you take the back alley’s which are barely big enough for a peanut to roll through.
Steps to execute Dijkstra’s Algorithm:
1.Initialize the distances according to the algorithm2. Pick the first node and calculate the distances to the adjacent nodes.3. Pick the next node with minimal distance; repeat adjacent node distance calculations and update their path lengths. The updation of path length is known as relaxation.4.Final result of shortest-path tree.
The following diagram will make the mechanics of the algorithm more clear.
There is one more very important greedy algorithm known as Huffman coding, but that is an entire article by itself so I’m not going to cover it in this one.
In conclusion greedy algortihms are extremely useful for finding the most optimal solutions, greedy algorithms can be used to find the best case and worst case scenarios and for the most part they give accurate results. Greedy algorithms are used in applications from navigation to compression, there are a load of uses for these algorithms.
References:
- Introduction To Algortihms C.L.R.S
- www.programiz.com
- www.brilliant.org
- www.hackerearth.com
