Write abstract algorithm for greedy design method.

457views

written 9.4 years ago by

teamques10 ★ 70k

There are group of algorithms tries to solve problems which have the following general structure:
There are n inputs of some values and an objective function.
The method gives an optimal solution to the problem by considering the inputs one at a time, checking to see if it can be included in the set of values which give an optimal solution and then check if it is the feasible solution.
All of n inputs may not be included, only those needed to form the optimal solution will be included.
Each input may consume some resource, which is generally available in limited quantity.
We may say that the feasible solution represents the basic or the essential requirements of the problem and the optimal solution denotes the more specific and desirable requirements of the problem. Thus the flow of data is given in Fig. 10.1.
The strategy adopted for achieving the optimal solution is called Greedy method. The word greedy refers to allocating the maximum possible value of some limited resource to the first element which enters the optimal solution. The feasibility of the solution is expressed in terms of obeying the constraints of the resource. Thus Greedy method depends upon local (short range) maximum.

The abstract algorithm can be expressed as follows:
[ a(1:n) is an array containing n inputs]
Solution <- empty
```
 a. for i<-1 to n do
```
- x<- SELECT(a); [as per some optimization criteria] - if FEASIBLE(solution , x) then - Solution <- UNION(solution , x)
- End
  
  b. End
Return solution
The three functions SELECT 0, FEASIBLE 0 , and UNION() do the detailed work of this abstract algorithm.
Their details will obviously vary from one problem to another.
SELECT() select an element from all such that it has a potential for satisfying the optimality criterion or selection policy.
FEASIBLE() checks if the selected element x satisfies the feasibility criterion.
UNION() integrates the element x in the solution.

ADD COMMENT EDIT