4.1 MultiStage Graph - Dynamic Programming

the problem is multistage graph this problem can be solved by applying dynamic programming strategy in this video I will explain you what is the graph problem second thing how dynamic programming is applicable third thing I will solve it using forward method let us start let us talk about the graph a multi-stage graph is a directed weighted graph and the vertices are divided into stages such that the word adjusts our connecting vertices from one stage to mix stage only first stage in the last stage will have just single vertex to represent the starting point that is source or ending point or sink of a graph this is usually useful for representing resource allocation so here there are various part from source to sink I have to select the path which is giving me minimum cost this is the objective of the problem so it's a minimization problem that is optimization problem the problem can be solved using dynamic programming let us understand whether the dynamic programming can be applied on this phone or not so dynamic programming works one principle of optimality principle of optimality says that a problem must be solved in sequence of decisions let us see can we solve this by taking sequence of decision if I start from here from first stage that is a stage 2 here okay in this stage I have to select one of the vertex if I select five then I should make sure that what I am selecting is optimal is going to give me optimal result okay once I selected this now again I have two options here from five I can go to eight and seven out of this again I have to decide and select any one again next I have to decide and select any one so every stage I can take a decision so yes here the principle of optimality holds now applying dynamic programming procedure that stimulation method to get data or fill in the table for each what is I am going to find the cause and for finding the cost I will start from here because if you see from here the edges are going that side so if I want to confine the cost of this one then I should consider all that just reaching till sink if I find the cost of three then I should consider all the paths going till sink if I consider ten then the cost of path reaching there now if I say sink then the cost is zero obviously so for the last vertex the cost is zero and the vertex is still only for the last vertex how I got the cost as zero I will right now - cost of fifty stage what x2 n so I will write here stage number and here the vertex number and the cost is zero this is how I will use the formula cost of five comma two elements 50 stage and the vertex number 12 and the cost of zero me let us find out the cost of all these vertices in this fourth stage so first cost of one stage for vertex nine so what is the cost of reaching until sink it is for this edge for just a single edge path it is so it is four and the cost of fourth stage and vertex its true cost of fourth stage eleventh vertex this is five but it says four to five right so from Reverse five to four so this is 5 this is 2 and this is 4 now by taking these vertices 9 10 and 11 where I am reaching I am reaching one two and the vertex only so this is 2 L and 2 L and to explain you what does it mean by D here ok very soon now let us take third stage so I have the vertices 6 7 & 8 I will find out the cost of these three so first six cost of third stage sixth word X now from here if I see there are two edges coming out so this is six to nine as well as six to ten so which one I should select I should select the minimum cost so let us consider both then select the minimum so I have to select minimum of what cost of an edge six comma nine plus cost of fourth stage ninth vertex and also cost of an edge six comma 10 plus cost of fourth stage tenth vertex I have to take the minimum of these tools so what is that six plus cost of nine five plus cost of ten so six is what this six to nine is an edge I am writing it like this right sees cost of an edge costas cost of in vertex this is C is weight of an inch okay I am writing it as weight of an edge six plus nine so what is this equal to minimum of C six to nine is how much 6 plus cost of 4 comma 9 is here 4 comma C of 6 comma 10 is how much 5 come Plus cost of 4 comma 10 10 s this one so all of this which one is smaller this one is a smaller the vertex 10 has given me smaller value 10 has given me smaller value what is that 7 so 6 is 7 and visual X has given me minimum cost vertex 10 so the one which is giving minimum result we have to write on that one here cost of 7 vertex that is stage 3 here cost of 3 comma 7 from 7 vertex if you see there are two edges going out so to know the cost of seven I should know the cost of 9 and 10 plus the cost of this edge so 4 plus cost of 9 3 plus cost of 10 all of those - whichever is minimum I should take so I'll try it like this cost of an edge from 7 to 9 plus cost of a vertex 9 in fourth stage , cost of an edge from 7 to 10 plus cost of a vertex 10 in stage 4 out of these two I should take minimum now if I take minimum out of these cost of 7 to 9 edge 70 minus 4 plus cost of 9th vertex s there from the table so you can see how the values from the table are useful so this is 9 already you found out no it is useful it was useful for 6 also know for 7 also this value of 9 is useful so this what overlapping subproblems are there in dynamic programming so 4 comma C of 7 to 10 7 to 10 is 3 plus cost of 10 cost of 10 is so much to do out of these two this is minimum that is 5 so cost of a vertex 7 is 5 this we are getting due to which vertex 10 so in the D I should write down 10 so India should write on the vertex which has given me the shortest path the minimum cost next is cost of 8 so there are two edges going out from 8 to 10 and 11 so cost of an edge from 8 to 10 and the cost of vertex 10 in full stage , this more space I write here C of 8 to 11 plus sort of a vertex lovin in stage 4 I have to take minimum of these so this is minimum I know these values so I will replace them cost of 8 to 10 5 plus cost of an edge 10 what extend sorry 2 comma cost of an edge 8 to 11 6 plus cost of a vertex 11 is five minimum as seven who has given the seven what extent has given this seven so here that is seven and the vertex that has given that result is a ten only now let us find the cost of all those vertices which are in stage two cost of vertex 2 in stage 2 see there are 3 edges going off from here one four six one four seven and one four eight so this is minimum of cost of an edge from two to six plus cost of vertex six in stage 3 , cause of an edge from two to seven plus cost of a vertex 7 in stage 3 , cost of an edge from two to eight plus cost of a vertex eight in stage three first we are writing stage okay so I have elaborated the cost function here it sells out of these I have to take the minimum see this one is how much cost of an edge 2 2 6 2 2 6 is 4 plus cost of 6 in 7 comma cost of an edge 2 comma 7 is how much 2 plus cost of this 7s v comma C of this one is 1 plus cost of a vertex 8 is 7 out of these three which one is a smaller this is 7 and this is 8 and this is 11 so 7 is a smaller so this one has given us minimum result so the answer of this cost of what X 2 this 7 and who has given us minimum result the vertex 7 has given us minimum result so this is 7 cost of second stage fourth vertex as minimum off from 4 there is only one edge so cost of 4 comma 8 plus cost of vertex 8 Stage three out of this there is only one value so this is 11 plus cost of 811 plus cost of 8 is 7 so this is 18 who gave the answers that 8 has given done so this vertex has given the answer so this is 18 and this is 8 cost of second stage 54 Texas minimum off from 5 there are two edges one is going to sever and one is going to 8 so C of 5 comma 7 plus cost of 7th vertex in stage 3 plus comma cost of fairness from 5 to 8 plus cost of vertex 8 in stage 3 sort of this minimum of C of 5 comma 7 is 11 plus cost of 7 is 5 comma this one is 8 plus cost of 8 is 7 so this is 16 and this is 15 15 is a smaller and who has given this result 8 so this is 15 and this is 8 now lose the table is filled here only 1 values remaining now we are at the stage to find the minimum cost for this that is starting vertex so that will give us the minimum cost from here to there source to sink cost of 1 comma 1 from vertex 1 in stage 1 that first stage there in vertex there are 4 1 2 2 & 3 & 4 & 5 so I should consider all and take the minimum do we have the cost of what X 2 3 4 5 years all these they are filled here so that is easy for solving now to find this cost C this is cost of an edge from 1 to 2 plus cost of 2 2 2 comma cost of an edge from 1 2 3 plus of toward vertex in stage 2 is what is minimum let us find out see the values are 9 7 3 2 right so this is 9 plus cost of two common to this 7 comma cost of 1 comma 3 so much 7 plus cost of what X 3 is 9 comma cost of this vertex 1 comma 4 H is how much 3 plus cost of 4 is 18 comma cost of 1 comma 5 is a 2 plus cost of 5 is 15 out of this which one is a smaller this is 16 this is also 16 this is 21 and this is 17 so I got two answers that are same so the answer is 16 only but that is going why I what first also vertex 2 and ii was vertex 3 both are giving same result so i write 2 or 3 here I can take only 1 also but I am writing both to see how the difference will be it's like first filling their smaller values then getting the answer for the larger value so he started from the backwards side that is from the backside of our multistage care of last stage onwards he started but still this is called as forward method how we will see that next let us frame the formula now I did not show you the formula but now but the procedure already have shown you let me frame the formula we were finding it like this cost of I stage giant vortex this Iser stage number right and this J is a vertex number so this was minimum all I was taking minimum of what this was cost of an edge from vertex J to some vertex l plus cost of cost of that next vertex L if I say J and L J is supposed to then L suppose so she cost off 2 to 6 then the cost of 6 thirds stays 6 worth X so we were writing the stage number here I plus 1 and L this for the formula we were finding whatever the edges are available for two there are three edges so we wrote the same thing three times you can see that for finding cause cost off second stage third vertex was minimum off one of the valuable right on third vertex to sixth word x plus cost of third stage sixth vertex if I say this is stage number two and vertex this is J then minimum of cost of an edge J to some and some vertex L then cost of that L and that L 6 is definitely in the next stage so this is I plus 1 if I is a 2 then this is 2 plus 1 so this is I plus 1 this is all we were using the formula for finding these cost and multistage graphs so this is the formula former stage graph and we say that I and J and L belongs to set of engines and and L belongs to next stage so this is the formula that you can find in the textbooks not actual dynamic programming starts right already we have the formula hand filled up the table based on the dynamic programming or the dynamic programming approach to get the result actually the method of dynamic programming is to solve a problem by taking sequence Ossetians we have not taken in a decision so far but now we are going to take the sequence of decision based on the data available so already I was writing the D value whichever the vertex was giving us minimum result writing the devalue they're using that we take a decision what decisions we take from here where we should go to which vertex then from there where we should go then from there we'll so decisions are taken only have this complete data with you so already we have the data now we are going to solve it by taking sequence of decision and we will start from vertex 1 onwards towards sync so this is forward the decisions will be taking in forward direction so the base board decisions this is forward method let me do that first of all distance of D D D value ROI or you have four one two three four all I have so first I will write stage number this is a stage number right and then I will write on vertex this is vertex D of 1 comma 1 so actually be a concern about this I am writing it like a formula okay so this is stage number and this is vertex number so we will consider this vertex number what is the answer to so let us take 2 now in the second stage already we have taken 2 D of 2 comma 2 since of the first stage we selected first vertex in second stage second vertex - what is - now from there where we should go so - who has given the minimum result 4 to 7 so this is 7 in D we have 7 now we are on the seventh vertex on 7 more days in stage 3 now being on stage 3 where we should go next from 9 or 10 which one so 7 has given as 10 so 10 now we are on the word extend in stage 4 then from 4 to stage 10 - vertex where we should go next so table will tell us everything so we should go on 12 so that's it - well so when part is what we started from vertex 1 to 2 then 7 then 10 and 12 so this 1 to 2 2 to 7 7 to 10 10 to 12 this is the shortest path from source to sink that this D values has given the result so now we have taken sequence of decisions let me show you once more for three I said that for both two and three we got down for a sixteen so let us three what does it give I start from vertex one that stage 1 so 1 1 gives us what tree then I am going to stage 2 on vertex 3 then third vertex what is the one which has given minimum result 6 so this says goes to 6 then in the third stage among vertex 6 known so ok I'll do it here also I have gone to 3 then 3 has sent me to 6 now being on third stage sixth word X where I should go next so 6 what's the answer 10 so go to 10 so it says that I should be moved to this one so this is the decision I have taken then 10 is in 4th stage so from 10th vertex where I should go 10th vertex we already have seen this answer that is 12 to us so from 10 I should go to 12 so this is another root you see this is another vote which is eaten as the minimum result so this is 1 right so why are to 7 10 then 1 3 6 and 10 n - 1 so I have 2 parts of same cost so the optimal result is only 1 but in by chance we are having 2 parts which are giving us the same result that's all about multistage graph problem and I have explained you how dynamic programming is followed here

Channel: Abdul Bari

Views: 439,353

Keywords: Multistage graph, multistage graph problem, multi stage graph, multi stage, dynamic programming, algorithms, algorithm, abdul bari, bari, gate

Id: 9iE9Mj4m8jk

Length: 21min 7sec (1267 seconds)

Published: Fri Feb 16 2018