Greedy method | Algorithm Techniques

 Advanced Design and Analysis of Algorithm Techniques

Greedy method

Feasible Solution: For solving a particular problem there exists n inputs and we need to obtain a subset that satisfies some constraints. Then any subset that satisfies these constraints is called feasible solution.

Optimal solution: From a set of feasible solutions, particular solution that satisfies or nearly satisfies the objectives of the function such a solution is called optimal solution.

Objective function: A feasible solution that either minimizes or maximizes a given function is called objective function.

Greedy method is popular for obtaining the optimized solutions. The Greedy-technique is a general algorithm design strategy, built on below mentioned elements:

Configurations: Different choices, values to find

Objective function: Some configurations to be either maximized or minimized

Greedy algorithms don’t always yield an optimal solution. But sometimes they do. We will see a problem for which they do. Then we’ll look at some general characteristics of when greedy algorithms give optimal solutions.

General method:

1. All problems using the greedy method have n inputs and require us to obtain a subset that satisfies some constraints
2. Any subset that satisfies these constraints is a feasible solution
3. A feasible solution that either minimizes or maximizes given objective function is an optimal solution

Control Abstraction for divide and conquer method is given below:

Algorithm Greedy(a, n) // a[1:n] contains the n inputs.
{
solution := EMPTY; // Initialize the solution for (i := 1 to n ) do
{
x := Select(a);
if feasible(solution, x) then solution := Union(solution, x);
}
return solution;
}

Applications in greedy method are:

1. 1. 1. 1. 1. Knapsack problem
            2. Job sequencing with deadlines
            3. Minimum cost spanning trees
            4. Single source shortest paths
            5. Optimal merge pattern

Topic : Greedy method | Algorithm Techniques

This articel is contributed by Alapati Sai Karthik. If you any mistake in this article please comment below in comment section.In-case any doubt or issue please reach out us by email academyEra.com@gmail.com

Like our facebook page facebook.com/academyera  and instagram Account instagram.com/academyera for new updates and solve topic-wise  psu and gate cse questions

Thanq
Team
AcademyEra