Greedy Method in Daa: Types, Steps, Examples

Greedy algorithm is a solution strategy such that each step or choice in the solution procedure is the best. The greedy algorithm never looks back and how the current choice might affect the next steps is never considered; it makes choices that seem best at the time. The algorithm takes a series of steps which it thinks will result in the best solution, but without considering the long-term consequences of these steps.

Greedy algorithms are used chiefly for greedy-choice property problems and optimal substructure problems. The greedy-choice property ensures optimal choices leading to a globally optimal solution. In contrast, optimal substructure indicates that optimal solutions for the problem can be constructed efficiently from optimal subproblem solutions.

Here  are the types of greedy algorithms such as:

1. Fractional Greedy Algorithms

Fractional greedy algorithms choose the optimum option in each step, following the ability to divide objects. Fractional greedy algorithms solve problems that divide resources or objects into fractions. The goal is to obtain a maximal solution by choosing the optimal portions of existing resources. A classic example is the Fractional Knapsack Problem in which objects can be incorporated partially depending on their value/weight ratio.

2. Pure Greedy Algorithms

Pure greedy algorithms choose the best option at every step without considering future consequences. The moment a decision is taken, it cannot be reversed, and there is no chance of backtracking. Such algorithms are concerned with selecting locally optimal solutions for every step, hoping that these selections will result in globally optimal solutions. A case in Activity Selection Problem where activities are selected based on completion times to maximize the number of non-overlapping activities.

3. Recursive Greedy Algorithms

Recursive greedy algorithms divide a problem into subproblems and make a greedy choice in every recursive call. Recursive greedy algorithms divide the problem into simpler subproblems, solve them greedily, and then build the solution from them. They are generally applied to problems with optimal substructure. A typical example is Prim's Algorithm for finding the minimum spanning tree, where the minimum edge is selected and recursively added to the tree.

4. Greedy Choice Property Algorithms

Greedy choice property algorithms assume that the optimal decision at each step will result in an optimal solution. This property ensures a series of locally optimal choices result in a globally optimal solution. Greedy choice property algorithms work optimally in problems where local decisions inherently result in the final solution without needing backtracking. Huffman Coding is one example where characters are given variable-length codes according to their frequency to minimise the overall encoding length.

5. Adaptive Greedy Algorithms

Adaptive greedy algorithms change their strategy depending on the current situation of the problem. Adaptive greedy algorithms backtrack on previous decisions when the problem shifts to try and improve the total solution. Adaptive greedy algorithms are more adaptable than pure greedy algorithms, which are flexible in evolving knowledge or requirements as the solution is developed. One example is Greedy Graph Coloring, where the algorithm dynamically changes the vertices' colouration according to the graph's shifting topology as it goes through more vertices.

6. Constructive Greedy Algorithms

Constructive greedy algorithms construct the solution incrementally by choosing the optimal from the available choices at every step based on a specific criterion. These algorithms develop the final solution piece by piece, enabling each step's solution to exist. One example of this algorithm is Kruskal's Algorithm for finding the minimum spanning tree, where edges are added one at a time in non-decreasing order of the weight, and cycles are prevented to form the tree.

7. Non-Adaptive Greedy Algorithms

Non-adaptive greedy algorithms are final in their decisions and irreversible once taken. Their algorithm does not revisit or modify decisions based on the problem state or intermediate outcomes. Once a decision has been made, the process doesn't change. An example is Dijkstra's Algorithm to find the shortest path within a graph, where once the shortest distance of a vertex has been calculated, no modifications are made to it.

Implementing a greedy algorithm for a problem is achieved by the following steps:

• Determine the type of problem and the goal (maximize or minimize).
• Specify what makes a good solution for the current problem.
• Select the optimal choice based on available information at hand. At every step, select the locally optimal one.
• Ensure that the problem has the Greedy Choice Property, i.e., an optimal solution can be built by making the optimal choice at each step.
• Keep on repeating the process of greedy choice until a solution is achieved.
• After the algorithm stops, check the correctness and feasibility of the solution.

Greedy algorithms share specific distinct characteristics that define under what circumstances and how they might be used: 

• Simplicity: Greedy algorithms are easy to implement and read.
• Efficiency: They often run in polynomial time and are more efficient than other complex algorithms.
• No Backtracking: The choice once made is never reversed.
• Local Optimization: Best available option now is selected step by step with the hope it will lead us to the global optimum.
• Non-Optimal Solutions: Greedy algorithms sometimes do not result in the best solution for any problem.’

A Greedy Algorithm generally consists of the following components:

• Candidate Set: A collection of candidate solutions or possible candidates that are to be searched at every step.
• Selection Function: A function that is utilized to choose the optimal candidate among the set of candidates.
• Feasibility Function: A function determining if a chosen candidate can be added to the existing solution without compromising constraints.
• Objective Function: A function to return a value or weight for the current partial solution.
• Solution Function: A function to determine if a solution is obtained or more steps are needed.

