GREEDY ALGORITHMS
Firstly it’s better to get familiar with what actually are greedy algorithms . These are basically meant to solve optimization problems ,what is an optimization problem then? is the thing that strikes , it is basically a problem that is associated with an objective function called a value, a predicate P that represents feasibility criteria, a solution space of all possible solutions U, and an extremum .requirement . The main aim of solving an optimization problem is to find a set of feasible solutions that satisfies the predicate P and achieve the desired maximum.
A person that is associated with the computer science field deals with such optimization problems a lot of times for example storing files in a compressed form in a disk (taking into consideration the main aim of reducing space) etc.
ELEMENTS OF GREEDY ALGORITHMS
OBJECTIVE FUNCTION
The main objective of the greedy algorithm is what a objective function is basically , the objective function should be either maximized or minimized.
SELECTION PROCEDURE
The selection procedure is nothing but to choose the next item in the algorithm to be considered. This must be done based on greedy locally optimal criteria.
FEASIBILITY CHECK
It displays if the selected item is feasible as per the given constraint . If the constraint is satisfied then the item is added else rejected.
SOLUTION CHECK
Last but not the least , Solution check is to check whether the partial solutions together create a global solution for the given problem and if they do , a solution is returned.
SOME OF THE GREEDY ALGORITHMS
Kruskal’s algorithm
This algorithm first sorts the edges a graph based on the weight . Then , it adds sorted edges one by one , the addition of the edges must result in a non-cyclic form and if it becomes cyclic it is rejected. This algorithm is meant for constructing minimum spanning tree.
Prim’s Algorithm
It is an alternative way of creating a Minimum Spanning tree . Unlike Kruskal’s algorithm Prim’s algorithm starts with the edge.
Then all the neighbouring vertices are considered one by one and added using the greedy approach. As we can see in the example above the second picture is the prim’s minimum spanning tree of first picture.
Knapsack Problem
The objective of this problem is to pack objects of different sizes or volumes into a finite number of bins of certain capacity. The main objective of the problem is to minimization of space or maximization of profit.
Consider the problem having weights and profits are:
Weights: {2,3,4,5}
Profits: {3, 4, 5, 6}
The weight of the knapsack is 5 kg
The number of items is 4
The above problem can be solved by using the following method:
xi = {1, 0, 0, 1}
= {0, 0, 0, 1}
= {0, 1, 0, 1}
The above are the possible combinations. 1 denotes that the item is completely picked and 0 means that no item is picked. Since there are 4 items so possible combinations will be:
2⁴=16 ; So. There are 16 possible combinations that can be made by using the above problem.
Huffman Encoding algorithm
This algorithm is a greedy-based data compression algorithm and is used in effective storage and data transmission. It is based on the concept of prefix codes. The aim of the problem is to find optimal code.
Huffman coding is done with the help of the following steps-
- Calculate the frequency of each individual within the desk.
2.Sort the characters in increasing order of the frequency
3.Create an empty node X. Assign the minimum frequency to the left child of X and assign the second minimum frequency to the right child of X. Set the value of the X as the sum of the above two minimum frequencies.
4.For each non-leaf node, assign 0 to the left edge and 1 to the right edge
CONCLUSION
In this blog we noticed what are greedy algorithms. We been through a few examples of the issues solved using grasping approach. those algorithms need to have the components like optimization feature, constraints, selection procedure and answer test. but greedy algorithms aren’t usually the optimal manner, even after adjusting the order in their processing. Demonstrating the correctness of grasping algorithms (for exact or approximated solutions) can be very difficult. So, there are plenty of factors we will talk approximately grasping algorithms.