Thursday, 9 May 2013

Minimum Spanning of Multistage graph using Dynamic Programming by the Wanderer



Dynamic programming is an algorithm design method that can be used when the solution to a problem may be viewed as the result of a sequence of decisions”

Minimum spanning of multistage graph using dynamic programming

    a.   Forward Approach

    b.   Backward Approach

a.   Forward Approach:
Spanning a multiple stage graph using following considerations

·       Identify source and destination nodes.


·       Find all possible paths to reach destination from source and sum of weights of     adjacent nodes.


·       The path giving the least weight will be the minimum spanning path.




Consider a multistage graph given below

Minimum Spanning of Multistage graph using Dynamic Programming by the Wanderer 

 
Identifying source and destination nodes.

             Source node -> S

             Destination node -> D

The possible ways to connect S & D

d(S,D) =  min { 1 + d(A,D) ; 2 + d(F,D) ; 5 + d(C,D) } ------->1



d(A,D) = min{ 4 + d(B,D) ; 11 + d(G,D) }

            = min{ 4 + 18 ; 11 + 13 }   ‘Substation weights

            = min{ 22 ; 23 }

d(A,D) = 22  ------->2



d(F,D) = min{ 9 + d(B,D) ; 5 + d(G,D) ; 16 + d(E,D) }

            = min{ 9 + d(B,D) ; 5 + d(G,D) ; 16 + d(E,D) }

            = min{ 9 + 18 ; 5 + 13 ; 16 + 2}   ‘Substation weights
            = min{ 27 ; 18 ; 18}

d(F,D) = 18  ------->3





 d(C,D) = min{ 2 + d(E,D) }

             = min{ 2 + 2}   ‘Substation weights
            = min{ 4}
d(C,D) = 4  ------->4


Substation of 2,3,4 in 1 gives


d(S,D) =  min { 1 + d(A,D) ; 2 + d(F,D) ; 5 + d(C,D) }

d(S,D) =  min { 1 + 22 ; 2 + 18 ; 5 + 4 }

d(S,D) =  min { 23 ; 20 ; 9 }

d(S,D) =  9
Hence minimum spanning path from S to D is
                       S -> C -> E -> D
          according to Forward Approach.


b.   Backward Approach:
Backward Approach is just the reverse of  forward approach, here Source node and the next node is considered at every stage.

Considering same Multi staged Graph,
Minimum Spanning of Multistage graph using Dynamic Programming by the Wanderer


1 -> 2

Source node S to next nodes A, F and C

d(S,A) = 1

d(S,F) = 2

d(S,C) = 5



1 -> 2 -> 3

Source node S to next nodes B, G and E

d(S,B) = min{ 1 + d(A,B) ; 2 + d(F,B)}

            = min{ 1 + 4 ; 2 + 9}

            = min{ 5 ; 11} 

 d(S,B) = 5



d(S,G) = min{ 1 + d(A,G) ; 2 + d(F,G)}

            = min{ 1 + 11 ; 2 + 5}

            = min{ 12 ; 7} 

 d(S,G) = 7



d(S,E) = min{ 2 + d(F,E) ; 5 + d(C,E)}

            = min{ 1 + 16 ; 5 + 2}

            = min{ 17 ; 7} 

 d(S,E) = 7





1 -> 2 -> 3 -> 4

d(S,D) = min{ 5 + d(B,D) ; 7 + d(G,D) ; 7 + d(E,D)}

            = min{ 5 + 18 ; 7 + 13 ; 7 + 2}

            = min{ 23 ; 20 ; 9} 

 d(S,D) = 9


Hence minimum spanning path from S to D is
                       S -> C -> E -> D
          according to Backward Approach.

4 comments:

  1. Well explanation is good and continue d topic...

    ReplyDelete
  2. your made a minor mistake in calculating d(A,T) in forward approach ...ur ans is correct co-incidently cz ultimately we get min as 22.

    ReplyDelete
    Replies
    1. Sorry, I did made a mistake in calculating the distance for nodes A,D in forward approach. Thanks for stopping here and correcting me.

      Delete

Featured post

Common Errors in English

Although English is a foreign language yet its important to learn in our country, If you needs to survive just out of your state now En...