Greedy Algorithms

Greedy Algorithms for Problem Solving

.

“A Greedy algorithm is an approach to solving problems by making locally optimal (best) choices at each step with the hope of finding a global optimum (best) or near-best solution.”

In other words, it is a strategy that makes the best decision at each stage of a problem while not worrying about the consequences of those decisions on future steps.

.

Edsger W. Dijkstra, a computer scientist and mathematician who wanted to calculate a minimum spanning tree, introduced the term “Greedy algorithm”.

Dijkstra theorem (minimum spanning tree theorem) also was made by Edgser Dijkstra.

.

Characteristics of Greedy Algorithms

1. Choice of the Best Option – At each step, the algorithm selects the best available option based on a specific criterion. This choice is made without considering the impact of future selections.
2. Greedy Choice Property – The selected option should be the one that appears to be the most advantageous in the current context. This choice is based on some criteria or objective function.
3. Optimal Substructure – The problem must exhibit the property of optimal substructure, which means that finding an optimal solution to the problem involves finding optimal solutions to its subproblems.
4. Irrevocable Choices – Once a decision is made in a greedy algorithm, it is final and cannot be changed in subsequent steps.
5. Short Sightedness – The term “short-sighted” emphasizes that this algorithm doesn’t have a long-term vision or strategy. It’s like making decisions in the moment without thinking about how they might affect the bigger picture. While this approach can work well in some situations, it may not always lead to the best overall solution.

.

Optimal Reliability Problem

Greedy algorithms are often used to solve optimization problems, where the goal is to find the best solution among a set of feasible solutions.

While they are relatively simple and efficient, it’s important to note that greedy algorithms may not always produce globally optimal solutions.

In some cases, they can provide approximate solutions that are close to the optimal solution, while in others, they may fail to find the correct solution.

The effectiveness of a greedy algorithm depends on the problem at hand and the choice of the greedy criterion. It is crucial to analyse the problem’s properties and constraints to determine whether a greedy approach is appropriate and to design the greedy criterion carefully to achieve the desired results.

.

Applications of Greedy Algorithm

1. Activity Selection Problem

In this problem, you are given a set of activities, each with a start time and an end time. The goal is to select a maximum-sized subset of non-overlapping activities that can be performed without conflicting with each other, i.e., no two selected activities overlap in time.

.

2. Fractional Knapsack Problem

You are given a set of items, each with a weight (w) and a value (v), and a knapsack with a maximum weight capacity (W). The goal is to determine the most valuable combination of items to include in the knapsack without exceeding its weight capacity.

.

3. Minimum Spanning Tree

It involves finding the subset of edges in an undirected, connected graph that connects all the vertices while minimizing the total edge weight. Kruskal’s Algorithm and Prim’s Algorithm are two greedy problems.

.

4. Huffman Code

The Huffman coding problem is a well-known problem in computer science and information theory. It involves the compression of data by creating a variable-length prefix-free binary code, known as the Huffman code, to represent characters in a way that minimizes the total number of bits required for encoding.

.

5. Job Sequencing

you are given a set of jobs, each with a specific deadline and a profit or weight associated with it. The goal is to schedule these jobs on a single machine (or processor) in such a way that you maximize the total profit or minimize the total penalty.

.

6. Coin Change Problem

Determines the minimum number of coins needed to make change for a given amount. Greedily selects the largest coin denominations until the target amount is reached.