Greedy method :

 

Greedy algorithm :

 

·It works in stages , considers one input at a time .

·Inputs are considered in an order determined by some selection procedure.

·At each stage, decision is made regarding whether a particular input is in optimal solution.

·Inclusion of next input into partially constructed optimal solution should always result into feasible solution. If not then, this input is not considered.

·Selection procedure is based on some optimization measure; which may be objective function.

·Greedy algorithm that makes use of optimization measures to generate suboptimal solution is called ‘Subset Paradigm’.

General greedy algorithm :

 

Algorithm Greedy (a,n)

// a[1…n] contains n inputs.

{

solution=0; //initialise the solution

for( i=1 to n )

do

{

x= select(a);

if(feasible(solution, x)) then

solution= union(solution , x);

}

return solution;

}

à Function select , selects an input from a[ ] and removes it. The selected input’s value is assigned to x.

àFunction feasible is Boolean valued function that determines whether x can be included into solution vector.

àFunction union combines x with solution and updates the objective function.

·Knapsack problem , job sequencing , minimum spanning trees comes under the subset paradigm.

·Shortest path , Huffman codes comes under ordering paradigm.

Minimum cost spanning trees :

 

Definition : Spanning trees –

Let G = (V , E) be an undirected connected graph. A subgraph t= ( V , E’) of G is a spanning tree if and only if t is a tree. (No cycle exists.)

In practical situations, the edges have weights assigned to them, weights are positive. These weights may represent the cost of construction, lengths of links etc.

Given such weighted graph one would like to select cities (vertices) to have minimum total cost / minimum total length. So one can find a spanning tree with minimum cost.

Since identification of minimum spanning tree involves selection of a subset of the edges, this problem fits into the Subset Paradigm.

Greedy method constructs the tree by including edge by edge. Choose an edge that results in a minimum increase in sum of cost of edges so far included. Also set of edges so far selected form a tree. (No cycle.)

Prim()

// cost[1..n][1..] is a cost adjacency matrix.

// n: number of vertices in the graph.

// cost [ i ][ j ] =∞ , if there is no edge between I and j.

// cost [ i ][ j ] =∞ , if i=j

// cost [ i ][ j ] = cost [ i ][ j ] = positive number if it is edge.

// t [1..n-1][1..2] has all the edges of minimum spanning tree

// mincost is minimum cost

// near[ ] is an array which stores vertex in tree

// such that cost [ j ][ near[ j ] ] is minimum among all choices for near[ j ].

 

 

 

 

 

Complexity : The time required by algorithm Prim is O(n^2) where n is number of vertices in graph G. Each iteration of for loop takes O(n) time. So the total time is O(n^2).

If we store nodes not yet included in tree as a red-black tree then algorithm takes O(log n) time.

Disadvantages of Prim’s algorithm: