Greedy Algorithm Introduction

"Greedy Method finds out of many options, but you have to choose the best option."

In this method, we have to find out the best method/option out of many present ways.

In this approach/method we focus on the first stage and decide the output, don't think about the future.

Thus, it aims to find the local optimal solution at every step so as to find the global optimal solution for the entire problem.

                 Consider that there is an objective function that has to be optimized (maximized/ minimized). This approach makes greedy choices at each step and makes sure that the objective function is optimized.

The greedy algorithm has only one chance to compute the optimal solution and thus, cannot go back and look at other alternate solutions.

 However, in many problems, this strategy fails to produce a global optimal solution. 

Let's consider the following binary tree to understand how a basic greedy algorithm works:

For the above problem the objective function is:

To find the path with largest sum.

Since we need to maximize the objective function, Greedy approach can be used. Following steps are followed to find the solution:

Step 1: Initialize sum = 0

Step 2: Select the root node, so its value will be added to sum, sum = 0+8 = 8

Step 3: The algorithm compares nodes at next level, selects the largest node which is 12, making the sum = 20.

Step 4: The algorithm compares nodes at the next level, selects the largest node which is 10, making the sum = 30.

Thus, using the greedy algorithm, we get 8-12-10 as the path. But this is not the optimal solution, since the path 8-2-89 has the largest sum ie 99.

This happens because the algorithm makes decision based on the information available at each step without considering the overall problem.

Advantages of Greedy Approach/Technique

• This technique is easy to formulate and implement.
• It works efficiently in many scenarios.
• This approach minimizes the time required for generating the solution.

Now, let's see a few disadvantages too,

Disadvantages of Greedy Approach/Technique

• This approach does not guarantee a global optimal solution since it never looks back at the choices made for finding the local optimal solution.

Example:

1. machine scheduling
2. Fractional Knapsack Problem
3. Minimum Spanning Tree
4. Huffman Code
5. Job Sequencing
6. Activity Selection Problem

Elements of the greedy strategy

A greedy algorithm obtains an optimal solution to a problem by making a sequence of choices. For each decision point in the algorithm, the choice that seems best at the moment is chosen. This heuristic strategy does not always produce an optimal solution, but as we saw in the activity-selection problem, sometimes it does. This section discusses some of the general properties of greedy methods.
How can one tell if a greedy algorithm will solve a particular optimization problem? There is no way in general, but there are two ingredients that are exhibited by most problems that lend themselves to a greedy strategy: the greedy-choice property and optimal substructure.

Greedy-choice property

                        The first key ingredient is the greedy-choice property: a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
 Here is where greedy algorithms differ from dynamic programming. 
In dynamic programming, we make a choice at each step, but the choice may depend on the solutions to subproblems.
 In a greedy algorithm, we make whatever choice seems best at the moment and then solve the subproblems arising after the choice is made. 
The choice made by a greedy algorithm may depend on choices so far, but it cannot depend on any future choices or on the solutions to subproblems. 
Thus, unlike dynamic programming, which solves the subproblems bottom up, a greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, iteratively reducing each given problem instance to a smaller one.

Optimal substructure

A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. 
This property is a key ingredient of assessing the applicability of dynamic programming as well as greedy algorithms.
 As an example of optimal substructure, that if an optimal solution A to the activity selection problem begins with activity 1, then the set of activities A' = A - {1} is an optimal solution to the activity-selection problem S' = {i  S : s_i  â₁}.