An idea I had for the travelling salesman problem (when the points are in some euclidean space): 1) Enclose the smallest possible convex hull around all of the points. 2) For each point not on the edge of the current hull, pick the one that is closest to the hull (or, that would increase the length of the path the least if inserted into the closest hull edge). 3) Bend the hull to include that point. The point would be inserted between the two points already in the hull forming the edge that it is closest to. 4) Go to step 2 until there are no points left not part of the hull. For added precision, you could enumerate through all of the first N possible vertex insertions and use the combination of insertions that results in the shortest path. The above algorithm assumes N == 1. I just tried doing this manually in MS Paint and it seems to work pretty well. I got almost the same result you did at 1:17 (though I did eyeball it).
This seems like a good optimization for these kind of special cases - perhaps very similar to this: www.sciencedirect.com/science/article/abs/pii/0020019096001251?via%3Dihub
If you ever played Galactic Civilizations 3, you have to deal with this problem too when you start to set up your Hypergate networks. Thanks for the suggestions about moving the edges. That will help!
One of the sub problems that i had in my dimploma project duting my bacholer's involed this problem. I solved it using two methods: integer programming and genetic algorithms. It was so fun and exciting. I'm so eager to learn more math during my master's.
Also, I researched local neighborhood search and big neighborhood search. I was also thinking about applying neural networks, but it was too difficult for me
I can't believe my ears! Is this post rock music in an algorithm video I hear? Had to watch multiple times. It made my day! Now if only every piece of information was accessible through a video like this. :/
Random Person That there is why combinatorics is hard - not because the algorithms and formulas are complex but because the resulting numbers are so large you can't store them in any naïve format.
Thomas, Well, if you took every particle in the universe (about 10^80), made a quadrillion duplicates, then duplicated all of your new particles and old particles a quadrillion times, and did it again, and again, and again, and again, and again, and again, you still wouldn't have even close to that number (you'd have 10^200). You wouldn't even be in the ballpark. But this doesn't even remotely compare to all the possible arrangements of every particle in the universe, which is absolutely monstrously large. If you duplicated every particle in the universe a quadrillion times every second until the universe died, you would not have reached a number of particles that was even close to the number of possible arrangements of every particle in our universe. Every arrangement is something like 10^(10^80), that is 10 to the power of 1 followed by 10^80 zeroes. The number you'd get duplicating particles a quadrillion times per second to the end of the universe is a mere 10^(10^20) if you assume the universe will live for 100 trillion years.
This video is very fascinating. I appreciate it because on a real simple way, i.e. visualization, it provides the core of the TSP. But it contains a little mistake though. If the quantity of possible routes is calculated with (n-1)! with n:= number of cities then for 304 the solution should be about 8,43*10^(621) ____________________________________________________________ "Wenn Null besonders groß ist, ist es beinahe so groß wie ein bisschen Eins. Tadeln ist leicht, deshalb tun es so viele; mit Verstand loben ist schwer, darum versuchen es so wenige." (Anselm Feuerbach)
0:16, greedy-algo is taking the next closest point? but as he connects the first 8 points, the 7th is more far away from the 6th than the 8th from the 6th, isn't it? :D Aynway, really cool video!
I think you're right! I had chosen the top 8 locations from the population data I had found. The distances were calculated naively based on their lat/long coordinates. Either the calculations for Chicago->New York and Chicago->Philadelphia somehow put them opposite closeness, or I fudged it somehow . Not sure now, but Philadelphia is definitely a little closer!
It's beautiful, but please don't change the number of vertices from one demonstration to the next. This confuses the viewer as to whether the final result is truly optimal. I thought the last result is sub-optimal, because it didn't look like the one you showed previously, which was actually for a smaller number of cities.
Cool! Now do one on vertex cover focused on internet infrastructure! ;) I remember having a blast coding heuristics to find suboptimal solutions in the uni. Really enjoyed the video.
What if you split the area into quadrants and then connected them? You could also use a rotating axis that finds the 4 most optimal quadrants and then it syncs them. This 2-opt swap just ends up making a giant trace around the outside of the area; no more clever than connect the dots.
Yes! If you have prior knowledge about likely patterns in your data then you can potentially reduce the problem size by many factors. This visualization only demonstrates for the generic case. If this problem were being addressed for real, a likely optimization would be to cluster all the metropolitan areas together and solve those discretely, then add them back into the complete solution by removing the "interior" nodes. These problems are fun to think about - especially how additional/alternate optimizations might make make it faster!
Would it be more accurate to use a brute force algorithm? Iterate over each possible route, and throw away the previous route if the the current one is shorter?
Certainly! This will work fine for a small number of cities to test. However, as the number of cities grows, the number of possible solutions increases with a factorial amount - the time needed to check all of these grows from hours to days to years. There are optimizations (for instance, branch and bound - don't even consider a set of solutions unlikely to yield better result), but even then, the possible considered solutions can be quite large. Read more here: en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms
Good question. Each set of vertices is a subset of the next - they're US cities sorted by population in descending order. I used the different numbers of these cities to illustrate the strengths (and weaknesses) of the techniques. For instance, it'd be harder to visually see the local minimum demonstrated in the local search section with the 300 vertices used in the simulated annealing section. Likewise, the apparent chaos resolving to a solution in simulated annealing wouldn't be quite as captivating with the 30 vertices used in local search.
I'm thinking a sequence of pi should be rendered around the travel area. Then the program extrapolates the rout to the perimeter of the travel area. Once the outline is created, the remaining locations could run greedy sequence. The key is starting with a circle and working from there, wish I could write code or I'd try it haha.
+Fatbackwards I agree, it's really interesting to think about optimizations for large problem sizes such as this! I wrote the music using software synthesizers and lots of arpeggiators :) Here is a link to the soundcloud of the song soundcloud.com/poprhythm/clearly-opaque
Doesn't the order of the swapping affect the outcome? You say to select edges at random for the swap, but I'm assuming you're actually comparing every edge to every other edge once, right? (Otherwise, how do you know when to stop?) So, if you go through the whole thing once, wouldn't going through it again produce further changes? As other parts of the route switch around, the changed distance between each edge also varies, no?
Hi! You might be interested in reading this more detailed look into the 2-opt swap mechanism : en.wikipedia.org/wiki/2-opt . You've hinted at the underlying problem - how do you know when to stop? For non-trivial optimization problems, you're often faced with accepting a "very good" solution as opposed to the optimal - simply because the search space for larger problems becomes astronomically large. Like hundreds of years on modern hardware large. So using a heuristic-based search to find good solutions in a reasonable amount of time is currently our best bet.
I have an idea for finding the optimal route consistently, a new approach, a new algorithm. How would I get it to work like your video? I'm not a programmer. Is there software to do this? If not would you be willing to consider writing it if I describe it to you? Thank you. ..
+Dave Ped There exist some toolkits for tinkering with optimization algorithms such as this. I'm not very familiar with them - this one came up in a google search, and it contains a TSP function optalgtoolkit.sourceforge.net/
+poprhythm Thank you. I need a nerd to check out my idea. I'm not nerd enough to do this. I just come up with ideas. I understand most people's ideas are not worth pursuing so if you want me to describe it in detail first, no obligations, fine I can do that. Thanks.
hello... how to write programs using HEAPSORT to solve Travelling Salesman Problem - TSP on programming language ... and I need code :( im form Viet Nam...thanks
Your car GPS does a small bit of this every time you put in an address to go to. It will not find the BEST solution but one that is as good at is can find in the time before you lose patience and reboot it thinking it's crashed.
R is a great tool, but no, this was made in C#. Here's an article about creating it: popcyclical.com/2013/08/19/TravelingSalesmanProblemVisualization.aspx
please, next time, make the background music louder, I feel I could still discern some notes through the distortion, also choose it more randomly, I feel it wasn't a 100% inappropriate
Hey, could you enable the video to receive contributions from the community? I'd like to include a Portuguese subtitle. And thanks for providing this awesome video.
My code isn't in a state that'd be appropriate to share - however, here are some of my notes: popcyclical.com/2013/08/19/TravelingSalesmanProblemVisualization.aspx Also, here's some java code implementing many of the same ideas: www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6 And another: toddwschneider.com/posts/traveling-salesman-with-simulated-annealing-r-and-shiny/
We'd need to know the distances of each route to guarantee it was the shortest. Given the complexity of the problem, with ~10^624 possible routes, testing say 100 routes every second, it'd take many times the age of the universe to verify each one. So we use techniques like this to intelligently reduce the number of routes being checked. We end up with very reasonable solutions, but no, we don't know that it's the absolute best.
Part of the problem's history includes finding a solution to school bus routing in the 1930's, and followed by countless other route optimization problems in the real world. And unless the points have a strict radial organization, the solution is never simply a circle. en.wikipedia.org/wiki/Travelling_salesman_problem#History
Wonder what would actually happen if a real travelling salesman used this. [A travelling salesman walks up to a door and knocks] _Man:_ Hello? _Salesman:_ Hello! Would yo be interested in buying math algorithms that solves the problems of least distance between major cities? _Man:_ What? _Salesman:_ I wasted my entire life looking for the perfect route rather than just actually traveling.
Love how the music speeds up when the code is in action, it actually makes it enjoyable and not a bunch of boring moving lines.
the background music make it looks extra cool
I always come back to this video due to the sheer amount of beauty it contains.
ruclips.net/video/gm0Nc4wPJZI/видео.html
hello
I first watched it to understand methods of solving TSP. Then I watched it 4 more times because it's so optically pleasing.
+1
and then like 62345 times because of music lol
Not just "optically", it's "optimally" pleasing too ; )
ruclips.net/video/gm0Nc4wPJZI/видео.html
I watched this 2 or 3 years ago. Now, I am here again.
Great video! Visualization and your choice of music make me watch this over and over again.
This is the absolute best TL;DW (too long, didn't watch) video for anybody looking for a quick intro into what is local search. Great work!
This is the most beautiful algorithm video I have seen on youtube.
Finally a video that explains the core logic so easily, thanks a tonn!
This isn't just a good visualization but also a good production video.
Thus it's might invite more audience into the field.
'Thus it's might invite' - that gave me cancer
I like science, so you are correct in saying it might invite more people into the field, because it worked for me.
ruclips.net/video/gm0Nc4wPJZI/видео.html
An idea I had for the travelling salesman problem (when the points are in some euclidean space):
1) Enclose the smallest possible convex hull around all of the points.
2) For each point not on the edge of the current hull, pick the one that is closest to the hull (or, that would increase the length of the path the least if inserted into the closest hull edge).
3) Bend the hull to include that point. The point would be inserted between the two points already in the hull forming the edge that it is closest to.
4) Go to step 2 until there are no points left not part of the hull.
For added precision, you could enumerate through all of the first N possible vertex insertions and use the combination of insertions that results in the shortest path. The above algorithm assumes N == 1.
I just tried doing this manually in MS Paint and it seems to work pretty well. I got almost the same result you did at 1:17 (though I did eyeball it).
This seems like a good optimization for these kind of special cases - perhaps very similar to this: www.sciencedirect.com/science/article/abs/pii/0020019096001251?via%3Dihub
@@poprhythm Thanks, I'll have to read it ::}
Man, travelling salesmen are smarter nowadays...
If you ever played Galactic Civilizations 3, you have to deal with this problem too when you start to set up your Hypergate networks. Thanks for the suggestions about moving the edges. That will help!
Oh this is so beautiful. Thanks for making this video!
best visualization I've seen on TSP
These kind of video are actual motivation to get into the stuff
One of the sub problems that i had in my dimploma project duting my bacholer's involed this problem. I solved it using two methods: integer programming and genetic algorithms. It was so fun and exciting. I'm so eager to learn more math during my master's.
Also, I researched local neighborhood search and big neighborhood search. I was also thinking about applying neural networks, but it was too difficult for me
I can't believe my ears! Is this post rock music in an algorithm video I hear? Had to watch multiple times. It made my day! Now if only every piece of information was accessible through a video like this. :/
Have a look if you like this video
ruclips.net/video/uUOd5dJTR7E/видео.html
Love it! These are the types of visualizations we need to get people into mathematics. So much easier to understand than a dude at a white board
2.3*10^624 possibility? That is 10^544 times more than atoms in observable universe
+Oktay So, like....a lot?
Random Person That there is why combinatorics is hard - not because the algorithms and formulas are complex but because the resulting numbers are so large you can't store them in any naïve format.
Thomas,
Well, if you took every particle in the universe (about 10^80), made a quadrillion duplicates, then duplicated all of your new particles and old particles a quadrillion times, and did it again, and again, and again, and again, and again, and again, you still wouldn't have even close to that number (you'd have 10^200). You wouldn't even be in the ballpark.
But this doesn't even remotely compare to all the possible arrangements of every particle in the universe, which is absolutely monstrously large. If you duplicated every particle in the universe a quadrillion times every second until the universe died, you would not have reached a number of particles that was even close to the number of possible arrangements of every particle in our universe.
Every arrangement is something like 10^(10^80), that is 10 to the power of 1 followed by 10^80 zeroes. The number you'd get duplicating particles a quadrillion times per second to the end of the universe is a mere 10^(10^20) if you assume the universe will live for 100 trillion years.
Can't explain/calculate something with 100% accuracy? Goddidit
Thta's why we have to find a new algorthim that shortens the avaible routes
What a magnificent way of explaining these concepts, thank you!
What an impressive approach of the problem. It's clear, and the video is so cool.
This video is very fascinating. I appreciate it because on a real simple way, i.e. visualization, it provides the core of the TSP.
But it contains a little mistake though.
If the quantity of possible routes is calculated with (n-1)!
with n:= number of cities then for 304 the solution should be about 8,43*10^(621)
____________________________________________________________
"Wenn Null besonders groß ist, ist es beinahe so groß wie ein bisschen Eins. Tadeln ist leicht, deshalb tun es so viele; mit Verstand loben ist schwer, darum versuchen es so wenige." (Anselm Feuerbach)
the drums are like routes connecting and colliding with eachother. i like it
lol I can literally just watch this for the music. Mmy favourite part starts at 1:43, watched for 4 times.
Wow, it's so intense and difficult that there had to be epic music to accompany it
0:16, greedy-algo is taking the next closest point? but as he connects the first 8 points, the 7th is more far away from the 6th than the 8th from the 6th, isn't it? :D Aynway, really cool video!
I think you're right! I had chosen the top 8 locations from the population data I had found. The distances were calculated naively based on their lat/long coordinates. Either the calculations for Chicago->New York and Chicago->Philadelphia somehow put them opposite closeness, or I fudged it somehow . Not sure now, but Philadelphia is definitely a little closer!
Curvature of the earth plays with flat maps a bit.
I would guess the points are closer in reality, but the flat projection of the US makes it appear different.
It would be easier if the edges show their weights/distances.
It's beautiful, but please don't change the number of vertices from one demonstration to the next. This confuses the viewer as to whether the final result is truly optimal.
I thought the last result is sub-optimal, because it didn't look like the one you showed previously, which was actually for a smaller number of cities.
I agree with the others...I'm a techie and route planning solver...this helps me when explaining to customers
Good visualization of the salesman problem. Thanks!
More visualising algorithms videos please :)
How about 2D sorts, these are on a 2D grid and the numbers must decrease downwards as well as rightwards.
ruclips.net/video/gm0Nc4wPJZI/видео.html
Thanks! Really appreciate your work! May I cite your work in my presentation? Please let me know how can I properly cite it!
Awesome visualization!
Hey. What softwares did it take to build such kind of beautiful simulation ?
+Sanyam Jain Hey thanks! Here's a blog article on how I made it popcyclical.com/2013/08/19/TravelingSalesmanProblemVisualization.aspx
Cool! Now do one on vertex cover focused on internet infrastructure! ;)
I remember having a blast coding heuristics to find suboptimal solutions in the uni.
Really enjoyed the video.
The general consensus I'm getting is, travel in a circle that makes your last point nearest to your starting point, and don't cross lines.
very cool video on travelling salesman problem. Interesting visualization.
As a CS nerd, I love the visualisation. Any way I can purchase a copy of the song?
+Chaoswarrior3489 Thank you very much! I've enabled downloads for the song here soundcloud.com/poprhythm/clearly-opaque
What if you split the area into quadrants and then connected them? You could also use a rotating axis that finds the 4 most optimal quadrants and then it syncs them. This 2-opt swap just ends up making a giant trace around the outside of the area; no more clever than connect the dots.
Yes! If you have prior knowledge about likely patterns in your data then you can potentially reduce the problem size by many factors. This visualization only demonstrates for the generic case. If this problem were being addressed for real, a likely optimization would be to cluster all the metropolitan areas together and solve those discretely, then add them back into the complete solution by removing the "interior" nodes. These problems are fun to think about - especially how additional/alternate optimizations might make make it faster!
I loved the music, it just plain awesome
In what computer science course do we learn about the Traveling Salesman Problem, the Post Correspondence Problem, etc..?
Excelent video on an famous algorithm.
Would it be more accurate to use a brute force algorithm? Iterate over each possible route, and throw away the previous route if the the current one is shorter?
Certainly! This will work fine for a small number of cities to test. However, as the number of cities grows, the number of possible solutions increases with a factorial amount - the time needed to check all of these grows from hours to days to years. There are optimizations (for instance, branch and bound - don't even consider a set of solutions unlikely to yield better result), but even then, the possible considered solutions can be quite large. Read more here: en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms
teacher I developed a heuristic and would like to share it. My heuristic uses topology and concentric circles. What do you think?.
Why do you choose different vertices in different algorithms?
Good question. Each set of vertices is a subset of the next - they're US cities sorted by population in descending order. I used the different numbers of these cities to illustrate the strengths (and weaknesses) of the techniques. For instance, it'd be harder to visually see the local minimum demonstrated in the local search section with the 300 vertices used in the simulated annealing section. Likewise, the apparent chaos resolving to a solution in simulated annealing wouldn't be quite as captivating with the 30 vertices used in local search.
how were you able to make the simulation? can you tell us what software/application you have used for the same?
I'm thinking a sequence of pi should be rendered around the travel area. Then the program extrapolates the rout to the perimeter of the travel area. Once the outline is created, the remaining locations could run greedy sequence. The key is starting with a circle and working from there, wish I could write code or I'd try it haha.
Why Pi though?
Hey there, this is a very interesting algorythm; I just would like to ask what background music are you using for this video?
+Fatbackwards I agree, it's really interesting to think about optimizations for large problem sizes such as this! I wrote the music using software synthesizers and lots of arpeggiators :) Here is a link to the soundcloud of the song soundcloud.com/poprhythm/clearly-opaque
love the music
Awesome. Thanks for sharing the video.
0:05 why wouldn't it be 8!?
Simulated annealing seems like it would make a good approximation algorithm
It always end up choosing the outline made by the points, why search then?
Your "greedy algorithm" doesn't choose the nearest city as claimed 00:16
Doesn't the order of the swapping affect the outcome? You say to select edges at random for the swap, but I'm assuming you're actually comparing every edge to every other edge once, right? (Otherwise, how do you know when to stop?) So, if you go through the whole thing once, wouldn't going through it again produce further changes? As other parts of the route switch around, the changed distance between each edge also varies, no?
Hi! You might be interested in reading this more detailed look into the 2-opt swap mechanism : en.wikipedia.org/wiki/2-opt . You've hinted at the underlying problem - how do you know when to stop? For non-trivial optimization problems, you're often faced with accepting a "very good" solution as opposed to the optimal - simply because the search space for larger problems becomes astronomically large. Like hundreds of years on modern hardware large. So using a heuristic-based search to find good solutions in a reasonable amount of time is currently our best bet.
...which is why sometimes your car navigator will take a different route between the same adresses.
How difficult is it to draw a circle?
I have an idea for finding the optimal route consistently, a new approach, a new algorithm. How would I get it to work like your video? I'm not a programmer. Is there software to do this? If not would you be willing to consider writing it if I describe it to you?
Thank you.
..
+Dave Ped There exist some toolkits for tinkering with optimization algorithms such as this. I'm not very familiar with them - this one came up in a google search, and it contains a TSP function optalgtoolkit.sourceforge.net/
+poprhythm Thank you. I need a nerd to check out my idea. I'm not nerd enough to do this. I just come up with ideas. I understand most people's ideas are not worth pursuing so if you want me to describe it in detail first, no obligations, fine I can do that. Thanks.
This is fine and all, but what if the name of the salesman is Crowley?
hello...
how to write programs using HEAPSORT to
solve Travelling Salesman Problem - TSP on programming language ...
and I need code :(
im form Viet Nam...thanks
How did you get the visual representation?
This woke me up - literally :D
More videos pls
So good. Very impressed
0:17 trivial*
its awesome
Thank you!
I have a feeling you need to make a shape with the smallest area
Guys, I think I found the solution to reduce the time as much as possible. But what can I do with the solution?
How did you make this video
Practically speaking, what is this information used for in practical life
Your car GPS does a small bit of this every time you put in an address to go to. It will not find the BEST solution but one that is as good at is can find in the time before you lose patience and reboot it thinking it's crashed.
Could genetic algorithms be implemented? I would like to see that.
ruclips.net/video/gm0Nc4wPJZI/видео.html
What if there is several salesmen?
Which programme used??
What software did you make this in? Looks like R?
R is a great tool, but no, this was made in C#. Here's an article about creating it: popcyclical.com/2013/08/19/TravelingSalesmanProblemVisualization.aspx
Is this a minimum spanning tree problem?
They're both distance-on-a-graph problems, but not quite the same! - here's a short discussion: stackoverflow.com/a/3838791/99492
great job, thanks for sharing
this music while solving Rubik's cube would be more thrilling ... ;-)
so beautiful. thank you
Love the visualization
Very well done!
please, next time, make the background music louder, I feel I could still discern some notes through the distortion, also choose it more randomly, I feel it wasn't a 100% inappropriate
Hey, could you enable the video to receive contributions from the community? I'd like to include a Portuguese subtitle. And thanks for providing this awesome video.
Thank you! I've enabled the Community Contributions for closed captioning, I think. Let me know if you have any problem with it.
I've just submitted the subtitles. Thanks for enabling Community Contributions. It's a great video.
This was very nice. Thanks
I love it man!
uhm... isn't it (n-1)!/2 ?
great music!
Can I get the source code
Please sent the source code to this email.
rafiyakhanum939@gmail.com
Ill use it to visit US thank you
can you please share the code
My code isn't in a state that'd be appropriate to share - however, here are some of my notes: popcyclical.com/2013/08/19/TravelingSalesmanProblemVisualization.aspx
Also, here's some java code implementing many of the same ideas: www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
And another: toddwschneider.com/posts/traveling-salesman-with-simulated-annealing-r-and-shiny/
@@poprhythm thankuuuuu
But is it the shortest
We'd need to know the distances of each route to guarantee it was the shortest. Given the complexity of the problem, with ~10^624 possible routes, testing say 100 routes every second, it'd take many times the age of the universe to verify each one. So we use techniques like this to intelligently reduce the number of routes being checked. We end up with very reasonable solutions, but no, we don't know that it's the absolute best.
@@poprhythm Thanks for the explanation, TSP is such an interesting problem
I Luv the channel name
First of all, thank you for the video. But, I think for 8 cities there are 8!/2 = 20160 possible routes, not 5040
Nope. The number of Hamiltonian Circuits in a graph with N vertices is (N-1)!. Hence for 8 cities there are 7! possible routes. Which is 5040.
very nice video
I love the little 7!
Do we need this to show us how to travel in a circle?
They created the problem first to justify an answer.
Part of the problem's history includes finding a solution to school bus routing in the 1930's, and followed by countless other route optimization problems in the real world. And unless the points have a strict radial organization, the solution is never simply a circle.
en.wikipedia.org/wiki/Travelling_salesman_problem#History
I don't see this is exactly answer.
welp rikei ga koi piqued my interest to here
irvan maulana Same
Watch video at half the speed.
It helps a lot, thanks
The company could just invite all clients for a conference, just sayin
fantastic!
Wonder what would actually happen if a real travelling salesman used this.
[A travelling salesman walks up to a door and knocks]
_Man:_ Hello?
_Salesman:_ Hello! Would yo be interested in buying math algorithms that solves the problems of least distance between major cities?
_Man:_ What?
_Salesman:_ I wasted my entire life looking for the perfect route rather than just actually traveling.