Let us consider the example of the container loading problem.<\/p>\n
In a container loading problem, a large ship is loaded with cargo. The cargo has containers of equal sizes but different weights. The cargo capacity is of the ship is cp.<\/p>\n
We need to load the containers in the ship in such a way that the ship has maximum containers.<\/p>\n
For example, let us say there are a total of 4 containers with weights: w1=20, w2=60, w33=40, w4=25.<\/p>\n
Let cp = 80. Then, to load maximum containers we will load container-1,3,4.<\/p>\n
We will load the containers in the order of increasing weights so that maximum containers load inside the ship. Here, the order of loading is container1\u2192container4\u2192container3.<\/p>\n The greedy algorithm was first coined by the Dutch computer scientist and mathematician Edsger W. Dijkstra when he wanted to calculate the minimum spanning tree. The major purpose of many greedy algorithms was to solve graph-based problems.<\/p>\n The greedy algorithms first started coming into the picture in the 1950s. The then scientists, Prim and Kruskal also achieved the optimization techniques for minimizing the costs of graphs during that decade.<\/p>\n A few years later, in the 1970s, many American researchers proposed a recursive strategy for solving greedy problems. In 2005, the NIST records registered the greedy paradigm as a separate optimization strategy.<\/p>\n Since then, the greedy algorithm has been extensively in use in multiple fields including the web protocols such as the open-shortest-path-first (OSPF) and many other network packet switching protocols.<\/p>\n The greedy algorithm works in various stages and considers one input at a time while proceeding.\u00a0At each stage, we try to find a feasible solution for our problem, a solution that is good for the algorithm at that point.\u00a0This means that we make a locally optimal choice for each sub-task.\u00a0These local optimal choices eventually lead us to the global optimal choice for our problem which we call the final optimal solution.<\/p>\n The pseudo-code for the simplest greedy algorithm is shown below:<\/p>\n Here, A = an array of size n.<\/p>\n The select function takes an input from the array and removes it. We assign this selected input value to x.<\/p>\n Feasible is the boolean function that decides whether we can include x in the final solution vector or not. A good greedy algorithm has a proper implementation of select, Feasible and Union.<\/p>\n There are many techniques to solve a problem. Out of these many techniques, we have optimization techniques for a particular set of problems. Out of optimization techniques as well, there are multiple choices.<\/p>\n So, how do we know that when to use and when not to use the greedy method as an optimization algorithm.<\/p>\n For this purpose, we will check the properties of the algorithm. If the following two properties hold, we will use the greedy approach or other approaches.<\/p>\n To reach the final optimal solution or the globally optimal solution, we find locally optimal solutions(the best at that moment) for each sub-task.<\/p>\n A solution to the subproblem of an optimal solution is also always optimal.<\/p>\n 1. In the greedy method, we divide the main problem into sub-problems and solve each of them recursively.<\/p>\n 2. The greedy method maximizes the resources in a given time constraint.<\/p>\n 3. There is a cost and value attribution attached to these resources.<\/p>\n The greedy algorithm proceeds by making feasible choices at each step of the whole process. Feasible choices are those which satisfy all the algorithmic constraints.<\/p>\n Choose what is best at the given time i.e. make locally optimal choices while preceding through the algorithm.<\/p>\n We cannot alter any sub-solution at any subsequent point of the algorithm while execution.<\/p>\n Greedy algorithms always choose the best possible solution at the current time. This sometimes leads to overall bad choices and might give worst-case results.<\/p>\n For example, Suppose we wish to reach a particular destination and there are different paths for it, as shown below:<\/p>\n Here, following path \u2018A\u2019 will cost us 50, path \u2018B\u2019 will cost 8(minimum) and path \u2018C\u2019 will cost us 80.<\/p>\n If we follow the greedy approach, we will first move from starting point to node \u2018C\u2019 because it has the minimum cost at that point. But in reality, this path has the maximum total cost. However, we were not able to detect it at the first step.<\/p>\n Following the greedy method will cost us the maximum here i.e. 80. In such cases, the greedy approach might not give optimal results.<\/p>\n So the question arises- When to use the greedy approach.<\/p>\n We use this technique because it gives optimal results in many cases by just making \u2018layman moves\u2019. We also prefer greedy methods whenever we are sure that they will provide us with good approximations. In such cases, the greedy approach proves to be very effective as it is cheaper and faster.<\/p>\n 1. It is a highly optimized and one of the most straightforward algorithms.<\/p>\n 2. This algorithm takes lesser time as compared to others because the best solution is immediately reachable.<\/p>\n 3. In the greedy method, multiple activities can execute in a given time frame.<\/p>\n 4. We don\u2019t need to combine the solutions of sub-problems, as it automatically reaches the optimal solution.<\/p>\n 5. The algorithm is easy to implement.<\/p>\n There are multiple applications of the greedy technique such as:<\/p>\n CPU scheduling is a process that allows and schedules more than one processes in a CPU at a time so that there is maximum utilization of the CPU.<\/p>\n This usually happens when one process is on hold due to the unavailability of resources, and to avoid CPU time wastage, we schedule a new process for the time.<\/p>\n Multiple algorithms help in CPU scheduling and they make use of the greedy approach. The purpose of these algorithms is to maximize CPU utilization and minimize the time taken by a process to execute. As the name suggests, it schedules processes based on first come first serve. It is a non-preemptive algorithm.<\/p>\n It is both preemptive as well as non-preemptive scheduling algorithm. In this algorithm, we give the highest priority to process with the lowest burst time. Its preemptive version is known as the Shortest job first algorithm.<\/p>\n It is both preemptive or non-preemptive. In this technique, we assign priority to every process and then execute in the priority order. It mostly uses a priority queue for execution.<\/p>\n In this algorithm, we assign a fixed time slot to each process. If the process does not execute completely in that time slot, it will complete its remaining execution in the next rounds. It is preemptive.<\/p>\n This is also a priority-based algorithm. It maintains multiple queues for the processes with different priorities.<\/p>\n A minimum spanning tree is a subset of a connected, weighted undirected graph that connects all the vertices without cycle. In MST, the total weight of all the edges is minimum.<\/p>\n This algorithm is used to find the shortest path between two vertices in a graph in such a way that the sum of weights between the edges is minimum. All those algorithms in which we need to maximize or minimize something make use of the greedy approach.<\/p>\n This algorithm allocates different memory blocks to the processes in an operating system.<\/p>\n In the fit algorithm, we make use of a pointer to keep track of all memory blocks available to us. The pointer also decides whether to accept or reject the request for memory block allocation for any incoming process. It makes this decision depending on three different fit memory management algorithms:<\/p>\n The pointer allocates that memory block to the process which it first finds to be sufficient for the process.<\/p>\n The algorithm allocates the minimum sufficiently available memory block to the process.<\/p>\n It allocates the largest sufficient memory block available in the memory.<\/p>\n This is one of the standard problems that a greedy algorithm solves. In this problem, our objective is to make use of the greedy technique to find the shortest possible path. The objective is to visit each city exactly once and then return to the initial starting point.<\/p>\n It is an optimization problem. In the fractional knapsack problem, we try to find a subset of items out of the total possible set of items. We ensure that their total weight is less than or equal to a given limit according to the problem. We also ensure that their value is maximum.<\/p>\n It is a finite sum of unique distinct fractions. We can represent every positive fraction as a sum of unique unit fractions which we call the Egyptian fraction.<\/p>\n In the bin packing problem, we have a finite number of bins of fixed volume. We pack items of different volumes into those bins in such a way that we use the minimum number of bins.<\/p>\n The greedy method works by finding the best possible outcome at every step of the algorithm. This sometimes leads to inaccurate results.<\/p>\n For example, suppose we wish to find the longest path in the following graph:<\/p>\n If we follow the greedy approach, we will make the best possible choice at every node.\u00a0In that case, the path will come out to be: 12\u219216\u21926\u219235 which comes out to be 69.<\/p>\n However, in reality, the actual longest path is 12\u21924\u219222\u219298 which comes out to be 136. Here, achieving 136 is impossible using the greedy approach. In this case, the greedy algorithm gave the wrong results.<\/p>\n The greedy method is well versed to solve multiple types of problems. Some of them are:<\/p>\n 1. Fractional knapsack problem<\/p>\n 2. Prim\u2019s algorithm<\/p>\n 3. Dijkstra\u2019s algorithm<\/p>\n 4. Kruskal\u2019s algorithm<\/p>\n 5. Activity search problem<\/p>\n 6. Huffman coding<\/p>\n 7. Travelling salesperson problem<\/p>\n 8. Ford- Fulkerson algorithm<\/p>\n 9. Boruvka\u2019s algorithm<\/p>\n Let us discuss all of these in detail.<\/p>\n It is an optimization problem in which we can select fractional items rather than binary choices. The objective is to obtain a filling knapsack that maximizes the total profit earned.<\/p>\n Step 1:<\/strong> Calculate the ratio of value overweight for every item. If the weight is in pounds, calculate the value per pound.<\/p>\n Step 2:<\/strong> Sort the items depending on the ratio calculated in step 1.<\/p>\n Step 3:<\/strong> Take the item with the highest ratio i.e. take the maximum possible value of substance with the maximum value per pound.<\/p>\n Step 4:<\/strong> Suppose that the amount that we took in step 3 exhausts but we still have space. Then, we will take the further possible amount of substance with the further maximum value of weight. Algorithm:<\/b><\/p>\n It is a greedy algorithm to obtain a minimum spanning tree. Its time complexity is of the order O(n2).<\/p>\n This algorithm builds the tree edge by edge, where it chooses the edge based on some optimization criterion. One of the criteria is to choose an edge in such a way that the increase in the sum of costs of edges is minimum.<\/p>\n The algorithm takes the input in the form of a graph. It then chooses the subset of edges of the graph in such a way that<\/p>\n a. The graph forms a tree including every vertex Algorithm :<\/strong><\/p>\n The steps are as follows:<\/p>\n 1: Initialize a vertex for the minimum spanning tree.<\/p>\n 2: Search for all the edges that connect the tree to new vertices.<\/p>\n 3: Find the minimum of all those selected edges.<\/p>\n 4: Add this value to the tree.<\/p>\n 5: We will perform the above steps recursively to reach the minimum spanning tree.<\/p>\n Stages in Prim\u2019s algorithm:<\/strong><\/p>\n Let us look through an example to understand the stages in Prim\u2019s algorithm:<\/p>\n Consider the following graph.<\/p>\n 1. Select any random vertex, say \u2018A\u2019 here.<\/p>\n 2. Select the edge with the minimum weight from this node and add it to the existing node.<\/p>\n 3. Choose the nearest vertex that we can include.<\/p>\n 4. Repeat these above steps recursively to obtain based on the minimum spanning tree.<\/p>\n The various stages of spanning tree will be:<\/p>\n The final obtained spanning tree is:<\/p>\n In a graph, there can exist multiple paths between a pair of vertices.\u00a0But, if we wish o find the shortest possible path between any two vertices, we make use of Dijkstra\u2019s algorithm.\u00a0It may or may not include all the vertices.<\/p>\n It is somewhat similar to Prim\u2019s algorithm and is used to find the shortest path just like Pri\u2019s algorithm.<\/p>\n While executing, it maintains two different sets. One set contains those vertices which we have included in the shortest path. The other set contains the remaining vertices, which we haven\u2019t included yet.<\/p>\n For example:<\/strong><\/p>\n 1. Consider the following graph:<\/p>\n 2. Select any vertex randomly. Consider it as the starting vertex.<\/p>\n Consider the remaining vertices to be at an infinite distance from the starting vertex.<\/p>\n 3. From the starting vertex, traverse to every immediate vertex. As we reach the particular vertex, we update its path in our graph.<\/p>\n If the adjacent path of a particular vertex is greater than the current path, do not update the values.<\/p>\n 4. Repeat step 3.<\/p>\n Do not change or update the path of those nodes which we have already visited once.<\/p>\n 5. Check if there is still any unvisited node in the graph or not. If an unvisited node still exists, select the path with the shortest possible distance to reach that node.<\/p>\n This is how we calculate the shortest path using Dijkstra\u2019s algorithm.<\/p>\n It is another possible interpretation to find out the minimum spanning tree in a graph. A minimum spanning tree always has one edge less than the number of edges in the graph. Algorithm:<\/strong><\/p>\n 1. Sort all the edges of the graph in non-descending order of their weights.<\/p>\n 2. Take the smallest edge.<\/p>\n 3. Check whether it is forming a cycle or not with the spanning-tree formed so far.<\/p>\n 4. If a cycle is found, discard this particular edge leading to the cycle. If there is no cycle, include the edge in the spanning tree.<\/p>\n 5. Repeat the above steps until we have included all the vertices.<\/p>\n Example:<\/strong><\/p>\n Consider the following graph:<\/p>\n a. We need to find the minimum spanning tree for this graph using Kruskal\u2019s algorithm.<\/p>\n b. Select the edge having minimum weight. If multiple edges are having minimum weight, choose any one of them randomly.<\/p>\n c. Select the next shortest edge with the next minimum weight. Add it to the spanning tree.<\/p>\n d. Select the subsequent edges, in the same manner, depending on their weights.<\/p>\n e. Make sure that none of the added edges forms a cycle.<\/p>\n f. Repeat the above steps until we get our desired spanning tree.<\/p>\n Thus, the various stages of Kruskal\u2019s algorithm are as follows:<\/p>\n It is an optimization problem. This algorithm selects non-conflicting activities which we can perform in the given time frame. This problem schedules activities in the given intervals in such a way that maximum activities can be performed in the given time constraint.<\/p>\n Example:<\/strong><\/p>\n 1. Let there be \u2018n\u2019 activities ranging from 1 to n in a given set i.e. let S = {1,2,3,4,5,………,n-1, n}.<\/p>\n 2. Only one activity can use a resource at a time i.e. the resources are non-sharable.<\/p>\n 3. Let the start time for these \u2018n\u2019 activities be s1, s2, s3, s4,……sn.<\/p>\n 4. Let the finish time of these activities be f1, f2, f3,f4,……….fn.<\/p>\n 5. Consider two random activities \u2018i\u2019 and \u2018j\u2019. Then, let the interval of activity \u2018i\u2019 be [si, fi) and the interval of activity \u2018j\u2019 be (sj, fj).<\/p>\n In this case, activities \u2018i\u2019 and \u2018j\u2019 will be compatible only when their intervals i.e. [si, fi) and (sj, fj) respectively, do not overlap.<\/p>\n Let us consider an example to understand the activity\/task scheduling problem.<\/span><\/p>\n Suppose there are 7 tasks named a,b,c,d,e,f,g.<\/span><\/p>\n The following table gives the starting and finishing time for each task:<\/span><\/p>\n Our objective is to assign these tasks to the computer in such a way that no two tasks overlap. We can make use of multiple machines. But since this is a greedy approach, we need to minimize the number of machines that we use for performing these tasks.<\/p>\n Initially, we will consider that the number of machines used = number of tasks i.e. we are assigning each task to an individual machine. In this case, the number of machines = 7(M1, M2, M3, M4, M5, M6, M7).<\/p>\n We will try to optimize the problem by minimizing the number of machines and at the same time, prevent overlapping. Thus, the final optimized schedule will be:<\/p>\n This table shows that \u2018a\u2019 occurs 45 times in the string, \u2018e\u2019 occurs 13 times and so on.<\/span><\/p>\n Here, a occurs maximum number of times, therefore it will have the lowest code.<\/span><\/p>\n Total bits required:= ( 45*1+13*4+12*4+14*3+16*3 )*1000 = 210,000 bits.<\/span><\/p>\n Fixed length Code:<\/strong><\/p>\n It assigns 3 bits to each character. Thus, for the whole file, we will need 3 x 106 bits.<\/p>\n Variable-length code:<\/strong><\/p>\n It assigns long bits to less frequent characters and short bits to more frequent characters.<\/p>\n Huffman Coding Algorithm:<\/strong><\/p>\n This problem states that there is a salesman who needs to visit a given set of cities starting from a particular city. We need to design the algorithm in such a way that the salesman cannot visit a city more than once. Also, he needs to return to the starting point after visiting all the cities.<\/p>\n We need to find the minimum possible path for the salesman to travel across all the cities. We make use of an adjacency matrix to depict the connected cities.<\/p>\n Consider a set of N cities- C1, C2, C3\u2026…Cn. let the cost of travelling be Tij for travelling between Ci and Cj.<\/p>\n The adjacency matrix for the above path will be as follows:<\/p>\n![\"Greedy](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/06\/Greedy-method-normal-image.jpg\")
<\/a><\/p>\nHistory of Greedy Algorithm<\/h3>\n
Working of Greedy Algorithm<\/h3>\n
ALgorithm Greedy(A,n)\n{\n solution := \u03d5; \/\/Initializing the solution\n for i:= 1 to n do\n {\n x := select(A);\n if Feasible(solution,x) then\n solution := Union(solution, x);\n }\n return solution;\n}\n<\/pre>\nProperties required for the Greedy Algorithm<\/h3>\n
1. Greedy choice property<\/h4>\n
2. Optimal sub-programs<\/h4>\n
Characteristic of a Greedy Approach<\/h3>\n
Steps to achieve Greedy Algorithm<\/h3>\n
1. Feasible<\/h4>\n
2. Local optimal choice<\/h4>\n
3. Unalterable<\/h4>\n
When to use Greedy Algorithm?<\/h3>\n
<\/a><\/p>\nAdvantages of Greedy Algorithm<\/h3>\n
Applications of Greedy Method<\/h3>\n
1. CPU Scheduling algorithms<\/h4>\n
\nThere are various types of scheduling algorithms:<\/p>\na. First come first serve<\/h5>\n
b. Shortest job first<\/h5>\n
c. Priority scheduling<\/h5>\n
d. Round-robin scheduling<\/h5>\n
e. Multiple level queue schedule<\/h5>\n
2. Minimum spanning trees<\/h4>\n
3. Dijkstra shortest path algorithm<\/h4>\n
4. Fit algorithm in memory management<\/h4>\n
a. First fit algorithm<\/h5>\n
b. Best fit algorithm<\/h5>\n
c. Worst fit algorithm<\/h5>\n
5. Travelling salesman problem<\/h4>\n
6. Fractional knapsack problem<\/h4>\n
7. Egyptian fraction<\/h4>\n
8. Bin packing problem<\/h4>\n
Limitations of Greedy Algorithm<\/h3>\n
<\/a><\/p>\nProblems solved by Greedy Method<\/h3>\n
<\/a><\/p>\n1. Fractional Knapsack Problem<\/h4>\n
\ni.e. we will take the next highest ratio.<\/p>\nfractional_knapsack (array w, array v, int C)\n{\n for i= 1 to size (v) do\n for i= 1 to size (v);\n sort_descending (vpp);\n i := 1;\n while (C>0) do{\n amt = min (C, w [i]);\n sol [i] = amt;\n C= C - amt;\n i := i+1;\n }\n return sol;\n}\n<\/pre>\n2. Prims algorithm<\/h4>\n
\nb. The graph has the minimum sum of weight among all the subtrees.<\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n3. Dijkstra\u2019s algorithm<\/h4>\n
<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n4. Kruskal algorithm<\/h4>\n
\nThis algorithm also ensures that there are no loops created on adding edges to the tree.<\/p>\n<\/a><\/p>\n<\/a><\/p>\n5. Activity search problem<\/h4>\n
Activity search problem Algorithm:<\/strong><\/h4>\n
Algorithm Activity_Selector(s, f)\n{\n n := len[s];\n A := {1};\n j := 1;\n for i := 2 to n do{\n if (si \u2265 fi) then\n A := A U {i};\n j := i;\n }\n return A;\n}\n<\/pre>\n\n\n
\n TASK<\/b><\/td>\n START TIME<\/b><\/td>\n FINISH TIME<\/b><\/td>\n<\/tr>\n \n a<\/span><\/td>\n 0<\/span><\/td>\n 2<\/span><\/td>\n<\/tr>\n \n b<\/span><\/td>\n 3<\/span><\/td>\n 7<\/span><\/td>\n<\/tr>\n \n c<\/span><\/td>\n 4<\/span><\/td>\n 7<\/span><\/td>\n<\/tr>\n \n d<\/span><\/td>\n 9<\/span><\/td>\n 11<\/span><\/td>\n<\/tr>\n \n e<\/span><\/td>\n 7<\/span><\/td>\n 10<\/span><\/td>\n<\/tr>\n \n f<\/span><\/td>\n 1<\/span><\/td>\n 5<\/span><\/td>\n<\/tr>\n \n g<\/span><\/td>\n 6<\/span><\/td>\n 8<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \n\n
\n Character<\/b>\u00a0<\/span><\/td>\n a<\/span><\/td>\n e<\/span><\/td>\n i<\/span><\/td>\n o<\/span><\/td>\n u<\/span><\/td>\n<\/tr>\n \n frequency<\/b><\/td>\n 45<\/span><\/td>\n 13<\/span><\/td>\n 12<\/span><\/td>\n 14<\/span><\/td>\n 16<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \n\n
\n Character\u00a0<\/span><\/td>\n code<\/span><\/td>\n<\/tr>\n \n a<\/span><\/td>\n 0<\/span><\/td>\n<\/tr>\n \n e<\/span><\/td>\n 101<\/span><\/td>\n<\/tr>\n \n i<\/span><\/td>\n 110<\/span><\/td>\n<\/tr>\n \n o<\/span><\/td>\n 100<\/span><\/td>\n<\/tr>\n \n u<\/span><\/td>\n 111<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Huffman_codes(C)\n{\n n=|C|;\n Q := C;\n for i=1 to n-1 do{\n z= allocate-Node ();\n x = left[z]=Extract-Min(Q);\n y= right[z] =Extract-Min(Q);\n arr [z]=arr[x]+arr[y];\n Insert (Q, z);\n }\n return Extract-Min (Q);\n}\n<\/pre>\n7. Travelling Salesman Problem<\/h4>\n
<\/a><\/p>\n