L-5.4: Traveling Salesman Problem | Dynamic Programming
L-5.4: Traveling Salesman Problem | Dynamic Programming
đSubscribe to our new channel:   / @varunainashots Â
đLinks for DAA Notes:
đFile-1: https://rb.gy/2byrg
đ§âđContributed by: Junaid Gazi
đFile-2: https://rb.gy/gibu5
đ§âđContributed by: Mannu Garg
The traveling salesman problem (TSP) is an algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited. In the problem statement, the points are the cities a salesperson might visit. The salesmanâs goal is to keep both the travel costs and the distance travelled as low as possible.
âşDesign and Analysis of algorithms (DAA) (Complete Playlist):
   â˘Â Design and Analysis of algorithms (DAA) Â
Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
âş Operating System :
   â˘Â Operating System (Complete Playlist) Â
âşDatabase Management System:
   â˘Â DBMS (Database Management system) ComâŚÂ Â
âş Theory of Computation
   â˘Â TOC(Theory of Computation) Â
âşArtificial Intelligence:
   â˘Â Artificial Intelligence (Complete PlaâŚÂ Â
âşComputer Networks (Complete Playlist):
   â˘Â Computer Networks (Complete Playlist) Â
âşComputer Architecture (Complete Playlist):
   â˘Â Computer Organization and ArchitecturâŚÂ Â
âşStructured Query Language (SQL):
   â˘Â Structured Query Language (SQL) Â
âşDiscrete Mathematics:
   â˘Â Discrete Mathematics Â
âşCompiler Design:
   â˘Â Compiler Design (Complete Playlist) Â
âşNumber System:
   â˘Â Number system Â
âşCloud Computing \u0026 BIG Data:
   â˘Â Cloud Computing \u0026 BIG Data Â
âşSoftware Engineering:
   â˘Â Software Engineering Â
âşData Structure:
   â˘Â Data Structure Â
âşGraph Theory:
   â˘Â Graph Theory Â
âşProgramming in C:
   â˘Â C Programming Â
âşDigital Logic:
   â˘Â Digital Logic(Complete Playlist) Â
---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
âş Subscribe to us on YouTube:    / gatesmashers Â
âşSubscribe to our new channel:    / @varunainashots Â
âş Like our page on Facebook: https://www.facebook.com/gatesmashers
âş Follow us on Instagram: https://www.instagram.com/gate.smashers
âş Follow us on Instagram: https://www.instagram.com/varunainashots
âş Follow us on Telegram: https://t.me/gatesmashersofficial
âş Follow us on Threads: https://www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
âşFor Any Query, Suggestion or notes contribution:
Email us at: [email protected]
Content
0 -> Music
6.375 -> Dear students, welcome to Gate Smashers
8.4 -> In this video I am going to explain
10.425 -> Travelling Salesman Problem in Dynamic Programming
13.821 -> So guys, all the important points related to Travelling Salesman Problem
18 -> I will explain all of them to you
20 -> Which you can easily answer in your competitive
exams, college, university exams, interviews, anywhere
26.2 -> So guys, like the video quickly
28.2 -> Subscribe the channel, if you haven't done it yet
30.4 -> And if you have done it, then you can
get more subscribers from other devices
33.425 -> Subscribers are very important
34.975 -> So let's start Travelling Salesman Problem
38.175 -> First of all let's see what it is
40.2 -> Travelling Salesman Problem
42.4 -> So what is the salesman doing? Travelling
45.575 -> So what is the problem in this?
46.6 -> The problem is that we are representing in the form of a graph
50.8 -> Now I have 4 nodes in this graph
53 -> 1, 2, 3, 4
54.2 -> You can call these nodes as city
56.2 -> And in the middle you can see the edges
58.4 -> These edges are in this direction also
60.6 -> I have made the edges in both directions
63.613 -> They are made because maybe 1 to 2 weight is something else
66.638 -> 2 to 1 weight is something else
68.2 -> And all those weights are given to you in this matrix
71.4 -> Now what is the problem in actual?
73.6 -> That the salesman has to do the travelling
76.8 -> And that travelling is starting from any particular node
80 -> Let's say my starting city is 1
82.175 -> From 1 it has to start, it has to tour
84.333 -> Obviously what the salesman will do?
87.2 -> He will do marketing to sell a product
90.375 -> He is trying to promote it in different cities
95.2 -> So what he is doing is that he will start his tour from 1
98.4 -> He will start from 1 city
100.4 -> He will travel other cities
102.6 -> Means 2, 3, 4, he can travel in any order
105.8 -> And he has to come back to 1
109 -> Means he has to come back to 1 after roaming around
113 -> But what should be the cost?
115.375 -> Minimum
116.4 -> Obviously what should be the cost?
118.6 -> Minimum should be there
119.8 -> What is my actual problem?
122 -> So it looks very easy that what is this?
124.2 -> So we can easily do it
126.4 -> We can use Google map
128.425 -> It must be coming in your mind very easily
130.152 -> But when we try to implement it in real life
133.175 -> Then what is the time complexity?
135.2 -> How do we resolve this problem?
137.225 -> All these points should be in your mind
139.25 -> So see if we talk
140.994 -> It must be coming in your mind that first
143.6 -> If we use greedy approach
145.6 -> Because we have done many algorithms on the basis of greed
148.799 -> So if we use greedy approach
151 -> Then we are standing on 1
152.375 -> What we will do from 1 is
154.4 -> We will go to the minimum cost
156.844 -> What does greedy do?
158.066 -> At present where you are standing
160.11 -> From that point you can choose the lowest cost in the other city
165.816 -> So see from 1 you can either go to 2
168.4 -> Or you can go to 3 or 4
170.466 -> So greedy will say choose the minimum cost
173.8 -> So which is the minimum cost?
175.825 -> 2
176.85 -> So let's say I chose 2 from 1
179.4 -> Means I went from 1 to 2 city
181.6 -> And my cost is 10
183.8 -> My cost is 10 from 1 to 2
186 -> Now after reaching 2 what I did?
188.2 -> I chose the minimum cost
189.4 -> Now from 2 which options do I have?
191.6 -> One option is that I go from 2 to 1 again
194.8 -> This option can also come in your mind
196.8 -> So from 2 you go to 1 again
198.8 -> Then from 1 to somewhere else
200 -> But guys if you start in any particular city
203.2 -> And then reach there again
205.4 -> Then obviously you have to travel to other cities too
208.6 -> So obviously your time will increase somewhere
212.4 -> Instead of decreasing your time will increase
214.6 -> So that's why obviously you will not try to go from 1 to 2
216.8 -> Or from 2 to 1 again
219 -> If you will do in this question
220.8 -> You can choose
222 -> But let's say if we go from 1 to 2
224.6 -> Let's say I chose from 2 that
226.799 -> I have option of 3 and 4 too
229.824 -> So which is the minimum of both?
230.849 -> 4
231.978 -> So I chose city of 2 to 4
234.6 -> And my cost is 10
236.975 -> You can see the cost
238 -> Cost of 2 to 4 is 10
240.375 -> Now after reaching 4
241.4 -> Maybe I go back to 1
243.425 -> Then from 1 to 3 or 2
245.799 -> But if you are repeating any city again
248.6 -> Then you must be thinking that
250.6 -> Repeating the city again means
252.6 -> Your time will increase somewhere
254 -> So then obviously from 4
256.375 -> What will you try to choose?
258 -> From 4 to 3
259.2 -> Because 2 is done, 4 is done
261 -> You started from 1
262.2 -> And to reach 1 again
264 -> Instead of 4 to 1
265.2 -> You will try to choose from 4 to 3
268.025 -> So from 4 to 3 cost is 20
271.812 -> And then from 3 obviously you will go back to 1
274.375 -> Because you started from 1 and reached back to 1
277.2 -> So from 3 to 1 your cost is 15
280.2 -> So see if we talk about this total cost
282.2 -> Then how much will it be? 20
284.375 -> 40
285.575 -> 50
286.4 -> 55
287.775 -> How much will be your total cost?
289.8 -> It will be 55 cost
291.8 -> So is this minimum value?
294 -> We can't tell you that now
295.8 -> From the point of view of greedy
297 -> This answer will come
298.2 -> But when we use dynamic programming
300.4 -> Then we actually get the optimal answer
303.4 -> So this greedy approach solves the problem in this way
307.4 -> Now if we talk about brute force method
310.6 -> What is brute force method?
312.4 -> You try all the possibilities
314.6 -> Travel all the possibilities
317 -> Then you find out
318.4 -> What is the minimum cost?
320.6 -> That will become your answer
322 -> So let's say if I try to travel all the possibilities
324.6 -> Then you can do it this way
326.4 -> Let's say you started the journey from 1
328.2 -> One option you have is to go from 1 to 2
330.8 -> Or went from 1 to 3
332.4 -> Or went from 1 to 4
334 -> Obviously from 1 you have these 3 options
336.2 -> If let's say you chose 2
338 -> Then from 2 you have either 3 option or 4 option
342.2 -> From 3 you have either 2 option or 4 option
345.8 -> From 4 you have 2 or you can go to 3
349 -> That's the same number
350.2 -> Now let's say from 1 to 2 you go from 2 to 3
352.6 -> Now after 3 obviously you will go to 4
355 -> And after 4 you will go back to 1
358.8 -> So this possibility of 1 can become yours
361.6 -> Then if from 1 to 2, 2 to 4
363.6 -> Obviously from 4 you will go to 3
365.6 -> From 3 you will go to 1
367.4 -> Similarly from 1 to 3, 2 to 4
370 -> From 4 you will go to 1
372 -> Similarly from 1 to 3, 4 to 2
374.4 -> From 2 to 1
376 -> Similarly from 1 to 4, 2 to 3
378.799 -> And after that you will go to 1
380.799 -> After 1 to 4, 3 to 3, 2 to 2
382.799 -> After 2 obviously you will go to 1
385 -> So these total possibilities you can say according to this graph
390 -> So evaluate all these values
392.4 -> After evaluating the minimum answer that will be your answer
396.8 -> Of which we have already done 1, 2, 4, 3, 1
400.4 -> So 1, 2, 4, 3, 1
402.4 -> We have already done this
403.6 -> 50, 50
404.6 -> So by calculating all the values in this way
407 -> The minimum answer that is coming
408.6 -> That brute force method will work in this way
411.6 -> So this is a very basic level problem
417 -> But this is a very interesting problem in the algorithm
422 -> Because here you learn how greedy works in actual
426.4 -> How dynamic programming works
428.599 -> What greedy always gives me an answer
430.799 -> This is what you find out here
432.599 -> So if you solve it, I am not telling you by solving all
435.2 -> If you solve all then obviously it will take more time
437.799 -> What to do, nothing is there, cost is in front of you
440.2 -> Add it and evaluate it
442 -> So let's say I went from 1 to 3
444.799 -> If I went from 1 to 3, how much is my cost? 15
448.4 -> So I chose 15 cost of 1 to 3 here
451.799 -> From 1 to 3 is 15
453.599 -> From 3 let's say I went to 4
455.2 -> So if I went from 3 to 4, how much is my cost? 5
459.2 -> From 4 I went to 2
461 -> Let's say I am evaluating this one
462.4 -> From 4 I went to 2
463.599 -> So if I went from 4 to 2, how much is my cost here? 10
467.4 -> And from 2 to 1, how much is my cost here? 5
471 -> So total cost will be 15 and 5, 20, 30, 35
476 -> So here you have cost less than greedy
481 -> So this is your point that your greedy is failing here
486 -> So in this way you can write them in exams
489 -> You can tell them anywhere
490 -> And if you evaluate all these answers
493 -> I have already done it
495 -> So you will get the minimum answer of 35
498 -> So what is the answer of this problem?
501 -> 35 is the minimum answer
503 -> So write this point in your notes
507 -> So that you get a clear cut answer
509.8 -> You can evaluate all these in your notes
512.799 -> I am not doing it because it will take time
515.799 -> Let me tell you one more point
517.799 -> If it comes in your mind
518.799 -> Sometimes it comes in the mind of the student
520.799 -> That if 1 goes from 1 to 2, then the cost is 10
523.799 -> And if 2 goes from 1 to 2, then the cost is 5
526.8 -> You must be seeing
527.8 -> That if 1 goes from 1 to 2, then the cost is 10
530.8 -> If 2 goes from 1 to 2, then the cost is 5
532.8 -> How can this be?
533.8 -> Means if 1 goes from 1 city to another, then the cost is 10
536.8 -> And if it comes back, then how the cost is less?
538.6 -> So this is a simple example
539.6 -> Let's say you went on a cycle and came on a car
543.6 -> This is also a possibility
544.6 -> So when we solve real life examples with the method of graphs
549.6 -> So you do not restrict it to one point
552.6 -> Many things are possible
554.6 -> Like how negative weights are possible in the Bellman Ford
557.6 -> That is the answer I told you
559.6 -> So this possibility can be that you went on a cycle
563.6 -> And again suffered on the car
566.4 -> If we talk from the point of view of your
time, then time will obviously be less
570.4 -> If we talk from the point of view of money,
then maybe your money can be more
575.4 -> So any factor, this is just a metric, this is just a number
579.4 -> If you are measuring money, time in any way
582.576 -> Then you have to measure very carefully
585.4 -> If we talk about this thing, then you can say efforts
588.4 -> In terms of time
589.4 -> Because we have to choose the minimum value
592.2 -> So in this way you can map it to any example
598.2 -> So here the answer is 35
601.2 -> So if we talk about time complexity
603.2 -> This brute force method we have applied
604.025 -> So we did that actually from 1
to we have N number of nodes
610.2 -> From 1 to we have N number of nodes
613.2 -> So what are we doing?
614.2 -> We are going back to 1
616.2 -> Means from 1 to N number of nodes
618.2 -> I know to go to 1 by roaming
620 -> From 1 to N number of nodes
622 -> But where will my suffer end on 1 again?
625 -> So if we talk about this example
627 -> So 1, 2, 3, 4, 1 again roaming
630 -> Or 1, 2, 4, 3 roaming
633 -> Or 1, 4, 3, 2, 1
636 -> In this way the N-1 nodes in between
639 -> Your possibilities are being created in between them
642 -> The other Nth node is the same as yours
644 -> The one with 1 is the same
646 -> So the N-1 possibilities in between
647.8 -> Which you can call N-1 factorial
651.8 -> Total possibilities are being created here
654.8 -> So N-1 factorial
656.8 -> So many possibilities are being created here
658.8 -> If there are number of nodes
659.8 -> Like in this case you can say there are 4 nodes
662.8 -> So 4-1 is 3 factorial
664.8 -> So 3x2 is 6
665.8 -> So see 6 possibilities are in front of you
668.8 -> So if we write it in the form of order of
670.8 -> So obviously you can write it from the point of view of order of N factorial
676.6 -> And order of N factorial
678.6 -> If you solve it
680.425 -> It is N power N
683.25 -> Which is the biggest time complexity
685.775 -> In exponential
687.6 -> Till now we talked about 2 raised to power N
690.6 -> Whether it is 01 knapsack or sum of subset problem
693.6 -> But N raised to power N is the biggest time complexity
697.775 -> So this time complexity is coming from brute force method
701.6 -> So obviously we can't bear this much time complexity
704.425 -> So we will try to put dynamic approach in this
710.087 -> Now I will give you a hint of dynamic programming
713.4 -> Already we have discussed about it
716.4 -> What is the funda of dynamic programming
718.4 -> So there are 2 things here
719.4 -> The benefit of dynamic programming is
722.4 -> First, your problem should be division in subproblems
726.4 -> We can divide it in subproblems
728.4 -> Second, there should be overlapping between my subproblems
733.2 -> Means if there is repetition of all problems
736.2 -> So obviously we will evaluate it once and store it
739.2 -> Next time we will use it
741.2 -> So that my time complexity is reduced
743.2 -> But here if we talk
745.2 -> So my problem is very small
748.2 -> Your subproblems are being divided
750.2 -> One condition is being satisfied here
753.2 -> But if we talk about repetition here
756.2 -> So see from here 1 to 2, 1 to 3, 1 to 4
760.2 -> And from here 2, 3, 4, 1
762 -> Will this problem be separate?
764 -> From here 2, 4, 3
765.825 -> This is separate
766.799 -> This one is your subproblems are separate
769 -> This one is your subproblems are separate
770.825 -> This one is your subproblems are separate
772.175 -> And this one is your subproblems are separate
774 -> Means you can't see any repetition between them
778 -> Maybe you can see it at the last level
779.844 -> Like if we talk about the last level
782.175 -> So maybe you can see it at the last level
785 -> Like 4, 1 is being repeated or 3, 1 or 3
787.8 -> But there is no repetition at the rest of n-1 level
791.624 -> So because of this I will tell you
793.8 -> After applying dynamic programming here
796.8 -> You can reduce it a little from n raised to power n
800.8 -> But still it will remain exponential time complexity
804.8 -> It will not be converted in polynomial
807.8 -> Which was in the 01-NAPSEC or matrix multiplication
810.8 -> Which we did
811.8 -> It is possible in that
812.8 -> It is not possible here
813.6 -> So that's why we call it NP-complete problem
817.425 -> And along with this
818.775 -> If we talk about it
819.6 -> It can be written somewhere here
822.425 -> Hamiltonian cycle
824.775 -> We call it Hamiltonian cycle
826.6 -> By the way it is a part of graph theory
828.775 -> Hamiltonian cycle is
830.6 -> Starting from one node
832.425 -> Covering all nodes of the graph
834.775 -> And coming back to that node
836.775 -> That is a Hamiltonian cycle problem
838.6 -> So that's why we call it Hamiltonian cycle
841.411 -> So for now just note this about time complexities
844.4 -> But still how much we reduce from dynamic programming
848.224 -> That we will check in the next video
850.502 -> Thank You.
Source: https://www.youtube.com/watch?v=3QiSyc7KyC4