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.
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).
"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.
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!
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.)
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.
@@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 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
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 TH-cam. 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.
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.
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!
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!!
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).
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)
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!
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.
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 :)
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.
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 TH-cam. Thank you so much!
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.
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.
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.
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.
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.
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.
Within the first 30 seconds of this video believe i have encountered this exact problem organically on my own, I've not watched the video to confirm its exactly the same problem but i figured I'd write this now if anybody wants a look into the thought process of somebody who encountered at least a similar problem at some point without knowing anything about this problem the solutions that have been devised for it or even what to call it (i had no idea it had a name, the closest thing i could think of to call it was non spatial pathfinding but at the time i didn't find much when i tried searching for it) so in effect i had to try figure it out on my own in a vacuum without knowing anything of it The encounter is basically this, i had a list of arbitrary colors of arbitrary and wanted to sort them in an order that creates a smooth gradient, which put into abstract can be viewed as being simply just a set of points that contain a set of its distances from every other point (I precalculated all the distances, so i was just working with a 2d table with each cell being it's distance between its 2 indexes) with the goal being to find an ordering of these points with the least total distance So again i didn't even know what to call it at the time but i figured out very quickly that it wasn't as simple a problem to solve as you might think at first look, and i ended up trying 3 solutions and deriving a 4th that i haven't bothered to test, in the order i thought of them - single pass selection - conventional sorting - brute force - single pass selection + smoothing pass I quickly figured out that conventional sorting algorithms wouldn't help so that one didn't last long and there isn't really much to talk about on it The third one, trying to brute force the absolute shortest order i quickly found is quite possibly the least efficient thing you could do with a computer that's not deliberately designed to be inefficient with any more than like 8 points, with larger ones having the potential to take up more computing power to complete than the entire planet has available even with my attempt to optimize the brute forcing (it did work at finding the objectively shortest route, but i was expecting to put up to 100 points into it and being the time to try every single order increases exponentially i determined it'd very quickly enter taking years, when i needed it to be measured in seconds at most) eventually i just settled on what was my first instinct solution which was to take a starting point and then simply pick the shortest not yet traveled point from it and traverse there and repeat until there were none left unvisited, being it was good enough and only took one pass so it was quite quick, the only real problem being it'll often shove a few odd ones on the end one improvement I thought of a couple days after decided on that (though I've not actually implemented or tested this) was to do basically do a second pass where it goes through the list again a few times after selecting the initial order to see if moving any to be between other points would make the total shorter to smooth out the straggler that usually ends up on the end, basically a reinsertion or smoothing pass And that's where i ended up after trying to figure it out on my own, figured it could be interesting for maybe at least someone to read the perspective of solving it as someone who doesn't really know a whole lot about algorithms or math or logic or data science
I would say i wish i had this video when i was working on that, but the solution i found was good enough and honestly i think the perspective i have of trying to solve a pretty significant algorithmic problem in a vacuum unaware of any of the methods already derived or even what the problem is called kinda makes it more interesting than if i just knew when i was doing that i think
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).
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!
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!
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.
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.
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.
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.
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.
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.
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.
Great video, I love the conclusion, I think you did a great job of tying everything together. The question of "what is the hardest problem in computer science" makes me think of things like the class of undecidable problems, or problems requiring exponential work to validate a solution, rather than just polynomial. Perhaps there are efficient ways to provide probabilistic answers to these questions, following your conclusion. I suppose the issue is we know that they're hard, too hard. So, practically, what you've presented is the hardest kind of question we're willing to work on. I find those kinds of questions interesting, reducibility, and other academic hemming and hawing. However, I suppose the real value that I find in your channel is the "applicability" of what you present, not just the ease of understanding. At my university, for someone motivated like me, it wasn't too difficult for me to get resources to learn about the computational complexity zoo, and other stuffy and "not useful" topics, but it was difficult to find out about these applied topics that you frequently present, as understandably as you do. I suppose at this point I'm just musing to myself, I guess the conclusion is, despite my enthusiasm for more academic topics, I wouldn't change a thing about your approach, I think you're doing great, lol.
We do work on (much) harder problems than TSP, but TSP is interesting because it's one of the most approachable NP-hard problems, along with SAT I guess. And NP is interesting, because we don't know whether P=NP. We already know that there are infinitely many classes that are strictly harder than NP.
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!
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
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.
I really love your channel. I wish I had such enlightening explainations about TSP when I was in engineering school 25 yrs ago... Anyway, how good are genetic algorithms on such problem ? Or a neural network ? After all, TSP is a minimizing problem and a multilayer perceptron is good at this. We could also train a perceptron or a genetic algorithm to tune a simulated annealing or an ant colony...
Finding a global minimum among many local minimum strongly recommends me about the various optimizers in machine learning. Usually gradient descent or some interactive version (momentum, aggregation). I wondered if there might be a better solution that's computationally viable. And perhaps this annealing simulation could do it. But the dimensionality is crazy
Absolutely love your videos. If you're willing to accept feedback, there's far too much background music. Makes it hard for me to think and focus on what you're saying. Only expressing this to help you improve, cause you're crushing it!
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.
There is an algorithm which is based on a simple idea that I like. The reason why the brute force algorithm does not work is not really the number of nodes but the number of edges. Of course, in the initial setting, the 2 are linked but it need not be the case. One reason why finding a minimum spanning tree is easy is because we can drastically reduce the number of edges. In Prim's algorithm, at each step, most if not all but one edges can be discarded. The idea is thus the following. - Take k tours obtains by good heuristics. - Construct the union of these k tours. - Brute force the solution in this reduced graph.
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! :)
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.
6:15 Just pet peeve of mine. It doesn't beg the question. It raises the question. Begging the question means something completely different (circular reasoning).
The thumbnail written that it's a problem "impossible to solve" but I've read on Wikipedia that with supercomputers they solved the problem for more than 24000 cities (points).
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
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).
12:30 From wikipedia "Christofides algorithm ... is named after Nicos Christofides and Anatoliy I. Serdyukov, who discovered it independently in 1976." I read about Christofides, and was somehow surprised that there wasn't much "glory" for him for such groundbreaking algorithm. I was expecting that he will then became a professor at some of the best known universities in Computer Science etc. He became a professor at Imperial College London only in 2009, at the age of 67 and then died 10 years later on 2019. Regarding Anatoliy I. Serdyukov there was no article in Wikipedia, and when I tried google it it was some other random guy.
Great video, this got me thinking about slime mold. Since we don't have fungus based computing chips (yet), I wonder if anyone has tried to train a neural network to think its a slime mold. I assume it would be good at solving problems like this, and relatively fast. Would also be good at modelling economic systems for optimizing resource expenditure and growth.
The ant pheremone technique is one example of a "metaheuristic" search technique. There's a really good review of all of them in PLOS ONE by Wahab et al., And from what I can tell Differential Evolution and particle swarm optimization perform the best YMMV.
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.
Can you do Max cut problem :)))
Congrats on the sponsorship dude!
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).
What software do you use to create animations?
Tell me a good digital signal processing text book
I know the optimal algorithm for a graph with two nodes.
Lol
Believe it or not, I have an algorithm even for three vertices!
Prove it!
@@gemigames154 too long to write in a comment
@@cyanmargh i am such a genious that i may be able to solve 4 vertices graph!
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!
@@abdulhfhd ohh nooo why did you correct him? you didn't owe him anything
@@abdulhfhd fs bestie, remember what you like to say. you don't owe anyone anything
@@abdulhfhd yeah but you still don't owe anyone anything. remember that. thats your motto 😂
@@abdulhfhd 💦 don't give it up hunny
@@abdulhfhd ;p
"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.
Thanks to the greedy algorithm, humanity discovered fossil fuel.
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!
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.)
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.
@@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.
@@herseem Bose-Einstein is like second year Physics undergraduate material, hardly arcane forbidden knowledge
@@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
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 TH-cam.
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.
there are harder problems
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.
I have an MSc in Computing Science, but I have never seen a treatment of TSP and friends as beautiful as this. Thank you.
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!
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!!
I was thinking the same, Ant colony optimization reminded me of genetic algorithm.
I will definitely apply this to my thesis problem: Point cloud registration and 3D reconstruction. Thank you very much.
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).
This is cool idea!
Really clever!
@@viniciusfriasaleite8016 Obrigado.
@@kemsekov6331 Thank you.
I mean, a bubble tries to minimize tension around the outside, which is basically just a 3D version of the same problem.
your videos are always a treat and often expose me to more knowledge that I didn't know exists before. thank you.
PSPACE problems, common in planning, are arguably "harder", as TSP is "only" NP-hard.
And then you have infinitely many degrees of uncomputable problems on top of that.
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)
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%
Assuming NP != PSPACE
@@Vaaaaadim i think that that is proven, but i am not sure.
but the Problem, if a program runs infinity, is unsolveable.
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!
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.
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 :)
A perfect TSP 101
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.
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 TH-cam. Thank you so much!
How to like a video multiple times? The explanation and animation was phenomenal. Great job!
The sheer amount of work that goes into creating these simulations.... Thank you!
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.
this video was specially intuitive and engaging. Extremely entertaining presentation!
This is one of the greatest computer science videos I have ever seen. Wow.
What an incredible intro to this problem. Wow, so clearly laid out. Thank you for all your work on this!!
Quality of the Content is Mind Bending .
Making this video must been a hell of a work. Thank you!
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.
I love this channel. This is better presented than a college education. Super high quality video. Thanks!
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.
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.
Always great to see you post!
Great video, simulated annealing is really interesting and easy to implement idea
Thank you for this video, it has been a fine "survey" on TSP in aestheticaly pleasing and compact way.
You're the only cs channel using manim at that level. Respect bro, keep going
Phenomenal video. This deserves more views.
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.
Sooooo well explained and animated, so good!
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.
Within the first 30 seconds of this video believe i have encountered this exact problem organically on my own, I've not watched the video to confirm its exactly the same problem but i figured I'd write this now if anybody wants a look into the thought process of somebody who encountered at least a similar problem at some point without knowing anything about this problem the solutions that have been devised for it or even what to call it (i had no idea it had a name, the closest thing i could think of to call it was non spatial pathfinding but at the time i didn't find much when i tried searching for it) so in effect i had to try figure it out on my own in a vacuum without knowing anything of it
The encounter is basically this, i had a list of arbitrary colors of arbitrary and wanted to sort them in an order that creates a smooth gradient, which put into abstract can be viewed as being simply just a set of points that contain a set of its distances from every other point (I precalculated all the distances, so i was just working with a 2d table with each cell being it's distance between its 2 indexes) with the goal being to find an ordering of these points with the least total distance
So again i didn't even know what to call it at the time but i figured out very quickly that it wasn't as simple a problem to solve as you might think at first look, and i ended up trying 3 solutions and deriving a 4th that i haven't bothered to test, in the order i thought of them
- single pass selection
- conventional sorting
- brute force
- single pass selection + smoothing pass
I quickly figured out that conventional sorting algorithms wouldn't help so that one didn't last long and there isn't really much to talk about on it
The third one, trying to brute force the absolute shortest order i quickly found is quite possibly the least efficient thing you could do with a computer that's not deliberately designed to be inefficient with any more than like 8 points, with larger ones having the potential to take up more computing power to complete than the entire planet has available even with my attempt to optimize the brute forcing (it did work at finding the objectively shortest route, but i was expecting to put up to 100 points into it and being the time to try every single order increases exponentially i determined it'd very quickly enter taking years, when i needed it to be measured in seconds at most)
eventually i just settled on what was my first instinct solution which was to take a starting point and then simply pick the shortest not yet traveled point from it and traverse there and repeat until there were none left unvisited, being it was good enough and only took one pass so it was quite quick, the only real problem being it'll often shove a few odd ones on the end
one improvement I thought of a couple days after decided on that (though I've not actually implemented or tested this) was to do basically do a second pass where it goes through the list again a few times after selecting the initial order to see if moving any to be between other points would make the total shorter to smooth out the straggler that usually ends up on the end, basically a reinsertion or smoothing pass
And that's where i ended up after trying to figure it out on my own, figured it could be interesting for maybe at least someone to read the perspective of solving it as someone who doesn't really know a whole lot about algorithms or math or logic or data science
I would say i wish i had this video when i was working on that, but the solution i found was good enough and honestly i think the perspective i have of trying to solve a pretty significant algorithmic problem in a vacuum unaware of any of the methods already derived or even what the problem is called kinda makes it more interesting than if i just knew when i was doing that i think
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).
Such a high quality content! Thank you :) remembers me to the time where I learned that during studying
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!
This video is so good that I want more people to see it, so I'm commenting to drive engagement.
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!
The production quality of your videos is insane. Keep it up!
Hello Lauren
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.
what an incredibly well done video mate
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.
Great intro to the TSP! You should check out the IPPA algorithm applied to this problem, it can create some great animations 😁
Alpha Pheonix's Voting Block algorithm was a beautiful demonstration of this
This video is awesome. Great explanation and great montage (it's a lot of work to show all this nodes and highlight them)
I always felt a bit daft at formal math but I'm amazed at how this video visualized my own intuition
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.
it's pronounced "accept"
you're welcome
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.
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.
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.
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.
What an absolute banger of a video. Liked every second of it.
Such an great video! You're doing an amazing job explaining those problems! Can't wait for your other videos!
your channel mean alot for me specially recursion one.
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!
Great video, I love the conclusion, I think you did a great job of tying everything together.
The question of "what is the hardest problem in computer science" makes me think of things like the class of undecidable problems, or problems requiring exponential work to validate a solution, rather than just polynomial. Perhaps there are efficient ways to provide probabilistic answers to these questions, following your conclusion. I suppose the issue is we know that they're hard, too hard. So, practically, what you've presented is the hardest kind of question we're willing to work on.
I find those kinds of questions interesting, reducibility, and other academic hemming and hawing. However, I suppose the real value that I find in your channel is the "applicability" of what you present, not just the ease of understanding. At my university, for someone motivated like me, it wasn't too difficult for me to get resources to learn about the computational complexity zoo, and other stuffy and "not useful" topics, but it was difficult to find out about these applied topics that you frequently present, as understandably as you do.
I suppose at this point I'm just musing to myself, I guess the conclusion is, despite my enthusiasm for more academic topics, I wouldn't change a thing about your approach, I think you're doing great, lol.
We do work on (much) harder problems than TSP, but TSP is interesting because it's one of the most approachable NP-hard problems, along with SAT I guess.
And NP is interesting, because we don't know whether P=NP. We already know that there are infinitely many classes that are strictly harder than NP.
Absolutely amazing video! Fantastic resources are posted in the information as well.
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!
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
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.
I really love your channel. I wish I had such enlightening explainations about TSP when I was in engineering school 25 yrs ago...
Anyway, how good are genetic algorithms on such problem ? Or a neural network ? After all, TSP is a minimizing problem and a multilayer perceptron is good at this. We could also train a perceptron or a genetic algorithm to tune a simulated annealing or an ant colony...
It's unsupervised. I think we cannot handle graph structures with ANNs.
You did a great job on this video. I learned a lot and it solidified other understandings I had. Awesome!
Finding a global minimum among many local minimum strongly recommends me about the various optimizers in machine learning. Usually gradient descent or some interactive version (momentum, aggregation). I wondered if there might be a better solution that's computationally viable. And perhaps this annealing simulation could do it.
But the dimensionality is crazy
Awesome video! Nice summarisation of very complex ideas.
1. Massively parallel computers
2. Digital/Analog hybrid computers
3. Fully-Associative memory
Absolutely love your videos. If you're willing to accept feedback, there's far too much background music. Makes it hard for me to think and focus on what you're saying. Only expressing this to help you improve, cause you're crushing it!
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.
There is an algorithm which is based on a simple idea that I like.
The reason why the brute force algorithm does not work is not really the number of nodes but the number of edges. Of course, in the initial setting, the 2 are linked but it need not be the case.
One reason why finding a minimum spanning tree is easy is because we can drastically reduce the number of edges. In Prim's algorithm, at each step, most if not all but one edges can be discarded.
The idea is thus the following.
- Take k tours obtains by good heuristics.
- Construct the union of these k tours.
- Brute force the solution in this reduced graph.
Great presentation on TSP, this was a pleasure to follow!
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! :)
Great, very comprehensive overview with all the important details, learned a lot
Great exploration of the problem space and amazing explanations of common approaches to solving it.
Thank you for such a high quality video. It was interesting to watch and very informative. Thank you!
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.
6:15 Just pet peeve of mine. It doesn't beg the question. It raises the question.
Begging the question means something completely different (circular reasoning).
here's an idea: use only nearest neighbor , but make all the possible paths each starting with a different node. then select the best one.
thank you for this reducible
amazing video... thanks for clear and interesting visualization!
The thumbnail written that it's a problem "impossible to solve" but I've read on Wikipedia that with supercomputers they solved the problem for more than 24000 cities (points).
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
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).
Thank you for the amazing animations and clear explanation!
If I could make presentations like this, I could die happy.
12:30 From wikipedia "Christofides algorithm ... is named after Nicos Christofides and Anatoliy I. Serdyukov, who discovered it independently in 1976."
I read about Christofides, and was somehow surprised that there wasn't much "glory" for him for such groundbreaking algorithm. I was expecting that he will then became a professor at some of the best known universities in Computer Science etc. He became a professor at Imperial College London only in 2009, at the age of 67 and then died 10 years later on 2019.
Regarding Anatoliy I. Serdyukov there was no article in Wikipedia, and when I tried google it it was some other random guy.
You make the best videos on the internet my dude, you should be funded by governments to redesign the curriculum, no joke.
Great video, this got me thinking about slime mold. Since we don't have fungus based computing chips (yet), I wonder if anyone has tried to train a neural network to think its a slime mold. I assume it would be good at solving problems like this, and relatively fast. Would also be good at modelling economic systems for optimizing resource expenditure and growth.
People have actually came up with methods for using certain mushrooms as computers, which is kind of hilarious
This video is pure gold
Ant colony optimization seems like it would be really good for heavily multithreaded situations, like maybe on a GPU. Is that viable?
Yes. Very.
I didn't know that simulated annealing and ant colony optimization was useful in travelling salesmen problems! Very cool
Crazy how the ants actually did achieve the 2-opt swap at 28:19
Sweet, a new video! You're incredible.
The ant pheremone technique is one example of a "metaheuristic" search technique. There's a really good review of all of them in PLOS ONE by Wahab et al., And from what I can tell Differential Evolution and particle swarm optimization perform the best YMMV.
'Ant colony optimization'
I literally came here to improve my Screeps.