Traveling Salesman Problem | Dynamic Programming | Graph Theory

[@Sheaxer]

thanks dude, you saved my ass on an exam. Much better explanation than the teacher.

[@unav-daily]

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.

[@kebenny]

This video is extremely helpful to understand the dp approach. Really thank you for your effort to make this video.

[@李佳键-i6r]

One correction: TSP is np_hard, only its decision version is np_ complete

[@Bruh-jw2ze]

What's the difference

[@kienhuynh1614]

@@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).

[@hikari1690]

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

[@dicidicee]

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.

[@WilliamFiset-videos]

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).

[@dicidicee]

@@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]

@@dicidicee Yes thanks! At 40+ nodes there are better ways of solving this problem :)

[@dicidicee]

​@@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.

[@WilliamFiset-videos]

@@dicidicee possibly, I wouldn't think I'd effect the time complexity though

[@zhengyuwang2709]

Thanks for tutorial of native English accent

[@梦帆马]

+10000 Had ENOUGH of SOME ASIAN ACCENT!!

[@_paralaks_]

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.

[@Detros12]

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.

[@interstella5555]

Thanks for this excellent explanation, this was the only video that clarified the topic for me

[@Nekroz05]

i just use the selling on ebay method to get that juicey O(1) complexity

[@a1mdreco]

I saw this problem in a anime I'm watching and decided to check it out....but watching this made my head hurt 😞

[@SurajKumar-bw9oi]

Which Anime?

[@talkingmango8658]

@@SurajKumar-bw9oi hanime

[@Jkauppa]

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

[@Jkauppa]

try djisktra shortest path algorithm, breadth first on all location starting points

[@Jkauppa]

please note, not all permutations are unique routes

[@Jkauppa]

the true number of unique routes is a lot less than factorial of the node count

[@lazarus6983]

Obtaining O(N2^n) is clear but how did you obtain a total runtime of O(n^22^n)?

[@pragyanupadhyaya8527]

It will not be memo(e)(next) but m(e)(next)

[@hikari1690]

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...

[@elizabethhanna6285]

Would this be considered a top-down or bottom-up approach to DP?

[@WilliamFiset-videos]

Bottom up because we're combining small paths to make a larger one.

[@mohammedmoulla3922]

corect first line of function tsp ... N = m.size() thanks :)

[@Norogoth]

THANK YOU

[@isabanusrat8085]

Very helpful. Thanks a lot!

[@philoficer]

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.

[@rahulsaggi7047]

A spin at the staring point

[@yanxiangyang9881]

Very very useful. Pretty clear explanation! Thank you!

[@unav-daily]

Even after understanding the standard logic from Tushar Roy's video I can't understand this 😭😭😭

[@Michael3241a]

Thank you!

[@testiesmcgee9019]

What about using structs and pointers for traversing and tallying route cost?

[@willjadsonevania9787]

teacher I developed a heuristic and would like to share it. My heuristic uses topology and concentric circles. What do you think?.

[@sudhanshukumarroy7018]

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.

[@toni_canada]

Hi! Thank you for this video! Very helpfull! ¿Does this work for asymetric matrices?

[@mikeeggleston1769]

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?

[@wanderingfido]

What if fuel cost per pound is a more accurate weighting for freight carriers?

[@shinkwrloggie7579]

thank you so much :)

[@makkimenzon3385]

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!

[@WilliamFiset-videos]

Sounds like a different problem. Are you looking for a en.wikipedia.org/wiki/Hamiltonian_path?

[@ajaytyagi3018]

Minimize distances of memo[end][1111111...] over all end nodes.

[@sequalesminombre]

Good vid! But i learned to read a long time ago!! xd

[@Lutz64]

@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

[@WilliamFiset-videos]

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.

[@nimishbansal8282]

If I am not wrong 1

[@vaibhaves]

How are you taking care that the we must visit the starting point again?

[@ata_gunay]

Can someone help me about binary rep. I can not understand anything about binary rep

[@azonicrider32]

im still working on this.. i made a solution that always takes the longest possible path..lol

[@28_vovanthinh75]

Can you explain to me the mean of memo matrix?

[@iqbalibrahim4713]

Do we need to return back to the starting point, we just need to visit all nodes right? Sorry if I'm wrong

[@WilliamFiset-videos]

Yes, TSP requires you to return to the start node.

[@iqbalibrahim4713]

Ouhhh alright, thanks, your explanation is really great, keep up the good work 👍🏻👍🏻

[@roboticus3647]

The travelling salesman wants to eventually get back home and sleep in his own bed! ;^)

[@quoccuongtran3056]

can anybody tell me the meaning of the line state = subset ^ (1

[@AlefeLucas]

Is it right to say that this "memo" table and tables used in dynamic programming in general are "lookup tables"?

[@onurcanisler]

*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...*

[@thezyreick4289]

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

[@movingheadmau8128]

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.

[@yuvarajanm2059]

Can anybody tell why in 11:59 r is initialize to 3

[@movingheadmau8128]

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.

[@colinweil4034]

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?

[@AlefeLucas]

Instead of if !condition: continue; body do if condition: body

[@WilliamFiset-videos]

True, but I generally prefer flat over nested, especially when we're already 5+ layers deep.

[@nimishbansal8282]

@@WilliamFiset-videos oh thanks a lot :-), I realized how beautiful the code will look if we use this strategy(instead of nesting deeply)

[@benzeltser9851]

The graph is misleading.

[@chadidridi9306]

2:02 lol

[@muaazkhan4681]

Worst education I did not understand anything

[@salsamancer]

Finally somebody who isn't a Indian! So sick of them spamming KZbin with their indecipherable accents

[@Megalepozy]

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).

[@aminuolawale1843]

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.

[@adityabansal4731]

Bro you need more energy.....lack of energy in voice