The Traveling Salesman Problem: When Good Enough Beats Perfect

Подписаться 279 тыс.

Просмотров 258 тыс.

50% 1

Use the code "reducible" to get CuriosityStream for less than $15 a year! 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: cse442-17f.github.io/Travelin...
Many of the results for the algorithms are based on findings in this paper: 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]. www.manim.community/
Here is link to the repository that contains the code used to generate the animations in this video: 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

Опубликовано:

30 май 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 508

@Reducible Год назад

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.

@tuongnguyen9391 Год назад

Can you do Max cut problem :)))

@hexeddecimals Год назад

Congrats on the sponsorship dude!

@deadhorseak Год назад

Hello. I've academically researched the Travelling Salesman Problem for years now (mostly centered around finding better algorithms than existing branch-and-bound approaches). I can say you did quite a good job explaining it. Even better than I could do in some of my own presentations. If you're looking for a mind-bogglingly difficult problem, you could do one on the Bandwidth Minimization Problem. If I remember correctly one of the algorithms for it had complexity ≈ O(20^N).

@dodimantakimpo5743 Год назад

What software do you use to create animations?

@RakeshKumar-te1tr Год назад

Tell me a good digital signal processing text book

@KazeSenshi2929 Год назад

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

@shivanshmishra752 Год назад

Lol

@cyanmargh Год назад

Believe it or not, I have an algorithm even for three vertices!

@gemigames154 Год назад

Prove it!

@Shxrpay Год назад

@@gemigames154 too long to write in a comment

@no_name4796 Год назад

@@cyanmargh i am such a genious that i may be able to solve 4 vertices graph!

@austinbutts3000 Год назад

"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.

@MagDrag123 Год назад

Thanks to the greedy algorithm, humanity discovered fossil fuel.

@Nononoya009 Год назад

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!

@cit0110 Год назад

@@abdulhfhd ohh nooo why did you correct him? you didn't owe him anything

@cit0110 Год назад

@@abdulhfhd fs bestie, remember what you like to say. you don't owe anyone anything

@cit0110 Год назад

@@abdulhfhd yeah but you still don't owe anyone anything. remember that. thats your motto 😂

@cit0110 Год назад

@@abdulhfhd 💦 don't give it up hunny

@cit0110 Год назад

@@abdulhfhd ;p

@wafikiri_ Год назад

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).

@kemsekov6331 Год назад

This is cool idea!

@viniciusfriasaleite8016 Год назад

Really clever!

@wafikiri_ Год назад

@@viniciusfriasaleite8016 Obrigado.

@wafikiri_ Год назад

@@kemsekov6331 Thank you.

@angeldude101 Год назад

I mean, a bubble tries to minimize tension around the outside, which is basically just a 3D version of the same problem.

@breckandolley8904 Год назад

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!

@breckandolley8904 Год назад

Post Script: My specialty is particle physics, and his is machine learning, so maybe I'm just too in love with entropy to shut up about it. (I have been told that it is not normal to use the Bose Statistics to explain how I organize eggs in a carton.)

@Reducible Год назад

Interesting, the entropy connection feels natural with Simulated Annealing, and it makes some sense with Ant Colony Optimization. I couldn't quite find an appropriate place to add it into the script without it feeling a little forced though. Thanks for bringing up this connection.

@herseem Год назад

@@breckandolley8904 Even without having ever heard of Bose-Einstein statistics before, but knowing already it's an obscure branch of advanced maths, this made me laugh out loud. Nevertheless, I did check out what it is afterwards, so thanks for bringing it's existence to my attention.

@TAP7a Год назад

@@herseem Bose-Einstein is like second year Physics undergraduate material, hardly arcane forbidden knowledge

@herseem Год назад

@@TAP7a I believe you, and that is still pretty obscure for most people who struggle to understand basic statistics. And still far more advanced than is required for filling an egg carton

@Mutual_Information Год назад

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 RU-vid. 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.

@schwingedeshaehers Год назад

there are harder problems

@tkzubaran Год назад

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

@theprofessionalfence-sitter Год назад

And then you have infinitely many degrees of uncomputable problems on top of that.

@mafrasi2 Год назад

According to the time hierarchy theorem, there even are infinitely many *computable* classes harder than NP. I think the video title is a bit misleading (or wrong really)

@HaoSunUW Год назад

It also has a 3/2 approx in general and PTAS in the planar and euclidean cases. Further real world instances are often solved to within 1-2%

@Vaaaaadim Год назад

Assuming NP != PSPACE

@schwingedeshaehers Год назад

