Traveling Salesman Problem | Dynamic Programming | Graph Theory
Вставка
- Опубліковано 31 гру 2017
- Solving the traveling salesman problem using dynamic programming
Related Videos:
TSP intro: • Traveling Salesman Pro...
TSP code video: • Travelling Salesman Pr...
Source code:
github.com/williamfiset/algor...
Powerset backtracking video:
• Backtracking tutorial:...
=====================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on UA-cam:
www.udemy.com/course/graph-th...
This video is extremely helpful to understand the dp approach. Really thank you for your effort to make this video.
Thanks for this excellent explanation, this was the only video that clarified the topic for me
thanks dude, you saved my ass on an exam. Much better explanation than the teacher.
Very helpful. Thanks a lot!
Very very useful. Pretty clear explanation! Thank you!
For whoever who didn't understand watch tushar Roy's video on this, it's without the bit mask though. But I understood it from his explanation much better.
One correction: TSP is np_hard, only its decision version is np_ complete
What's the difference
@@Bruh-jw2ze The optimization version of TSP (NP hard) ask: what's the best tour? The decision version ask: is there a tour with length < X. Both are NP hard to solve, but the decision is also NP: given any tour, you can easily compute its length and check if it satisfies your decision question (< X or not).
My lecturer mentioned something about tsp and np but I sill dont understand what being np hard or no complete means lol. despite reading so many definitions. only thing that penetrated my skull was big money prize
Thank you!
Could you do a video about the advanced bit manipulation techniques and about the binary operators?
You make very good videos and I'm sure it would be really useful for a lot of people.
Obtaining O(N2^n) is clear but how did you obtain a total runtime of O(n^22^n)?
What about using structs and pointers for traversing and tallying route cost?
Is it right to say that this "memo" table and tables used in dynamic programming in general are "lookup tables"?
thank you so much :)
How are you taking care that the we must visit the starting point again?
Going by the name, if combinations returns a list of all possible combinations of cities/nodes, then are you not doing a brute force search?
If I am not wrong 1
Thanks for tutorial of native English accent
+10000 Had ENOUGH of SOME ASIAN ACCENT!!
@WilliamFiset im confused about the binary representation of a state at 7:00. How do you arrive at the binary reprentation of going 0 to 1 as 0011 or 3
That state 0011 only encodes that nodes 0 and 1 are present in the state. It's not say anything about going from node 0 -> 1 or 1 -> 0. In the image, I'm simply illustrating the intuition of going from node 0 and expanding the state 0001 to 1001, 0101 and 0011.
I feel like I'm missing something. Given the description at 0:23, doesn't 0:42 leave out the fact that you have to return to the vertex of origin? A Hamiltonian cycle does not necessarily have to return to a particular origin, or be even close to doing so.
Hi! Thank you for this video! Very helpfull! ¿Does this work for asymetric matrices?
Worth to mention it becomes impossible to use a 32-bit integer to compress the set of traversed nodes if there are more than 32 nodes. At this point, we could start using 64-bit integers but they can't be used as index of an array so we'd need to use hash maps and pay the overhead in running time and memory usage. If 64 isn't enough either we can go to big integers (if the language supports it), paying an extra overhead. However, this problem is arguably difficult enough with 32 cities, so we don't necessarily need to worry about very large number of nodes.
True, however, this isn't much of a concern since the computation time to handle even 25-30 nodes requires way too much computation for any modern home computer to handle. Remember the time complexity is exponential: O(n^2*2^n).
@@WilliamFiset-videos Mmm yeah I thought I remembered that 30 could be handled in reasonable time with a computer than would explore 1 million states per second, but actually it already takes 11 hours and it would take 2.3 years for 40. So fair enough, I think we don't need to worry about this, just worth explaining why :)
@@dicidicee Yes thanks! At 40+ nodes there are better ways of solving this problem :)
@@WilliamFiset-videos Sorry, another note. Aren't you exploring some states multiple times? For example the combinations of 3 elements among 4 would be: 1110, 1101, 1011, 0111.
Then, for each of them you unset one bit among the three bits that are set. For example for 1110, this will generate: 1100, 1010, 0110. What will happen for 1101? It will generate 1100, 1001, 0101. These two sequences have one element in common (1100), hence there seems to be duplication of work here. Maybe we should check whether memo has already been filled for a state before executing the content of the loop for a given subset.
@@dicidicee possibly, I wouldn't think I'd effect the time complexity though
At 4:28, length is 2 and 5:18 paths of length 3, what these lengths are and how we got them, couldn't understand this.
teacher I developed a heuristic and would like to share it. My heuristic uses topology and concentric circles. What do you think?.
Would this be considered a top-down or bottom-up approach to DP?
Bottom up because we're combining small paths to make a larger one.
What if fuel cost per pound is a more accurate weighting for freight carriers?
Good vid! But i learned to read a long time ago!! xd
Can you explain to me the mean of memo matrix?
Hi, I have been trying to turn this code into C++ and my minimize cost doesn't work and once I get past 8 nodes then it also doesn't find the best path. I am fairly sure I have the same exact code as your github and I'm not sure why it doesn't work. Could you help?
Can someone help me about binary rep. I can not understand anything about binary rep
Can you also help show how the code can be modified if the "getting back to the starting point" is NOT required? From what I've read, a dummy can be added on the distanceMatrix but I couldn't quite grasp how exactly it would be done. Thanks!
Sounds like a different problem. Are you looking for a en.wikipedia.org/wiki/Hamiltonian_path?
Minimize distances of memo[end][1111111...] over all end nodes.
corect first line of function tsp ...
N = m.size()
thanks :)
THANK YOU
can anybody tell me the meaning of the line state = subset ^ (1
i just use the selling on ebay method to get that juicey O(1) complexity
Even after understanding the standard logic from Tushar Roy's video I can't understand this 😭😭😭
A spin at the staring point
try sorting all edge lengths, amount ½n^2, n is location count, then try the permutations until you have a guaranteed shortest loop path, but how fast you get the permutation that gives a full loop path
try djisktra shortest path algorithm, breadth first on all location starting points
please note, not all permutations are unique routes
the true number of unique routes is a lot less than factorial of the node count
I saw this problem in a anime I'm watching and decided to check it out....but watching this made my head hurt 😞
Which Anime?
@@SurajKumar-bw9oi hanime
It will not be memo(e)(next) but m(e)(next)
Do we need to return back to the starting point, we just need to visit all nodes right? Sorry if I'm wrong
Yes, TSP requires you to return to the start node.
Ouhhh alright, thanks, your explanation is really great, keep up the good work 👍🏻👍🏻
The travelling salesman wants to eventually get back home and sleep in his own bed! ;^)
Can anybody tell why in 11:59 r is initialize to 3
The setup step already computed solutions of path-size 2 (going from your starting location to every other node respectively). The solve function can thus start by looking at solutions of path-length 3 hence the r=3 setup in the for-loop.
this is sad, I just got my masters in computing and I had no idea what he was talking about... and here I am wanting to continue to PhD...
Please update 2:01, TSP is not NP-Complete it is NP-Hard. NP-Complete means that you can check the answer in polynomial time once you have the answer. However given you are looking for the shortest distance, you cannot verify that the final solution is optimal as you will need to check all other solutions. In short, NP-Complete problem solutions are quick and easy to check if there is a logical formulation (boolean) like hamiltonian path, however TSP is an optimisation problem and it is not possible to say that answer is optimal without doing all computation again, therefore is NP-Hard.
Should be that the decision version of the TSP is np-complete, in general you're right that it's np-hard
Isn't there a much faster and easier way to do this though? You can just apply graphical logic to it and bring the compute time down into polynomial time
I do not think that is possible, however if you can provide a solution which finds an optimal solution for the TSP in polynomial time that would be most likely a groundbreaking algorithm.
This could be the best video explanation for TSP solution but oh my God, you pause almost every 2 words which makes it impossible to follow what you are saying. I am going to try with 1.5x speed.
Instead of
if !condition: continue;
body
do
if condition:
body
True, but I generally prefer flat over nested, especially when we're already 5+ layers deep.
@@WilliamFiset-videos oh thanks a lot :-), I realized how beautiful the code will look if we use this strategy(instead of nesting deeply)
2:02 lol
The graph is misleading.
*WilliamFiset, Remeber this name kids. One day you will see that name near the name of many computer scientists that are assumed to be fathers of algorithms. Donald Knutth, Thomas H. Cormen, Leiserson, Ronald Rivest, Clifford, Prim, Dijkstra and many others...*
Worst education I did not understand anything
Bro you need more energy.....lack of energy in voice
Finally somebody who isn't a Indian! So sick of them spamming UA-cam with their indecipherable accents
Than how about trying to improve your hearing/understanding capabilities?
Honestly I also find it easier to understand what a native English speaker is saying vs. an Indian one (I'm not native speaker as well and I guess that it's self-evident). But and it's a big BUT, many times I find that the videos made by non native English speakers (most of them are Indians) are better at explaining an idea which make the learning way easier.... for example the video by Tushar Roy about TSP helped me a lot (I got to it from one of the comments above).
They make great tutorial videos if you try to understand them. And it is actually weird to be sick of people sharing their knowledge freely.