4.7 [New] Traveling Salesman Problem - Dynamic Programming using Formula

hi the topic is traveling salesperson problem already I have one video on this problem already I have taken the same example and I have solved there but now I am going to explain you in a different way by using the forum line each and every step so let us see about the problem quickly I will tell you see the problem is a directed weighted graph is given so it means every edge is having some weight see these are actually parallel edges two edges one two two also two two one also but to show two edges I have shown it them as only one edge bi-directional now every edge is having weight so this is the cause adjacency matrix for this directed graph now the problem is we have to start from some vertex and travel all the other vertices once and we have to return back to the same starting vertex so start from any vertex and go through all the vertices once and return back to the starting vertex and the cost of travelling must be minimum this is the traveling salesperson problem for solving that this is a formula given this is a dynamic programming formula this is the general form of a formula now I will write on this formula according to these four vertices graphs then I will discuss about it the cost function is termed as G here our starting vertex is 1 and we have to visit remaining vertices those are 2 3 & 4 and minimum of what is this let us see see from any starting vertex I I can go to any of the K vertices that belong to the set it means from starting vertex 1 I can go to 2 also 3 also for also so here C of 1 2 K what K can be K can be anything from 2 3 & 4 plus G of starting vertex K and from 2 3 4 subtract key this is a general formula but we have written a formula with respect to four vertices the formula says that starting vertex is 1 and you have to visit remaining what it says in any order you want so you can move from 1 to 2 also 1 to 3 also 1 to 4 also so that all possibilities we are trying here we will be going from 1 to 2 or 1 to 3 1 to 4 anything out of that we have to take the minimum so whichever one we are going that vertex we should subtract from the set of vertices see if you observe this the formula is recursive it's a recursive formula cost of a root is defined in terms of cost of a root again here the set of vertices to be visited are two three four and here it is one less this is recursive formula how we can find the result of any recursive function we generated a recursive tree so let us generate a recursive tree for this one see here I can go from 1 to 2 so the starting vertex is 1 so if I go to vertex 2 then as per the formula C of 1k what is the K we are considering 2 so C of 1 2 + G of 2 2 remaining so 2 to see k k here so remaining remaining what K is a 2 here so 2 is removed so remaining will be 3 & 4 so this is 3 & 4 see again we got a cost function next I can go on vertex 3 also so 1 2 3 if I go from 1 to 3 so this is cost of an edge from 1 to 3 plus cost of 3 2 remaining so G of 3 2 what is remaining 2 & 4 so this is 2 & 4 and one more I can go from 1 to 4 also so this is for cost of an edge from 1 to 4 from G of 4 2 remaining what are those 2 & 3 see this is just like I have substituted 3 different values of K what are those 2 & 3 & 4 2 & 3 & 4 I have substituted so three different formulas now out of three different formulas all these three I have to take the minimum so this expansion I have done here I have written them separately I am showing them in the form of a tree out of these three I have to take minimum this minimum can they know minimum I don't know this I don't know this and this I don't know the cost of this so unless I know the cost of these functions I cannot get dancer and he cannot find minimum so how to find out this one again the same formula applies the same formula now here the starting point is two and here the starting point is three and the starting point is four so again use the formula expand them but before going further I can show you one thing cost refer netsy of one to two one two three one two four I can get it here they are given 1 2 2 1 2 3 1 2 4 that is 10 15 and 20 so I will write down 1 2 2 is how much then ok this value will be remaining I have to find out this one this is how much 15 this is remaining I have to find out this this is 20 this is remaining now let us expand these formulas and get the answer and add it to this one then out of this take minimum so first let us expand this now from here what is the possibility starting about X is 2 I can go to 3 or 4 I can go to vertex 3 if I am going to vertex 3 this is from 2 to 3 so cost of an H 2 to 3 plus G of 3 to four remaining vertex well before C 2 to 3 and then remaining is 4 so 3 4 where there so now 3 came out only four is remaining or else from two I can go to 3 also - I can go to four also so if I go on forward then C of 2 to 4 plus G of 4 then if I am going one for what will be remaining 3 will be remaining now in the same way I will expand these formulas also 3 to 2 I can go so co of 3 + G of 2 to 4 or 3 to 4 I can move so this is 4 so C of 3 comma 4 plus G of 4 2 remaining vertex is 2 then here also I will expand so this is I can go from 4 to 2 also and 3 also so if I am doing 4 to 2 this is C of 2 2 + G of 2 2 remaining vertex will be 3 plus C of 4 to 3 then G of 3 2 remaining vertex will be 2 now total 6 formulas we have now I can fill up these C values the cost of an edge so I will write all the values C C of - 3 - 4 - 3 is 9 - 4 is 10 so this becomes 9 and this becomes 10 then 3 2 3 4 3 2 is 13 3 4 is 12 so this is 13 and this is 12 then C 4 2 s 8 + 4 3 is 9 this is 8 and this is 9 4 2 is 8 4 3 is 9 still we don't know the value of these functions so let us use the formula and expand them if you observe here this says that starting what its history and the remaining vertex that we have to visit it only for so I'll go to vertex 4 so this will be from 3 to 4 so C of 3 4 plus G of 4 2 remaining is nothing when 4 is also gone we have visited for also there's nothing is remaining so same thing here remaining is 3 so say C or 4 - 3 + G or 4 3 2 nothing - 3 plus G of 3 to nothing is remaining then this is 3 to 2 so C of 3 2 G of 2 nothing is remaining say you know you can realize if we are solving it using a recursive tree then the tree will expand like this no doubt it will not execute like this the order of execution will be different but the complete tree looks like this now these cost or suggests I can write down here C of 3/4 C of 3/4 is how much 3 4 is 12 so let us take that 12 plus so-and-so function is there then C off for 3 is 9 C of 2 for 10 C of 4 2 is 8 C of 2 3 is 9 C of 3 2 is 13 now remaining still functions are there so I will show here C cost of a root from 2 to nothing so you are on what X 2 and no other vertex you have to visit because if you see from this 1 from 1 to 4 we have gone from 4 to 3 then 3 to 2 and as first traveling salesperson problem you must go back to the starting vertex again so from 2 we have to go back to vertex 1 again so for 2 to nothing means we have to go back to vertex 1 so 2 to 1 is how much 5 so we can replace this with 5 so let us start from here so - nothing will fall to 1/4 - 1 is how much see you can see this column 4 to 1 is 8 3 2 1 and 6 2 2 1 is 5 so here I have 4 to nothing 4 to 1 4 to 1 is how much 8 & 3 to nothing 3 2 1 is how much 6 4 to nothing so 4 to 1 is 8 2 to 1 s fine 3 2 1 s 6 and 2 2 1 s 5 so the last level we have the values now just you look at the three ones I am going to substitute the values and get back to the final answer just really have a look at a tree once the tree have expanded so much if we try to use a recursive tree then this is how it will expand so to avoid this we don't follow this method for solving and getting the answer but we will make it as a table and we get the values for this last level first then the upper level then above level then automatically we get dancer so I will show you how actually this is solved this is not the way I am just explaining this one I was just explaining this now let us see what is the way of solving this I'll remove this one here I will write on so actually you will find out the last level values what are those G off we are on the second vertex is nothing is remaining G off we are on the third vertex and nothing is remaining G of your unfold vertex nothing is remaining so we need answer to do nothing total thing is how much 5 + 3 - nothing s 6 4 - nothing s 8 see this is like a table will generate actually dynamic programming programming means with tabular values it's not software it's not computer programming programming means table or values dynamic programming dynamic collision at the table actually we should solve it like a recursion but we don't solve it like this we will prepare a table we what values you find out we find out the smaller values first then we can know that this value C unless I know this value it cannot get dance for this this why we followed these now in the next level you will find out these values C what are these 3 to 4 4 to 3 2 to 4 4 to 2 2 to 3 3 to 2 so we need these values we are on vertex two and three is remaining we are on vertex 2 and 4 is remaining we are on vertex 3 and what x2 is remaining we are on vertex 3 and vertex 4 is remaining and we are on vertex 4 2 is remaining to be visited what it's for 3 is remaining to be visited see here nothing remaining so 2/5 3/5 4/5 now one vertex remaining so if you are one two there are two possibilities three may be remaining or 4 maybe remaining so this way we have taken these functions and that are actually representing this second last level you see 4 2 2 3 3 2 all these are representing them now let us see what are these values see this is 3 for 3 we are on 3 and remaining is 4 so this is 20 so 3 we are on three remaining 4 is 20 so we know this value now I will change it with 20 we are on four remaining what is this 3 so this is 15 we are on four remaining what is 3 this is 15 so I'll change this value to 15 I know the answer now here on what x2 remaining value is 4 so this is 18 2 & 4 this is 18 I'll replace this with 18 Vinod ons are now here we are on 4 remaining is true it is 13 we are on 4 remaining is - as 13 so we know this answer 13 we are on to remaining is 3 we are on to remaining is 3 is how much 15 so this is 15 15 we are on 3 and remaining is 2 so this is 18 so 2 remaining we are on 3 and remaining is 2 is 18 so this is 18 now I'll show you from the table leave it on one vertex and remaining only one what X was remaining now if we say - what is this what are the possibilities we are on vertex 2 & 3 for our remaining or we are on vertex 3 & 2 for our remaining we are on what X 4 and 2 3 are remaining these are the possibilities see these 3 sets are representing this one we are one two three four remaining three to four remaining four to three minute how to get these values minimum of these two what is minimum 29 and 25 so this is 25 25 so this is 25 we don't need this now I will remove this now this is 31 and 25 3 to 4 or remaining is 25 25 so I remove this I'll write 25 years now if you do not answer for this also 4 remaining is 2 3 this one out of this which is minimum this is 23 and this is 27 so 23 is minimum so 23 is many more no remove this and write 23 now out of these we can find out minimum that will be done so for this so that is finally G of 1 and 2 3 4 3 vertices sorry meaning out of the switches minimum this is 35 and this is 40 and this is 43 out of this minimum is 35 so answer is 35 so answer for this one is 35 so the shortest route or for traveling salesperson problem is 35 so that's it

Channel: Abdul Bari

Views: 226,849

Keywords: TSP, traveling salesman problem, travelling salesman problem, dynamic programming, traveling slaesperson oproblem, algorithms, algorithm, gate, bari, abdul bari

Id: Q4zHb-Swzro

Length: 17min 18sec (1038 seconds)

Published: Mon Apr 02 2018