@@Vaaaaadim i think that that is proven, but i am not sure. but the Problem, if a program runs infinity, is unsolveable.

@brain5853 Год назад

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.

@tenet-rotas Год назад

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!

@EricKolotyluk Год назад

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

@Arthurt120 Год назад

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.

@Agedude Год назад

In a lot of cases that might be more difficult, but in many cases it might actually be easier to solve. Adding additional rules to the system could make most potential solutions very obviously bad or eliminate them entirely until there are only a few possibilities to check.

@U20E0 Год назад

The ant solution might be the best in that case, and it would work without any extra modification. ( for one-way roads just initialize the appropriate entry in the weight matrix as zero instead of one ) Plus it can adapt to variable conditions well. ( Adding as an additional input an array that weighs the randomness on each node may help with sudden changes. )

@CursedByManga Год назад

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!!

@dr_davinci Год назад

I was thinking the same, Ant colony optimization reminded me of genetic algorithm.

@thomascoolidge2161 Год назад

I did a report in Linear Algebra discussing using Adjacency Matrices to find paths from any point to any other point by raising matrices to their power step by step. I managed to make it work for minimum hop count and shortest path between two points. Unfortunately it doesnt solve the TSP because it does not go back to it starting point.. only that it can hit every point. We had another idea of using something similar to what we called gravitic weighting to image creating the shortest path by picking any point and then "lifting it" and seeing the other points fall based upon distance.. we ran into problems with pruning of ineffecient routes.. if we could identify routes that were not going to be used we think it would have worked.. unfortunately our advisor didnt seem to care to help us at all... to him TSP was just an impossible problem and we were waisting our time.

@rohitd09 Год назад

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

@jimboli9400 Год назад

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

@kaishang6406 Год назад

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

@papagunit Год назад

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

@ThePlayfulJoker Год назад

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!

@sathirasilva4958 Год назад

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 RU-vid. Thank you so much!

@ricardocardoso6523 Год назад

This video was very well done! I come from a data science background, and so I was more familiar with the traveling salesman problem in the context of evolucionary optimization and multi objective optimization. The heuristic aproaches presented in this video are super interesting, and the presentation is amazing, it was really easy to understand.

@nsiepmann Год назад

Thank you - this was SO helpful. I watched it once this morning, and came back to rewatch and make notes in the afternoon, and I finally feel like I have a good understanding of the topic! Subscribed.

@madhes23 8 месяцев назад

How to like a video multiple times? The explanation and animation was phenomenal. Great job!

@BillyBob-wh4sq Год назад

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.

@dfkjbdfondfngg Год назад

The sheer amount of work that goes into creating these simulations.... Thank you!

@Habib-ov3nv Год назад

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

@JohSmith Год назад

This video is awesome. Great explanation and great montage (it's a lot of work to show all this nodes and highlight them)

@_spartan11796 Год назад

Always great to see you post!

@tellurian7999 Год назад

One of my favorite approximations is using a blob-like shape that stretches itself to just barely touch all the nodes while taking up as little space as possible, and then going around the edges of the blob.

@10produz90 Год назад

The visualizations are just awesome and add so much to the already awesome explanation.

@pamdemonia Год назад

Fascinating and informative as usual. I love that you have the ability to make some rather difficult subjects understandable, even to my fine arts degree brain!

@ferdiaz8703 Год назад

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!

@Boringpenguin Год назад

Very well done! TSP is one of the problems that interests me a lot but I just never got the time to learn it properly. This is the perfect introduction on TSP for all of us to enjoy :)

@JordanMetroidManiac Год назад

A perfect TSP 101

@herseem Год назад

Absolutely top-quality video. Thanks for creating it. Has stimulated me to find an algorithmic solution that is better than what is currently available. Will be a useful problem for learning Python

@Funzelwicht 7 месяцев назад

Sooooo well explained and animated, so good!

@rubensleite5838 Месяц назад

I will definitely apply this to my thesis problem: Point cloud registration and 3D reconstruction. Thank you very much.

@tinymints3134 Год назад

You did a great job on this video. I learned a lot and it solidified other understandings I had. Awesome!

@anshumandash1304 Год назад

I think you do amazing work, you have a talent at showing your passion for this beauty, it's truly infectious. Amazing work as always!

@HiAdrian Год назад

Great presentation on TSP, this was a pleasure to follow!

@elijahberegovsky8957 Год назад

I loooove discrete optimization, very happy you made a video on it. The problem with ACO as opposed to SA is that every single step of ACO is, in my (small) experience, slower. SA usually makes very local changes to the current solution, so calculating the makeup and cost of the next solution is very efficient, sometimes, like with 2-opt, even independent of size of the problem. ACO, on the other hand, has to compute its solutions from scratch, which makes it incredibly slow.

