Introduction
Greedy algorithms are typically used to solve an optimization problem. An optimization problem is one in which we are given a set of input values, which required to be either maximized or minimized w.r.t. some constraints or condition.
Generally a optimization problem has n inputs (we call is as input domain or Candidate Set, C), we need to obtain a subset of C (call it solution set, S where S⊆C) that satisfies the given constraints, is called feasible solution.
Approach to find Optimal Solution
It is a step-by-step procedure by considering one input at a time. At each stage, the decision is made regarding whether a particular input chosen gives an optimal solution or not. Out choice of selection input x is being guided by selection function (say select). If the x gives optimal solution then this is added to the solution set. If it not generate optimal solution then it is rejected and never be considered again.
If everything works correctly the first solution is always optimal.
Activities are performed in Greedy Method:
1. First we select an element, say x form input domain C.
2. Then we check the solution set S is feasible or not. That is we check whether x can be included into the solution set S or not. If yes, then solution set S⬅️S U {x}. If no, then this input x is discarded and not added to the partial solution set S. Initially S is set to empty.
S⬅️{ะค}.
3. Continue until S is filled up (i.e. Optional solution found) or C is exhausted whichever is earlier.
Characteristics of Greedy Algorithm
- Used to solve Optimization problem.
- Most general, Straightforward method to solve a problem.
- Easy to implement, and if exist, are efficient.
- Always make the choice that looks best at the moment.
- Once any choice of input from C is rejected then it never considered again.
- Don't always yield an optimal solution; but for many problems they do.
Formalization of Greedy Technique
- A candidate set from which a solution is created. It may be set of nodes, edges in a graph etc. call this set as:
C: Set of given values or set of candidate
2. A solution set S (where S⊆C) , in which we build up a solution. This contains those candidate values, which are considered and chosen by the greedy technique to reach a solution. we can call this set as;
S: Set of selected candidates(or input) which is used to give optimal solution.
3. A function (say solution) to test whether a given set of candidates give a solution.
4. A selection function ( say select) which chooses the best candidate form C to be added t the solution set S.
5. A function (say feasible) to test if a set S can be extended to a solution.
6. An objective function (say ObjF) Which assigns a value to a solution, or a partial solution.
One of the widely used to example to learn greedy approach
The Fractional Knapsack Prolem
 |
| Knapsack Problem |
You can visit to this link www.akkytechx.blogspot.com