The Greedy Algorithm works by selecting the best local option at every step with the expectation that it will reach the global optimal. It works as follows:

• Begin at the start of the problem.
• Evaluate all the available choices from the current state.
• Select the optimal choice now, no matter what it could result in later.
• Move to the new state according to the selected option.
• Keep making the best local decisions until the goal is achieved or no further progress can be made.

Example of Greedy Algorithm

Consider the Coin Change Problem: Coin denominations are [1, 2, 5, 10] and the goal is to get change for amount 39 using the fewest coins.

Greedy Approach

• Begin with the most valuable denomination, 10.
• Subtract 10 from 39 and add one 10-coin.
• Subtract 10 from 29 and add a second 10-coin.
• Subtract 10 from 19 and add a third 10-coin.
• Subtract 5 from 9, which results in 4, and add a 5-coin.
• Subtract the last 2, 4 minus 2 equals 2, and add the last 2-coin.
• Subtract the last 2, resulting in 0, and add a final 2-coin.

CPP Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCoins(vector<int>& coins, int amount) {
    int n = coins.size();
    sort(coins.begin(), coins.end(), greater<int>());
    int res = 0;
  
    for (int i = 0; i < n; i++) {
        if (amount >= coins[i]) {
            int count = amount / coins[i];
            res += count;
            amount -= count * coins[i];
        }
        if (amount == 0) break;
    }
    return res;
}

int main() {
    vector<int> coins = {1, 2, 5, 10};
    int amount = 39;
    cout << "Minimum number of coins: " << minCoins(coins, amount);
    return 0;
}

Explanation

• The coins are arranged in descending order to begin with the maximum value coin.
• For every coin, it calculates how many times the coin fits into the remaining value (amount / coins[i]). The number of coins used is added to res, and the remaining value is adjusted.
• The amount decreases by subtracting the sum value of coins used (count * coins[i]).
• If the remaining balance is 0, break the loop and return the number of coins.

Output

Minimum number of coins: 6

Here are the applications of the greedy algorithm such as:

• Network Routing: Dijkstra's greedy algorithm finds the shortest path in network routing for minimal data packet transmission.
• Task Scheduling: Job sequencing problems in which jobs are selected through greedy algorithms by priorities, optimize profit maximization or deadlines.
• Resource Allocation: Resources in fractional knapsack problems are optimized by applying greedy using value-to-weight ratios.
• Data Compression: Huffman coding packs data by a greedy coding process, where the most occurring characters are assigned short codes.
• Coin Change: In finding the minimum number of coins for an amount, a greedy algorithm is typically employed when the denominations are constant.
• Greedy Coloring: Used in graph theory in graph coloring problems, trying to use the minimum number of colors while ensuring that adjacent vertices are differently colored.
• Traveling Salesman Problem (TSP): Greedy algorithms provide an approximate solution to TSP by always picking the nearest unvisited city at each step.

Here are the benefits of the greedy algorithm such as:

• Easy to implement and comprehend: Greedy algorithms are simple to implement and understand as they just worry about making the optimal local decision at each step.
• Efficient: They will generally have a lower time complexity than other methods, like dynamic programming, so they'll be faster at specific problems.
• Locally Optimal Decisions: One can choose the optimum local choice and then apply if a greedy algorithm to reach a solution easily without reversing steps. 
• Works Well for Certain Problems: Works well for optimal substructure and greedy choice problems, such as Minimum Spanning Tree and Huffman Coding.

Here are the limitations of the greedy algorithm such as:

• May Not Provide Optimal Solutions: Greedy algorithms rely on short-run optimization and might not consistently achieve the optimum global solution.
• Limited Applicability: They can be applied only to problems with greedy choice property and optimal substructure; otherwise, they will fail.
• No Backtracking: After making a decision we cannot change it and this might often give wrong solutions.
• Lack of Flexibility: Greedy algorithms are inflexible, and making them accept more problem constraints might be challenging.

The greedy method in data structures and algorithms focuses more on optimization problems. The greedy method might not always deliver an optimal solution but its efficiency, speed and simplicity make it desirable for many tasks. To effectively solve the computational problems, understanding how to use a greedy algorithm is crucial.

1. What is a greedy method in daa?

The greedy technique is a type of algorithmic strategy, at every stage, takes the optimum choice, aiming towards the optimum solution based on local choices and not backtracking. 

2. What is a greedy algorithm with an example?

Greedy algorithm solves optimisation problems by taking the optimal available choice at each step. As an example, the issue of coin change involves using the greedy strategy to keep coin usage minimal.

3. What is the basic principle of greedy method?

The greedy method is concerned with making the best local choice at every step and hoping these local optimal solutions yield an optimal global solution.

4. What is the backtracking method?

Backtracking is a method for solving problems in which all possible solutions are tried by building candidates step by step and discarding them if they do not result in a valid solution.