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.
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 :)
@@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.
@@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
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.
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
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.
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.
@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.
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!
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.
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?
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.
*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...*
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).
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.
thanks dude, you saved my ass on an exam. Much better explanation than the teacher.
This video is extremely helpful to understand the dp approach. Really thank you for your effort to make this video.
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
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
Thanks for tutorial of native English accent
+10000 Had ENOUGH of SOME ASIAN ACCENT!!
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.
i just use the selling on ebay method to get that juicey O(1) complexity
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
Thanks for this excellent explanation, this was the only video that clarified the topic for me
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
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.
Obtaining O(N2^n) is clear but how did you obtain a total runtime of O(n^22^n)?
corect first line of function tsp ...
N = m.size()
thanks :)
THANK YOU
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.
What about using structs and pointers for traversing and tallying route cost?
A spin at the staring point
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.
It will not be memo(e)(next) but m(e)(next)
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.
Very helpful. Thanks a lot!
teacher I developed a heuristic and would like to share it. My heuristic uses topology and concentric circles. What do you think?.
Very very useful. Pretty clear explanation! Thank you!
Hi! Thank you for this video! Very helpfull! ¿Does this work for asymetric matrices?
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?
Even after understanding the standard logic from Tushar Roy's video I can't understand this 😭😭😭
What if fuel cost per pound is a more accurate weighting for freight carriers?
How are you taking care that the we must visit the starting point again?
@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.
Thank you!
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...
Can you explain to me the mean of memo matrix?
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.
If I am not wrong 1
Is it right to say that this "memo" table and tables used in dynamic programming in general are "lookup tables"?
Can someone help me about binary rep. I can not understand anything about binary rep
thank you so much :)
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 me the meaning of the line state = subset ^ (1
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.
Good vid! But i learned to read a long time ago!! xd
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?
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)
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.
*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...*
2:02 lol
The graph is misleading.
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 TH-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.