The Traveling Salesman Problem: When Good Enough Beats Perfect

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

Many of the results for the algorithms are based on findings in this paper: https://www.cs.ubc.ca/~hutter/previou...

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:   / reducible  
Twitter:   / 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