Question 3:

Multistage Graphs Problem:

A multistage graph G = (V, E) is a directed graph in which the vertices are partitioned in k ³ 2 disjoint sets say V₁, V₂, ………, V_k. Further, if (u, v) is an edge in E, then, for i with 1 £ i < k, the edge u belongs to V_i and the vertex v belongs to V_i+1. The number of vertices in each of the first and last sets viz., V₁ and V_k is one. Let the node in the first set V₁ be called s and the node in the last set V_k be called t. Further, let c(i, j) be the cost of traversing from vertex i to vertex j.

The Multistage Graph Problem is to find a minimum cost path from the start node s to the terminal node t. Using Dynamic Programming, suggest a solution to Multi-stage Graph Problem.        (20 marks)

Answer:

A dynamic programming language formulation for a k-stage graph problem is obtained by first noticing that every s to t path is the result of a sequence of k-2 decisions. The ith decision involves determining which vertex in Vi+11? i ? k -2 is to be on the path. It is easy to see that principle of optimality holds. Let p(i, j) be a minimum cost path from vertex j in Vi to vertex t.

Let cost (i , j) be the cost of the path. Then using the forward approach, we obtain
Cost(i, j) = l min € <j, l > € E Vi+1 “{ c(i, j) + cost (i+1, l ) }
Since cost (k-1, j) = c(j, t) if < j, k > € E and cost (k-1, j ) = ? if < j , t > doesnot belongs to E may be solved for all j € V k-2 then cost (k-3, j ) for all j € V k-2 then cost (k-3, j) for all j € V k-3 and so on finally cost (1, s ) – 1.
F cost (3,6) = min { 6+ cost (4,9), 5 + cost (4, 10) }
= min { 6 + 4, 5+ 2}
= 7
F cost (3,7) = min { 4+ cost (4,9), 3 + cost (4, 10) }
= min { 4+ 4, 3+ 2}
= 5
F cost (3,8) = min { 5+ cost (4,10), 6 + cost (4, 11) }
= min { 5+2 , 6+ 5}
= 7
F cost (2, 2) = min { 4+ cost (3,6), 2 + cost (3, 7), 1+ cost (3, 8 ) }
= min { 4 +7, 2+ 5 , 1+ 7}
= 7
F cost (2, 3) = min { 2+ cost (3,6), 7 + cost (3, 7) }
= min { 2 + 7, 7+ 5}
= 9
F cost (2, 4) = min { 11+ cost (3, 8 ) }
= min { 11, 7}
= 18
F cost (2 ,5) = min { 11+ cost (3,7), 8 + cost (3, 8 ) }
= min { 11 + 5 , 8+7}
= 15
F cost (1,1) = min { 9+ cost (2,2), 7 + cost (2, 3) , 3+ cost (2, 4), 2 + cost (2, 5) }
= min {9 +7 , 7+ 9 , 3 + 18, 2+ 15}
= 16

Read Full Post Here

<< Previous Answer || Index Assignments || Next Answer>>