The Traveling Salesman Problem: When Good Enough Beats Perfect

Thanks to CuriosityStream for sponsoring this video! If you want to watch their content and support the channel while doing so, go to curiositystream.com/reducible and use code "reducible" to get access for $14.99/year.

I know the optimal algorithm for a graph with two nodes.

"Sometimes things have to get worse before they get better." I didn't expect life wisdom to come from a video on heuristic optimization algorithms. A surprise to be sure, but a welcome one.

TSP is a NP hard problem but so is making this video. Every seconds of the video I see an exponential effort invested. Thank you so much!

In the '80's, I used a different strategy to solve this problem, just for my satisfaction. I based my solution on the way Nature would create an inner expanding bubble until touching all the nodes with minimal tensional energy. I used Basic in an 80286 PC, with about 100 random nodes. A short program with less than 100 lines of code was enough to get satisfactory results. Edit: minor grammatical correction (English is not my first language, sorry for that).

I'm quite impressed that you managed to avoid mentioning entropy while discussing the annealing approach and the pheromone approach. I once tried to explain pheromone optimization to a friend of mine who wasn't familiar with using entropy to backtrack a search, and I simply wasn't able to explain the process. Well done!

Been excited for this video for awhile. I’ve heard of TSP superficially many times.. but never got a deep dive like this before. Very motivated, exceptionally beautiful and naturally narrated. Content like this is the gem of YouTube. Just to add: As impossible as this problem is.. it’s wild to know we have a record solution with a tour length of 7.5+ billion.

So I had this job at a water-selling firm (pumping artesian water source and distributing it either in bottles or through dispensing machines). I took care of machine maintenance and also the logistics of refilling the machines with water. Basically making routes for the drivers that did it. Then some time later got into coding trying to change my career, and in search of ideas to build a portfolio, had this "brilliant" idea of making a routing algorithm. "Should be easy, I can do the routes with my eyes closed by now, just need to put the logic in my brain into code". Or so I thought. After some research, you guessed it, it turned out that I was trying to tackle the TSP. After lots of hours trying to get it to output routes that actually make sense scaled it down to a small web-app that just sorted stuff by priorities, while still doing routing myself, still saved some time and made a nice entry into the portfolio.

I have an MSc in Computing Science, but I have never seen a treatment of TSP and friends as beautiful as this. Thank you.

Never would I have thought that there is a connection between crystallurgy and the travelling salesman problem. What a beautiful video. Thank you for making this accessible for everyone! <3

Great insight on TSP. The research is vast and the information is often overwhelming.. but the way everything seems connected at the end is just amazing. Great intuitive ways to solve the TSP, would love to see more content on NP hard and NP complete problems. I started watching your content almost 2 years back when I first saw your ‘Towers of Hanoi’ video. Informative and concise.. love the animations <3

your videos are always a treat and often expose me to more knowledge that I didn't know exists before. thank you.

In love with the new intro. Amazing content as always! Doing computer science proud!

Never knew there were so many similarities between solving TSPs and reinforcement learning! Simulated annealing is so similar to the explore-exploit problem/bandits/epsilon-greedy and the ant colony optimization also reminds me so much of genetic algorithms and reinforcement learning😻 Cool video!!

PSPACE problems, common in planning, are arguably "harder", as TSP is "only" NP-hard.

Wow, that's a lot better than the 10 slides I got in university for this problem. Even took me less time to go through your video because it made so much more sense. Online universities with teachers like you would be so much better for everyone involved. Mad respect for you to make videos at this level of quality!

What an incredible intro to this problem. Wow, so clearly laid out. Thank you for all your work on this!!

Woah this is a video that I was waiting for since a long time. I've attempted to solve many variations of TSPs but I couldn't find any good and intuitive video regarding TSPs and heuristic algorithms on YouTube. Thank you so much!

It's interesting to see how a "simplifyed" (two way edges, linear paths) can become arbitrarily hard to solve. Imagine bringing this problem to a urban scenario, where edges are streets that are not necessarily 2 way and are non linear and trafic is involved.

Such an great video! You're doing an amazing job explaining those problems! Can't wait for your other videos!