Hey! Thank you for making such amazing videos with so much explanation. I love every one of them. At 14:30, I think it wasn't just the last one. The distance will be same for 0,1,2,3 and 3,2,1,0 so if you had encountered 0,1,2,3 before and 3,2,1,0 at the end, it would seem as if it was the last one that was the best but actually there were two best.
You could optimize the code to be twice as fast by ignoring symmetric permutations of the array. IE 0,1,2 is the same as 2,1,0 so dont bother checking 2,1,0
In this case, yes, because we have a non oriented graph. In the general case of a digraph, going from city 1 to city 2 doesn't need to have the same "cost" as going from 2 to 1
+1 to this request! I’ve been working on differential growth algorithms (inspired by inconvergent.net/shepherding-random-growth/) and keep thinking to myself "If only Shiffman had a k-d tree video." (p.s. thank you for all these videos-it’s a huge inspiration!)
About the lexicographic order TSP algorithm that you showed. If you only check total_permutations / 2 times, you can get the solution in half the time. Because what matters here is that we get the minimum distance route. Example: for 3 cities, the distance for order [0, 1, 2] would be same as [2, 1, 0]. So why check both? If you have any further query regarding my premise, draw these two routes and check for yourself.
Hi, Dan, this is a really incredible series! I've already used hello.processing to introduce students and colleagues to the platform, and these are a really fun, accessible extension to show them once their interest is piqued. A question: Would it be a huge pain in the kiester to dump these coding challenge videos into your Vimeo account, too? I'm a public high school art teacher (as are a lot of my colleagues who I evangelize to about including creative code in their curricula), and public schools have a nasty habit of blanket-blocking TH-cam, while other streaming services like Vimeo tend to be permitted. If that would be a huge timesink for you, I totally get it, though (and I can just keep ripping MP4s to show in my classroom...).
I can share a google drive folder with you which might be easier. I want to do this, but don't really have the time to maintain both platforms and also worry about splitting the audience. I need to think about this more, can you contact me via e-mail or twitter?
Hello! Thanks lot for all the amazing videos! But I can't find the video with the implementation of a genetic lgorithm in this example. Is it somewhere?
for(int i=0 ; i < totalCity ; i++){ g.drawOval(city[i].x , city[i].y , city[i].width , city[i].height); n = order[i]; if(n < totalCity-1){ g.drawLine(city[n].x , city[n].y , city[n+1].x , city[n+1].y); } } this is java code.. here "order array" is changing correctly but path between cities are NOT updating..it was working before Lexicographic Order.. i am not changing "city array" anywere. plz help
Have you ever wanted to try another approach to this problem? I know you made the GA solution, but there is a set of really good solvers, such as ALNS, that are known to solve this problem in polynomial time. I would love to see you implementing LKH or something like that in your challenges. Sorry to bother here, i don't know if you got a official local to talk about this.
There are much better algorithms. The one presented in this video is all about brute force (testing all possibilities). It is slow because for N entries, we have to check N! (N factorial) possibilities. Look up for Dijkstra's shortest path algorithm. With this one, we have to check N^2 (N squared) possibilities, much better... For 10 cities, for example: Brute Force = 3.628.800 checsk, Dijkstra = 100 checks. The difference grows with the growth of N. Today there is a better implementation of Dijkstra that runs in (N*logN or M, M beeing the number of edges)...
@@gmbueno Dijkstra can't solve this problem, it only gives you the best path between 2 cities. The TSP requires the optimal route to travel all the cities. For bigger cases , ie: google maps, it's used heuristics that can approximate the result from the optimal solution. Currently it's possible to calculate the best route of milions of cities with < 3% difference from the optimal solution in a reasonable time.
I believe part of the travelling salesman is the salesman has to return to his home city and so completes a loop. Any ideas on including this in the next one as well?
It would probably run faster if it was calculated in a function outside the draw loop, and only displayed how far it got, every 0.02 seconds (50 frames).😀
Wouldn't this program be quicker if you do this? 1. Start at chosen city. 2. Look the distance between this city and all others. 3. Chosse city with shortest distance and draw path. 4. Exclude star city from looking pool. 5. Set city from point 3 as start city, go to point 2.
Imagine if the cities were spread out like the letter L, and the starting point was in the middle of the horizontal line, but the distance to the right was a bit larger than the distance to the left city. It would then start going left, continue upwards (vertical line), and then jump from the top of the L to the bottom (right next to the starting point), and then take the last few. The jump will be like the hypotenuse in a triangle, and therefore make this alt potentially longer then first going right, then jump back to start, and then take the rest. But if processing power costs more then the potentially longer distance, then I would go with your solution!
"For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution, but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps." --wikipedia (Greedy_algorithm)
@@KnakuanaRka lol no people say that at the end of the joke. Finding the TSP between 2 cities is just a straight line which is very easy so its a blonde joke
love these series, what could be interesting, if you'd might run out of idea's for these series or something; is lumance based effects on pixel inputs, like video. delaunay triangulation for example or Voronoi tessellation like this: th-cam.com/video/mTzbax2daKs/w-d-xo.html
Here's a simpler way to find the path: nest loop all the cities, like for each city, loop all of the cities that are not connected to it, find shortest distance, connect. Perform for next city
Hey! Thank you for making such amazing videos with so much explanation. I love every one of them.
At 14:30, I think it wasn't just the last one. The distance will be same for 0,1,2,3 and 3,2,1,0 so if you had encountered 0,1,2,3 before and 3,2,1,0 at the end, it would seem as if it was the last one that was the best but actually there were two best.
Hey Daniel, these are some great videos. I can't wait to see how the genetic algorithm solves this problem.
You could optimize the code to be twice as fast by ignoring symmetric permutations of the array. IE 0,1,2 is the same as 2,1,0 so dont bother checking 2,1,0
I'm curious, don't you kinda check everyone twice? Like, [0, 1, 2, 3] = [3, 2, 1, 0]. So one could half the computing time by excluding that, right?
In this case, yes, because we have a non oriented graph. In the general case of a digraph, going from city 1 to city 2 doesn't need to have the same "cost" as going from 2 to 1
Checking whether something needs to be excluded would probably be pretty complicated, so I don’t think you’d save much if any time overall.
@@KnakuanaRka Nah. Just cut it from middle as it is arranged in an alphabetical order.
@@abhishekjmathew5732 D'oh! *facepalm*
17:20 OOOOPS!!!
Copper nitro telluride
C U Next Tuesday!
Hello Everyone, i was doing this in processing and i wrote , if(dis
I would love to see the genetic algorithm implementation of this. Going through every single possibility seems hugely inefficient.
Yes, I plan to get to this soon!
I would like to know more about this Gene Ethic algorithm too
+1 to this request! I’ve been working on differential growth algorithms (inspired by inconvergent.net/shepherding-random-growth/) and keep thinking to myself "If only Shiffman had a k-d tree video."
(p.s. thank you for all these videos-it’s a huge inspiration!)
it's coming out soon
I know I'm about 4 years too late but Sebastian Lague has a really good video on that concept!
you deserve more views, man
very cool vids, I can't stop watching even though I learn java, not js
greetings from Ukraine
Hello!
Love the videos, you explain everything so well!! Just adding to the voices asking for the #4 :D
I think I'm going to do it tomorrow!
About the lexicographic order TSP algorithm that you showed.
If you only check total_permutations / 2 times, you can get the solution in half the time. Because what matters here is that we get the minimum distance route.
Example: for 3 cities, the distance for order [0, 1, 2] would be same as [2, 1, 0]. So why check both?
If you have any further query regarding my premise, draw these two routes and check for yourself.
Loved this video series.
Are we gonna get the Genetic Algorithm (part 4)??
Hope you will release or make this soon.
Eventually yes! Will try to get to it soon.
Hi, Dan, this is a really incredible series! I've already used hello.processing to introduce students and colleagues to the platform, and these are a really fun, accessible extension to show them once their interest is piqued.
A question: Would it be a huge pain in the kiester to dump these coding challenge videos into your Vimeo account, too? I'm a public high school art teacher (as are a lot of my colleagues who I evangelize to about including creative code in their curricula), and public schools have a nasty habit of blanket-blocking TH-cam, while other streaming services like Vimeo tend to be permitted.
If that would be a huge timesink for you, I totally get it, though (and I can just keep ripping MP4s to show in my classroom...).
I can share a google drive folder with you which might be easier. I want to do this, but don't really have the time to maintain both platforms and also worry about splitting the audience. I need to think about this more, can you contact me via e-mail or twitter?
Hello! Thanks lot for all the amazing videos! But I can't find the video with the implementation of a genetic lgorithm in this example. Is it somewhere?
Hi Dan, you are amazing Teacher and keep up the good work
for(int i=0 ; i < totalCity ; i++){
g.drawOval(city[i].x , city[i].y , city[i].width , city[i].height);
n = order[i];
if(n < totalCity-1){
g.drawLine(city[n].x , city[n].y , city[n+1].x , city[n+1].y);
}
}
this is java code..
here "order array" is changing correctly but path between cities are NOT updating..it was working before Lexicographic Order..
i am not changing "city array" anywere.
plz help
Would it be more efficient if you search for the most separated point of the group as a starting point, and from there you search the closest point ?
you could probably use some of the code from the poisson disc sampling video to make this quicker.
Have you ever wanted to try another approach to this problem? I know you made the GA solution, but there is a set of really good solvers, such as ALNS, that are known to solve this problem in polynomial time. I would love to see you implementing LKH or something like that in your challenges. Sorry to bother here, i don't know if you got a official local to talk about this.
It's really an amazing explanation, but I am wondering why the result was not 100% after the loop stopped.
How does Google Maps do it so quickly then (i.e. calculate the best or shortest route between several points on a map)?
There are much better algorithms. The one presented in this video is all about brute force (testing all possibilities). It is slow because for N entries, we have to check N! (N factorial) possibilities. Look up for Dijkstra's shortest path algorithm. With this one, we have to check N^2 (N squared) possibilities, much better...
For 10 cities, for example: Brute Force = 3.628.800 checsk, Dijkstra = 100 checks. The difference grows with the growth of N.
Today there is a better implementation of Dijkstra that runs in (N*logN or M, M beeing the number of edges)...
@@gmbueno Dijkstra can't solve this problem, it only gives you the best path between 2 cities. The TSP requires the optimal route to travel all the cities. For bigger cases , ie: google maps, it's used heuristics that can approximate the result from the optimal solution. Currently it's possible to calculate the best route of milions of cities with < 3% difference from the optimal solution in a reasonable time.
I didn't like the video before it auto played so I had to come back.
great series. keep it (Y)
You're a mad man
factorial 0 is also 1 btw :P with your current code if it somehow reached 0 it would loop forever.
Dude I almost just started crying this is so cool
I believe part of the travelling salesman is the salesman has to return to his home city and so completes a loop. Any ideas on including this in the next one as well?
Ah, this would be good to try!
Does somebody has its back to start version?
It would probably run faster if it was calculated in a function outside the draw loop, and only displayed how far it got, every 0.02 seconds (50 frames).😀
hey @ 9:55 how do i solve this when the number of cities is arbitrary?
try to determine what is the deviance from the assumed optimal compared to a quickly chosen average round trip
benefit of the optimization
a spiral path should be quite short compared to the average random
non-overlapping path
floating point
Wouldn't this program be quicker if you do this?
1. Start at chosen city.
2. Look the distance between this city and all others.
3. Chosse city with shortest distance and draw path.
4. Exclude star city from looking pool.
5. Set city from point 3 as start city, go to point 2.
Imagine if the cities were spread out like the letter L, and the starting point was in the middle of the horizontal line, but the distance to the right was a bit larger than the distance to the left city. It would then start going left, continue upwards (vertical line), and then jump from the top of the L to the bottom (right next to the starting point), and then take the last few. The jump will be like the hypotenuse in a triangle, and therefore make this alt potentially longer then first going right, then jump back to start, and then take the rest. But if processing power costs more then the potentially longer distance, then I would go with your solution!
"For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution, but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps." --wikipedia (Greedy_algorithm)
You could check half of them if you take into account that ABC and CBA are the same thing for this program :p
What are the specs on your computer?
Hear about the blonde travelling salesman who couldn't figure out the TSP between 2 cities?
Ba-dum-tss...
kevnar Is the “ba dum tss” the punchline? Because I don’t understand it at all.
@@KnakuanaRka lol no people say that at the end of the joke. Finding the TSP between 2 cities is just a straight line which is very easy so its a blonde joke
Christopher Barber D’oh!
Any chances for a minesweeper? :)
Great idea, suggest here: github.com/CodingRainbow/Rainbow-Topics/issues
I made Minesweeper, you can check it out and try to see how it works at pitt.edu/~ksa18/minesweeper/
love these series, what could be interesting, if you'd might run out of idea's for these series or something; is lumance based effects on pixel inputs, like video. delaunay triangulation for example or Voronoi tessellation like this: th-cam.com/video/mTzbax2daKs/w-d-xo.html
Here's a simpler way to find the path: nest loop all the cities, like for each city, loop all of the cities that are not connected to it, find shortest distance, connect. Perform for next city
That "greedy algorithm" won't necessarily find the shortest path, though it's likely to produce a better solution than a random path.
Wait, couldn't he just use Djikstra's algorithm for this?
No because we have to pass through all the cities and no just find the shortest path.
where is the TSP problem done with a Genetic Algorithm?
17:20 cheeky dig
this is really inefficient. you are checking every permutation twice because 0123 is the same as 3210 and 2310 is the same as 0132 etc.
No they are not, the distance between each city in each case is different
they are literally the reverse path, but honestly setting up a check for reverses would not be worth it
@@ThePizzabrothersGaming The reversed paths are just the last half of the paths checked. Totally worth just stopping half way.