Greedy Algorithms
❖ The greedy method is one of the strategies, like divide and conquer,
that is used to solve problems.
❖ This method is used to solve optimization problems.
❖ An optimization problem is a problem that demands either maximum or
minimum results.
Let's understand through some terms.
❖ The Greedy method is the simplest and most straightforward approach.
❖ It is not an algorithm, but it is a technique.
❖ The main function of this approach is that the decision is taken on the
basis of the currently available information.
❖ Whatever the current information is present, the decision is made
without worrying about the effect of the current decision in future.
❖ This technique is basically used to determine the feasible solution that
may or may not be optimal. The feasible solution is a subset that
satisfies the given criteria.
Applications of Greedy Algorithm
● It is used in finding the shortest path.
● It is used to find the minimum spanning tree using the prim's
algorithm or the Kruskal's algorithm.
● It is used in a job sequencing with a deadline.
● This algorithm is also used to solve the fractional knapsack problem.
Advantages of the Greedy Approach:
● The greedy approach is easy to implement.
● Typically have less time complexity.
● Greedy algorithms can be used for optimization purposes or finding
close to optimization in case of Hard problems.
● Greedy algorithms can produce efficient solutions in many cases.
● Greedy algorithms are often faster than other optimization
algorithms, such as dynamic programming or branch and bound,
because they require less computation and memory.
● The greedy approach can be used to solve problems in real-time, such
as scheduling problems or resource allocation problems, because it
does not require the solution to be computed in advance.
● Greedy algorithms are often used as a first step in solving
optimization problems, because they provide a good starting point for
more complex optimization algorithms.
Disadvantages of the Greedy Approach:
● The local optimal solution may not always be globally optimal.
● Greedy algorithms do not always guarantee to find the optimal
solution, and may produce suboptimal solutions in some cases.
● Greedy algorithms may be sensitive to small changes in the input.
Components of Greedy Algorithm (Elements)
The components that can be used in the greedy algorithm are:
o Candidate set: A solution that is created from the set is known as a
candidate set.
o Selection function: This function is used to choose the candidate or subset
which can be added in the solution.
o Feasibility function: A function that is used to determine whether the
candidate or subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution
or the partial solution.
o Solution function: This function is used to intimate whether the complete
function has been reached or not.
Pseudo code of Greedy Algorithm
1. Algorithm Greedy (a, n)
2. {
3. Solution : = 0;
4. for i = 0 to n do
5. {
6. x: = select(a);
7. if feasible(solution, x)
8. {
9. Solution: = union(solution , x)
10. }
11. return solution;
12. } }
The above is the greedy algorithm. Initially, the solution is assigned with zero value.
