Introduction to Greedy Method and its Applications

Greedy Method

 

A greedy method is an approach or an algorithmic paradigm to solve certain types of problems to find an optimal solution. The approach of the greedy method is considered to be the easiest and simple to implement. 

 

The greedy method is used to solve the optimization problem which means the problem asks for either minimum result or the maximum result.

 

Example: 

 

Suppose there is a problem that ‘P’ wants to buy a car, now there can be multiple solutions to this problem, a car can be among an SUV, a sedan, or a hatchback.

---

---

There can be so many solutions to the problem, but then the problem is not the optimization problem, therefore we must apply some sort of constraint. 

 

Let’s suppose the problem is to buy the cheapest BMW SUV, now the solution will be-:

---

---

As we are left with the minimized solution, the problem becomes an optimization problem and the solution is known as the optimal solution. 

 

An optimal solution could only be one, if there is more than one solution, they are not optimal, such solutions are known as feasible solutions. The popular methods to solve an optimization problem are the greedy method, dynamic programming, and the branch of the bound method.

 

(Must read: What Does Probabilistic Programming Work?)

 

Greedy algorithms suggest the following approach-:

 

1. The given problem is solved one by one or in stages.

2. In each case, we will consider one input.

3. If the input is feasible, then we will include it in a solution.

4. All feasible solutions are kept together to find the optimum solution.

 

Therefore for the given problem, we will consider as many feasible solutions as possible, for a problem to have feasible solutions, there needs to be a constraint. However, it is clear that there should be a further constraint to provide an optimum solution out of the feasible solutions.

---

---

The above figure shows that the greedy algorithm tries to find the local best solutions in order to find the global optimal solution. Now, we shall learn about some of the advantages and disadvantages of this algorithmic paradigm.

 

Advantages of Greedy Method

 

1. The implementation of the greedy method is easy because it takes the best possible solution.

 

2. The greedy method is considered to be cheaper than most of the other algorithmic paradigms.

 

3. The time complexity of greedy algorithms is generally less which means that greedy algorithms are usually fast.

 

4. Greedy algorithms are used to find the optimal solution, therefore, it is used for optimization problems or near-optimization problems such as the NP-Hard problem.

 

(Related blog: Machine learning algorithms)

 

Disadvantages of Greedy Method

 

1. Sometimes the feasible solution may not lead to the optimal solution. 

 

For example-: consider we have to find the longest path from the root to the last level.

---

---

Now, the Greedy method will start from the root(5) and will go to the next level, the next level has two values, and the most feasible value in order to find the longest path would be 8, therefore, it will choose 8 in the next level. 

 

Lastly, the greedy method will choose out of 11 and 9, 11 is greater than 9, so the longest route according to the greedy algorithm would be as followed-:

---

---

The longest route according to the greedy algorithm is 5 + 8 + 11= 24, but this is not the optimal solution, the correct longest path would be as followed-:

---

---

The correct longest path or the optimal solution of the problem is 5 + 7 + 21 = 33. This is one of the major drawbacks of the greedy method.

 

Pseudocode for Greedy Method

 

def GA(a,n):

    for i in range(1,n):

        x = select(a)

 

        if x is feasible:

            solution = solution + x

 

The pseudo-code is pretty simple, there is a function GA that accepts two variables, ‘a’ and ‘n’ where ‘a’ represents an input and ‘n’ represents the size of the input.

 

The for loop is starting from the first input and goes to the total number of input or till the last input to cover everything. Inside the for loop, we are selecting one input and storing it in a variable ‘x’, if this variable ‘x’ is feasible, we will simply include it in the solution.

 

Dynamic Programming VS Greedy Method (Important Points)

 

1. Both dynamic programming and the greedy method are used as an algorithmic paradigm to solve optimization problems.

 

2. Dynamic programming assures the optimal solution as it works on the principle of optimality whereas as we have discussed in the drawbacks, there is no guarantee to find the optimal solution in the case of the greedy method.

 

3. The time complexity of greedy algorithms is less as compared to the algorithms that use dynamic programming.

 

4. Dynamic programming divides the problem into the sub-parts and remembers the solution of the sub-part to apply it later when a similar sub-part occurs again whereas the greedy algorithm finds the most feasible solution at every stage to get to the optimal solution.

 

Greedy Method VS Divide And Conquer (Important Points)

 

1. The purpose of the divide and conquer method is to find a solution, it does not matter if the solution is optimal or not whereas the purpose of the greedy method is to find an optimal solution.

 

2. The divide and conquer method divides the problem into sub-parts and solves each one of them separately, for example: Merge Sort, Binary search. On the other hand, the greedy method takes the easiest step while solving a problem without worrying about the complexity of the future steps.

 

3. In terms of time complexity, both the divide and conquer method and greedy method take polynomial time but the greedy method is considered to be faster than the divide and conquer method.

 

4. Divide and conquer solve each problem separately and if the same type of problem occurs, again and again, it solves them repeatedly. On the other hand, the greedy method doesn’t solve the previously solved sub-problem again.

 

Greedy Method Applications

 

1. The greedy method is used to find the shortest distance between two vertices with the help of Dijkstra’s algorithm.

 

2. The greedy method is highly used in the scheduling process in the CPU and to use the CPU to its maximum extent. The purpose of the greedy method here is to find an optimal solution to maximize CPU utilization. 

 

3. The greedy method is also used in the non-preemptive algorithm such as the shortest job first algorithm. This algorithm prioritizes the process with the lowest burst time.

 

4. The traveling salesman problem is another application of the greedy method, the objective here is to find the shortest path possible.

 

5. Few algorithms like the knapsack problem, bin packing problem, Egyptian fraction, and minimum spanning trees could be solved best using the greedy method.

 

In this blog, we learned about the working of the greedy method with the help of an example of an optimization problem. 

 

The later section of the blog includes the pseudo-code for the implementation of the greedy algorithm with the fair comparison of the greedy method with other approaches like dynamic programming and the divide and conquer method. The final section concluded the major applications of the greedy method or the major algorithms that use the greedy method.