Скачать с ютуб The Traveling Salesman Problem: When Good Enough Beats Perfect в хорошем качестве

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