@fugoogle_was_already_taken Год назад

Thank you for this video, it has been a fine "survey" on TSP in aestheticaly pleasing and compact way.

@gabotron94 Год назад

Your narration has improved a lot! These keep getting better.

@hacker2ish Год назад

Great, very comprehensive overview with all the important details, learned a lot

@roberthildebrand1780 Год назад

Absolutely amazing video! Fantastic resources are posted in the information as well.

@Amplefii Год назад

I was reading grokkings algorithms book last night and ended up looking for a video on TSP and didnt find anything good, then you uploaded this. Gotta love when that happens.

@9785633425657 Год назад

A wonderful video. I've tried to understand many of the algorithms mentioned in the video, but couldn't get it. Thanks to you I now see and understand the logic of those solutions! Thank you! :)

@srinivasyeleti Год назад

Quality of the Content is Mind Bending .

@tru1988 Год назад

Great exploration of the problem space and amazing explanations of common approaches to solving it.

@sanchitsinghiitg Год назад

Awesome video! Nice summarisation of very complex ideas.

@raykos4257 6 месяцев назад

Phenomenal video. This deserves more views.

@13thk Год назад

Anıther great video, as always. This reminds me of my time trying to solve how to obtain the least amount of versions for a list of given version ranges and a set of available versions, for some reason. It operated by intersecting version ranges results together and taking the larger groups until all groups left didn't intersect.

@PowerhouseCell Год назад

Beautiful explanation of the Travelling Salesman Problem! 💛

@user-hl2yj8kp2s 4 месяца назад

I love this channel. This is better presented than a college education. Super high quality video. Thanks!

@laurenswissels8480 Год назад

The production quality of your videos is insane. Keep it up!

@rodgerwilliam198 Год назад

Hello Lauren

@BoazNahumPlus Год назад

Making this video must been a hell of a work. Thank you!

@Igigog Год назад

What an absolute banger of a video. Liked every second of it.

@louighi91 Год назад

Such a high quality content! Thank you :) remembers me to the time where I learned that during studying

@ralphwiggum3134 Год назад

I had trouble programming a tic-tac-toe game where I didn't want to rely on simple strategies for the computer's moves. I wanted to create a logic function that could be expanded to 4x4, 5x5, or more grids. I gave up for the time, but plan to try again some day. I think this video is very informative and can give me some clues to creating the logic that I would like to create.

@TrulyUnderstandingAlgorithms Год назад

Great video! In my experience, greedy plus local search is a dead simple way to obtain very good solutions to many optimisation problems. To nitpick a little bit, TSP is not impossible, just intractable in its generality (for all we know).

@gosunov Год назад

Great video, simulated annealing is really interesting and easy to implement idea

@user-un5tf3zz6k Год назад

Thank you for such a high quality video. It was interesting to watch and very informative. Thank you!

@cubiccentral4480 6 месяцев назад

This is one of the greatest computer science videos I have ever seen. Wow.

@ayoCC Год назад

this video was specially intuitive and engaging. Extremely entertaining presentation!

@daemitrious Год назад

what an incredibly well done video mate

@skatlag Месяц назад

You're the only cs channel using manim at that level. Respect bro, keep going

@RecursionIs Год назад

Great intro to the TSP! You should check out the IPPA algorithm applied to this problem, it can create some great animations 😁

@stacksmasherninja7266 Год назад

I'm a grad student studying this and honestly this is probably the best online explanation on this topic. 10/10 would watch again for reference

@JordanMetroidManiac Год назад

Amazingly easy to understand, thanks to you! One idea: What if we initialize R in the AS algorithm to correspond to the MST? I think that would yield faster convergence to a good solution and/or better solutions on average.

@JM-qu5sc Год назад

Awesome explanations, thank you for the content!

@dennisjecool Год назад

Thank you for the amazing animations and clear explanation!

@canberkuyar5469 10 месяцев назад

amazing video... thanks for clear and interesting visualization!

@kennethcula822 Год назад

I was just reading about approximation algorithms in Kleinberg’s and Tardos’s ‘Algorithm Design’ book. Great job at succinctly and informatively presenting the topics!

@andmefikri7555 Год назад

Great video! Learned so much from this.

@harold2718 Год назад

And yet in real life we (in Operations Research) solve such problems and harder ones such as vehicle routing daily, using solvers that are based on linear programming. Finding optimal solutions is very practical actually, it's mostly *theoretically* impossible, but the worst cases do not arise organically (you can construct them though).

