What is Greedy approach and when to use it?

In some cases making a decision that looks right at that moment gives the best solution (Greedy), but in other cases it doesn’t. The Greedy technique is best suited for looking at the immediate situation.

Greedy Strategy- Greedy algorithms work in stages. In each stage, a decision is made that is good at that point, without bothering about the future. This means that some local best is chosen. It assumes that a local good selection makes for a global optimal solution.

Why to choose Greedy Approach?

The greedy approach has a few tradeoffs, which may make it suitable for optimization. One prominent reason is to achieve the most feasible solution immediately. In the activity selection problem (Explained below), if more activities can be done before finishing the current activity, these activities can be performed within the same time. Another reason is to divide a problem recursively based on a condition, with no need to combine all the solutions. In the activity selection problem, the "recursive division" step is achieved by scanning a list of items only once and considering certain activities.

What are the elements of Greedy Algorithms?

The two basic properties of optimal Greedy algorithms are:

1. Greedy choice property.
2. Optimal substructure.

Greedy choice property: This property says that the globally optimal solution can be obtained by making a locally optimal solution (Greedy). The choice made by a Greedy algorithm may depend on earlier choices but not on the future. It iteratively makes one Greedy choice after another and reduces the given problem to a smaller one.

Optimal substructure: A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the subproblems. That means we can solve subproblems and build up the solutions to solve larger problems.

NOTE: Making locally optimal choices does not always work. Hence, Greedy algorithms will not always give the best solutions.

Advantages and Disadvantages of Greedy Method-

The main advantage of the Greedy method is that it is straightforward, easy to understand and easy to code. In Greedy algorithms, once we make a decision, we do not have to spend time reexamining the already computed values. Its main disadvantage is that for many problems there is no greedy algorithm. That means, in many cases there is no guarantee that making locally optimal improvements in a locally optimal solution gives the optimal global solution.

Some of the applications of Greedy Approach:

1. Sorting: Selection sort, Topological sort
2. Priority Queues: Heap sort
3. Huffman coding compression algorithm
4. Prim’s and Kruskal’s algorithms
5. Shortest path in Weighted Graph [Dijkstra’s]
6. Coin change problem
7. Fractional Knapsack problem
8. Disjoint sets-UNION by size and UNION by height (or rank)
9. Job scheduling algorithm

NOTE: Greedy techniques can be used as an approximation algorithm for complex problems

Lets look at some examples to get its better understanding.

• Minimum Spanning Tree -> finding a spanning tree for a graph whose weight edges sum to a minimum value.

• Fractional Knapsack -> selecting a subset of items to load in a container in order to maximize profit.

• Task Selection -> finding a maximum set of non-overlapping tasks (each with a fixed start and finish time) that can be completed by a single processor

• Huffman Coding -> finding a code for a set of items that minimizes the expected code-length.

• Unit Task Scheduling with Deadlines -> finding a unit-length a task-completion schedule for a single processor in order to maximize the total earned profit.

• Single source distances in a graph -> finding the distance from a source vertex in a graph to every other vertex in the graph.

NOTE: Like all families of algorithms, greedy algorithms tend to follow a similar analysis pattern.

Basic Observations on Greedy Algorithms-

Greedy Correctness -> It is usually proved through some form of induction. For example, assume their is an optimal solution that agrees with the first k choices of the algorithm. Then show that there is an optimal solution that agrees with the first k + 1 choices.

Greedy Complexity -> The running time of a greedy algorithm is determined by the ease in maintaining an ordering of the candidate choices in each round. This is usually accomplished via a static or dynamic sorting of the candidate choices.

Greedy Implementation -> Greedy algorithms are usually implemented with the help of a static sorting algorithm, such as Quicksort, or with a dynamic sorting structure, such as a heap. Additional data structures may be needed to efficiently update the candidate choices during each round.