2022-07-26

[public] 6.73K views, 12.3K likes, dislikes audio only

Reducible

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