Use the code “reducible” to get CuriosityStream for less than $15 a year! https://curiositystream.com/reducible
The Traveling Salesman Problem (TSP) is one of the most notorious problems in all of computer science. In this video, we dive into why the problem presents such a challenge for computer scientists and some of the clever methods used to solve the problem.
We start with showing why all brute force solutions and even optimizations to get exact solutions can’t reliably be used for large instances of the problem. We then proceed to discuss some heuristic based approaches such as nearest neighbors, greedy, and Christofides to get solutions that are reasonably close to the optimal solution.
But after finding a candidate solution, we also show how one might improve this solution via local search. We discuss some interesting algorithms for tour improvements including 2-opt, random swapping, and 3-opt improvements. Finally, we show some clever ways to analyze the search space, including simulated annealing and ant colony optimization.
Chapters:
0:00 Intro
1:27 Problem Definition
2:27 Why Finding Optimal Solution Is Practically Impossible
5:35 Nearest Neighbor Heuristic
6:59 Lower Bounding TSP
11:03 Greedy Heuristic
12:06 Christofides Algorithm
16:11 Sponsor (CuriosityStream)
17:15 Tour Improvements
21:13 Simulated Annealing
24:14 Ant Colony Optimization
28:25 Conclusion
Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.
References:
Nice interactive on various TSP algorithms: https://cse442-17f.github.io/Traveling-Salesman-Algorithms/
Many of the results for the algorithms are based on findings in this paper: https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf
This video wouldn’t be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim – Mathematical Animation Framework (Version v0.11.0) [Computer software]. https://www.manim.community/
Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible
Music in this video comes from Jesús Rascón and Aaskash Gandhi
Socials:
Patreon: https://www.patreon.com/reducible
Twitter: https://twitter.com/Reducible20
Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons:
Andjela Arsic
Andreas
Adam Dřínek
Burt Humburg
Brian Cloutier
Eugene Tulushev
kerrytazi
Matt Q
Mutual Information
Ram K
Richard Wells
Sebastian Gamboa
Winston Durand
Zac Landis
source
Thanks to CuriosityStream for sponsoring this video! If you want to watch their content and support the channel while doing so, go to https://curiositystream.com/reducible and use code "reducible" to get access for $14.99/year.
lol i solved this long ago like 10 years ago its to easy
Perfect is the enemy of good. — Voltaire
And yet, slime mold does it…No problem 🙂
This problem is easy: go with the season.
"if brute force doesn't work, you're not using enough of it"
Just curious
Wouldnt it better to use delaunay triangulation first, then search from there?
You can brute force it easy, but takes a long time. Or, you can do it fast, but not optimal. It's only difficult if you want a quick optimal solution with large N. Notice the value of N is always increasing!
Everyone knows that the hardest problem in computer science is naming variables, functions/methods and classes.
The Vehicle Routing problem (VRP) is the TSP problem on steroids and is almost a more common problem in reality. It can even get more complex when you add constraints like timed windows (VRPTW), vehicles with capacities, maximum drive distances, and anything else you can think of.
I once wrote a genetic algorithm to solve TSP once. Works quite well. Didn't do this much research then however.
I saw this in death stranding
This isn't really the "hardest". There are lots of problems that are equally hard, and TSP has a ton of great approximations that work really well.
We just catch all used routes by making all used routes twice as long as they have to be. We Don't need an optimum solution because most of our time is spent switching, we only going 12,500 miles at 84% the speed of light, so each HTTP address is unique and we have infinite addresses space in a modern device, we simply test all exluded paths in one try, and on the second pass, only allowed interrogation goes to it's locked target. Like let's say I'm matching the speed of light at 5ghz, but surely I can afford a short cut to switch ground to power by checking halfway with a short cut.
19:35 As someone who is red-green colorblind, ouch…
Better not teach such philosophical ways to computers, they'll conquer the world soon 😆.
Incredible explanation! I learned about simmulated annealling in a stochastic simulation methods course but never got the key idea behind it, but thanks to you now I get it!
also a nice solution: take the mid point out of all points, imagine a homogeneous stretching ideal baloon on that point. you pump the ballon up and somewhen it touches all the points. in a 2d plane you get the points to travel one by one on the line of the circle.
this works great if you are into puzzles and wanna do it by hand.
Thank you so much ☺❤
Why is the MST “close” to the solution of the TSP? I can see why it’s lower in all cases but the same is trivially true for an algorithm with runtime f(n)=0 so I don’t see why we care about the MST. Could anybody clarify?
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!
I had an idea for this problem at the start of the video,
Draw a shape that represents the average location of the remaining nodes before each, then choose between the closest nodes favoring nodes that are furthest from the average location border. I think it would help link those outer nodes so they don't have multiple long jumps to them
IDK if I've been watching too much 3Blue1Brown, but my first instinct for solving this was to convert all the distances into circles on the complex plane… … not sure how that would help in any possible way though
Great video!
Monte Carlo it, or quantum annealing if you’re a G like that
….WHAT IF WE KNOW THE WEIGHT?? DISTANCE TO THE CITY?? THEN CAN'T WE CHOOSE THE CLOSEST CITY?? (doing this for each vertex) and we'll eventually come back to starting point in optimal way (if we trace our path, we can follow back the trace right)???? WELL….it's already discussed in video..
Do a video about the shortest vector problem and its connection to quantum resistant lattice encryption
I took a set of 1000 cities (points on a Manhatan metric) whose lenght was 1.2 M units and brought it to 480k on my best run in under 6 minutes (8Gb of Ram, i5 Cpu).
Can someone tell me if that is any good in terms of current benchmarks?
Makes you respect the fact Google let's you get traffic from like 15 places at once,
As a courier, I solved this problem daily. It's easy.
Ummm, none of them used coordinates to use angle optimization? I mean, most of use could probably solve the exples by just trying to approximate a circle.
I have implemented all these algorithms on Discrete Optimization course on Coursera. They even had leaderboard where you can compare your best solutions with other peers. We were allowed to use all computer power we had.
Ant colony optimization was the last algorithm I tried and I was surprised how bad it performed in comparison with other. Maybe I did something wrong, or didn't find best parameters.
Great visualizations, animations, and explanations. I would comment on the choice of the color mapping in 19:40 not color-blind friendly.
'Ant colony optimization'
I literally came here to improve my Screeps.
Just so you know, the choice of green and red at 19:40 is completely indistinguishable to people with red-green colorblindness, with is roughly five to ten percent of all men.
Great, very comprehensive overview with all the important details, learned a lot
This could practically be used as an introduction to modern artificial intelligence techniques, with very little necessary extension! All AI research problems are the same: there's some optimal correspondence between inputs and outputs, but the search for the function that does that is even more intractable than this for numerous reasons – indeed, there usually is no one such function, since you're only able to provide a sample in many AI problems, as opposed to problems like these where you could enumerate every pair of edges, it'd just take a while. Nevertheless, the concept generalizes readily, and the ant colony method is very easy to relate to many practical techniques.
Your narration has improved a lot! These keep getting better.
LEGEND, PLZ UPLOAD MORE VIDEO!!!!
This video was fascinating!
As usual, statistics comes to save the day 🙂
Music????
This video is super well-made and really interesting, even as a person who already has some knowledge of the concepts mentioned. You did a great job taking a topic such as the TSP and simplifying it in a way that can be shown as an intro-level lesson.
Hey I really love the music in the video, can you tell which track plays when you start the simulating annealing part. Thank you, great video and explanation
Can u do a video on P VS NP??