@JimLeonard Год назад

Happy to see simulated annealing here. I improved the quality of an audio encoder I wrote that used vector quantization by introducing simulated annealing to refine the initial codebook.

@Ruchir205 Год назад

A classical problem from the field of Operations Research and one the most studied

@CyCloNeReactorCore Год назад

thank you for this reducible

@rupen42 Год назад

Annealing also reminds me of stochastic descent. Find the direction that decreases what you're trying to minimize, then add some fuzz to help to escape local minima.

@gaspump Год назад

I always felt a bit daft at formal math but I'm amazed at how this video visualized my own intuition

@Joker22593 Год назад

Complexity Theorist here. Did you know you can solve this in polynomial time using parallel computing on exponential processors? You just try every route at the same time. Since we all have video cards with thousands of cores, it's mostly practical to use this method for small data sets.

@yahav897 Год назад

Sweet, a new video! You're incredible.

@Ethan_Simon Год назад

Wow, I've been wanting to learn about this and take a crack at it myself!

@john-peterkrause7237 Год назад

This video was fascinating!

@9034833838 Год назад

Alpha Pheonix's Voting Block algorithm was a beautiful demonstration of this

@antonios3717 Год назад

beautiful video, great moments in my degree studying this problem

@aviralsood8141 Год назад

Absolutely incredible stuff

@Ellisha2488 Год назад

That was really interesting, I love your channel :)

@LiborTinka Год назад

I remember simulated annealing from learning nonlinear numerical optimization - it's a popular way to discover local minima that wouldn't be otherwise found with systematic approach.

@user-iu1xg6jv6e Год назад

I had issue understanding your pronunciation of "accept", so I did a huge mistake and went searching for how to pronounce it! I'm more confused now! Anyway, great video.

@mastershooter64 Год назад

it's pronounced "accept" you're welcome

@pauljones9150 Год назад

I didn't know that simulated annealing and ant colony optimization was useful in travelling salesmen problems! Very cool

@KurtWoloch Год назад

I once coded a similar algorithm. My version started with a single point (the origin point) and then added the other points one by one, in no particular order, but for each point an existing section of the path was broken up and the point inserted into it, and it checked for each existing segment how much length would be added if the new point was inserted into that segment, and the segment with the shortest length increase would be chosen to insert the new point into. Don't know how good of a solution this was though... By the way, I used this for a simulation of a scooter service man employed by an e-scooter sharing company who had to service (collect, deploy or battery swap) several given scooters on the map, and it would give a list of directions, a series of coordinates where to go to and instructions of what to do there, and the coordinates were sorted by this algorithm.

@kaifscarbrow Год назад

I'm probably having a bias from the examples shown but I kept thinking that the optimal path is when you imagine a circular string that surrounds all the points starts shrinking onto the points. Ofc, this will only connect the outermost vertices and the inner ones will be left out. [Edit: So how do we get to the inner nodes from here? Let the strings grow until it hits one of the inner nodes. DO NOT RECURSE from here. Move to the next segment. Do this until all the inner nodes are visited] So I had another idea. Imagine making a polygon out of the vertices. I'm guessing that the polygon whose sum of external angles is the least will be the optimum solution. Well I could just be guessing. Very nice video. Thanks for introducing the topic.

@VincentKun Год назад

Coding Adventure did the ants colony so i was familiar but the simulated annealing is just so pretty as a natura approach to this problem, i want to try to implement these two as soon i've some spare time.

@identityelement7729 Год назад

I am thinking that I saw a video where to calculate a lower bound was done by Linear Programming. Then the next task was to find a route which has this minimal cost. And from that video I remember that 100 nodes are paractically computable to get an optimal route.

@DiamondSane Год назад

It was nice to know, thanks

@Chizypuff Год назад

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

@awwastor Год назад

5:30 At one point we might get a good solution for the optimal road, if P =NP, then we will get it for large enough N anyway but even if not, there are some very fast solutions to many complex, NP-Complete problems. Like the N queens problem or the exact cover problem (or the generalised cover problem)

@MaxSzalinski Год назад

Such a nice video! I appreciate the fundamental approach to describe the TSP and showing various ideas to solve it. At the end I thought that it would be nice to hear a brief mention of Dynamic Programming (or at least Reinforcement Learning) for TSP.

@O5680 Год назад

A general solution to the Travelling Salesman problem for ANY graph: 1.) Throw away the graph. 2.) Create a single node. 3.) Since there is only one node, the solution for this graph is optimal. This algorithm runs in O(1) time. I can't overstate how important this development is to the world.