Greedy Approach
GREEDY METHOD
What is greedy approach?
This approach is used to find the optimal solution from the set of obtained feasible solutions. We use objective function to find the optimal solutions. It find the solution in the ste-by-step manner. This will be obtained in a sequential greedy approach.
Key-words used in the greedy method
Objective function: it is a function which maximizes or minimizes the output.
Optimal solution: it is a feasible solution which maximizes or minimizes the objective function.
Feasible solution: it is a solution which is obtained as the result of the objective function.
Pseudo representation of greedy algorithm:
Algorithm Greedy (a, n)
{
Solution=ϕ // Initialize solution
for i=1 to n do
{
X: = Select (a);
if Feasible (solution, x) then
Solution =Union (solution, x)
}
return solution;
}
Job scheduling using greedy approach:
In this problem we are given with the deadlines and the priority of each and every individual jobs, we have to find out which jobs are to be finished in the given consolidated time, so that the high profit jobs will completed in that stipulated time. We have to find this using the greedy approach.
Example:
Number of jobs will be 4
Priorities will be (p_{1}, p_{2}, p_{3}, p_{4}) = (100,10,15,27)
Deadlines will be (d_{1}, d_{2}, d_{3}, d_{4}) = (2, 1, 2, 1)
Maximum deadline is 2
SNO |
FEASIBLE SOLUTION |
PROCESSING SEQUENCE |
VALUE |
1 |
(1,2) |
2,1 |
110 |
2 |
(1,3) |
1,3 or 3, 1 |
115 |
3 |
(1,4) |
4, 1 |
127 |
4 |
(2,3) |
2, 3 |
25 |
5 |
(3,4) |
4,3 |
42 |
6 |
(1) |
1 |
100 |
7 |
(2) |
2 |
10 |
8 |
(3) |
3 |
15 |
9 |
(4) |
4 |
27 |
The job with the less deadline must be finished first, and then the job with the highest, this can be seen in the 1^{st} case, second job is with 1 unit of dead line, so it will we executed before 1.
When compared the value column, the highest value will be 3^{rd} row, which consists of 1 and 4, the sequence would be 4,1 because 4^{th} job having the less dead line than the 1^{st} .
Solving problem of knapsack with greedy approach
In this we will be given a knapsack which has some capacity to hold the goods having some weights. We will be given with the weight and the price of every item, based on that we have to fill the knapsack with the optimal commodities. In between we will get some feasible solutions, out of them we have to choose the optimal solution.
Example:
n= 3,
weight of knapsack(m)=20
(p_{1},p_{2},p_{3}) = (25,24,15)
(w_{1},w_{2},w_{3}) = (18,15,10)
Note down the items in the decreasing order of their profits.
Selection set will be w1, w2, and w3.
ITRM |
PROFIT |
WEIGHT |
REMAINING WEIGHT |
1 |
25 |
18 |
20-18=2 |
2 |
24 |
15 |
Remaining is 2, so cannot be put into bag |
So, optimal solution is only placing item1 in the knapsack.
Huff-man coding
It is used for the compression of code, in this we will be given with the string, out of which we have to find out the frequencies of every letter.
Example:
O P E N S E N S E
Mark o on left and 1 on right
Write the code by travelling in top down approach.
By applying the Huffman coding principles, take the least two frequencies first,
take the next least frequency N or S.
Check for the frequency which is greater than 4, if found go with adding in the left side, else split the tree.
Repeat the process same for the next two frequencies.
Done with all the nodes, so combine the two trees,
Now make the table with the modified code value,
ALPHABET |
CODE |
FREQUENCY |
TOTAL BITS |
O |
110 |
1 |
1*3 |
P |
111 |
1 |
1*3 |
E |
01 |
3 |
3*2 |
N |
10 |
2 |
2*2 |
S |
00 |
2 |
2*2 |
By this the length is reduced by 7 units.
MINIMUM SPANNING TREE
The tree is a connected graph with no cycles is formed in it. if G(V, E) be an undirected connected graph. A sub graph t = (V,E^{I }) of G is a spanning tree of G iff t is a tree. The spanning tree consists of all the vertices in the graph.
The given graph consists of so many spanning trees, but the graph which has the least cost is considered to be the minimum spanning tree.
Algorithms used to find the minimum spanning tree
- Prims
- Kruskal
Prims
Steps involved in finding the minimum spanning tree:
- Start the procedure with the selection the edge which has the minimum weight.
- Select the next edge which consists of two vertices among which one is already included in the tree and the other is not.
- Repeat the process until the tree contains n-1 edges.
Time complexity of prim’s algorithm is O(n^{2}).
Example:
Kruskal algorithm
Steps involved in finding the minimum spanning tree:
- Start the procedure with the selection the edge which has the minimum weight.
- Select the next minimum edge
- Repeat the process until the tree contains n-1 edges.
Time complexity of prim’s algorithm is O(ElogE).
Example: