Algorithm Design : What Is Greedy Techniques

1. Introduction to the Greedy Technique

In the field of algorithm design and optimization, greedy techniques stand as a powerful strategy for decision making that leads to efficient solutions. Rooted in the principle of making locally optimal choices at each step, greedy techniques provide a simple but effective approach to solving a wide range of optimization problems. From finding shortest paths in graphs to creating optimal binary codes for data compression, greedy techniques have found applications in various fields of computer science and beyond.

1.1 Algorithm: Greedy Technique

1. Initialization: Initialize an empty solution set (S) to store the selected elements.
2. Greedy Choice: At each step, choose the locally optimal element based on a predefined criterion.
3. Feasibility: Ensure that the chosen element does not violate any constraints or conditions imposed by the problem.
4. Update: Add the chosen element to the solution set (S).
5. Termination: Repeat steps 2-4 until a termination condition is met, such as reaching the desired solution or exhausting the input set.
6. Output: Return the solution set (S) containing the locally optimal choices.

1.2 Understand Greedy technique With A Classic Problem : the Coin Change Problem

Problem Statement:

You are a cashier in a store, and a customer wants to leave a certain amount of change using the least amount of coins possible. You have an unlimited supply of coins of different denominations. The task is to determine the minimum number of coins required to make the desired change.

Example:

Let’s say the customer needs to make a change of ₹63, and you have the following denominations of coins available: ₹1, ₹5, ₹10, and ₹25.

Solution:

1. Sort the denominations of coins in descending order: Sort the denominations of coins in non-ascending order: ₹25, ₹10, ₹5, and ₹1. This sorting step ensures that we give priority to using higher denomination coins first.
2. Select coins repeatedly: Starting with the highest denomination coin, repeatedly use the largest possible denomination coin until the desired change is achieved.
   • Step 1: Select 1 coin of denomination ₹25. Remaining change: ₹63 – ₹25 = ₹38.
   • Step 2: Select 1 coin of denomination ₹25. Remaining change: ₹38 – ₹25 = ₹13.
   • Step 3: Select 1 coin of denomination ₹10. Remaining change: ₹13 – ₹10 = ₹3.
   • Step 4: Select 1 coin of denomination ₹1. Remaining change: ₹3 – ₹1 = ₹2.
   • Step 5: Select 1 coin of denomination ₹1. Remaining change: ₹2 – ₹1 = ₹1.
   • Step 6: Select 1 coin of denomination ₹1. Remaining change: ₹1 – ₹1 = ₹0.
3. Count the total number of coins used: In this case, 6 coins were used: Two ₹25 coin, one ₹10 coin, and Three ₹1 coins.

1.3 Characteristics of Greedy Algorithms:

1. Greedy Choice Property: A greedy algorithm always makes a locally optimal choice at each step, without reconsidering previous decisions.

2. Optimal substructure: If a globally optimal solution can be constructed from locally optimal solutions, then greedy algorithms exhibit optimal substructure.

3. Feasibility: Greedy algorithms ensure that the elements chosen satisfy any feasibility conditions imposed by the problem.

4. Iterative improvement: Greedy algorithms iteratively construct the solution by adding locally optimal alternatives until the termination condition is met.

1.4 Optimal Solution in Greedy Algorithm:

In the context of greedy algorithms, the term “optimal solution” generally refers to a solution that is globally optimal, meaning that it provides the best possible outcome for a given problem instance. However, it is important to note that while greedy algorithms often yield solutions that are close to optimal, they do not always guarantee a completely optimal solution for every problem.

1.5 The concept of optimality in greedy algorithms is typically understood in two ways:

1. Locally optimal choice: Greedy algorithms make locally optimal choices at each step, selecting the best option available without considering the entire solution space. The optimality of these choices ensures that, at each step, the element chosen contributes to a solution that appears to be the best choice at that time.
2. Optimal substructure: Greedy algorithms exhibit optimal substructure if the locally optimal choices made at each step lead to a globally optimal solution. This means that the optimal solution to the entire problem can be constructed from the local optimal solutions of its subproblems.

For More Update Visit intelipariksha