Derick Hess Me too! Actually it is relaxing but at the same time it makes you feel the need to code! I would call this new way of relaxing: "prograxing"
I took the formula for line intersection from your Ray Casting video and I just made the TSP algorithm swap the tails of two random intersecting lines in the path. Then I gave it 999 points, and it unscrambled the path in a matter of ten minutes or so. It's not the shortest path, but the amount of progress for that many points is amazing.
Seriously Dan, I luv, luv, luuuv the way you teach. I am a software developer in training and you make it so much more palatable to digest. I truly hope you continue this great work you're doing man. You're my go to resource when I need ANYTHING for coding.
I love that you chose to use 'salesperson' as opposed to traditional 'salesman' term - obviously not all sales persons are 'men'. Thank you for thinking at that level! Makes a huge difference for mental processing!
Sally has 12 boyfriends. In order to keep them from finding out about each other, she insists on having her visits at the guy's houses. What route does she visit them in that saves her the most travel time so she can maximize the time she spends with each guy?
I really love these videos, they are super informative. I'm a Sophomore in college earning my degree in Computer Science. Even though I haven't learned Java or JavaScript, I really appreciate these videos.
I think one way of avoiding the trap that you see at 21:18 is to sometimes swap more than 2 points. Though that actually isn't a two point trap now that I look at it.
does the salesman have to end up at home after hitting each point once or does he travel from job to job forever? #2 if you had a short repeatable solution. how would a person responsibly disseminate their findings?
Perfect! I am studying it for a project in my R coding class. Your logic explanation was clear, didatic and easy to understand. I enjoyed it :) Keep making videos like that!
traveling salesman problem is one of the hardest problem in math having no exact method/equation for finding the EXACT shortest route and its is one of the NP problems.... if you can find a quick way to solve this problem for any number of points, it will proof that P = NP and that will get you million dollars as it is one of the 1million$ millennium problem
5:29 I am here because I'm trying to make a program that can come up with the optimal arrangement for a bunch of chunks of music to form a song, such that the arrangement follows some given rules (e.g., what chunks are allowed to follow what other chunks, minimal repetition of chunks)
The dynamic network graph is amazing. I wonder how to create those dynamic animation. Is it a special drawing software or particular packages of some languages?
I know this is 4 years ago, but just in case you didn't find it, this is p5js! It's a free JavaScript library that makes it easy to create these drawings, and it also has an in-browser editor you can use to get started. It's a fantastic tool and this channel has lots of tutorials for it.
Still, since when talking about time and space complexities we are referring to very large N counts, the problem's upper bound is still called n! or factorial, since any constant (in your comment's case = (1/2) * n! ) multiplying the n is "irrelevant"
What this video needs is.... more talking with the arms and hands. ;-) interesting stuff! though a lot flies over my head. You're an enthusiastic teacher.. fun watch.
Is this a case where a genetic algorithm could do a "good enough" job in a much shorter time for large lists of coordinates? I.e.you could feed it an acceptable total distance, or time to travel, and it could quickly evolve a decent route.
I don't know about that. I just finished doing a branch&bound implementation of the traveling salesman problem and I can't see why you'd go the genetic algorithm path on this one (for anyone interested, look up my github and I've done 3 different branch and bound implementations for different heuristics: github.com/drkztan/javasalesman). I've also used dijkstra's algorithm to create some tables to fetch distance data in linear time instead of calculating it at every solution node. Neural network or a very well thought out heuristic+preparation work for a branch and bound type algorithm seems much, much better.
think something someone can try, is instead of making each gene to be just one city, and mutation changes that city, they can try to make a gene to start with every city, and randomly let every agent select randomly between the possibilities in the gene, and make mutation randomly delete a city in that gene. in a way, this will be the reverse way most genetic algorithm work the idea is that wrong a wrong city in gene x, will make that gene less fit, then a gene without that city. hope that make some sense, english is not my language
Probably not, unless your approximation is really coarse. A property of NP-hard problems is that they cannot be approximated very well. This is because a good approximation yields a precise solution (follows from the PCP theorem, if you want to look it up)
maybe, one thing i am pretty sure of, is that my code will be very slow :-) partly because of it can't use crossover, and has to have a mutation rate that are extremely low.
I work with TSP problems with capacity, multiple time windows, service times and profit. The problem escalates so much faster but with some smart meta heuristics, you can get a nice solution really quick. If someone wants the state-of-the-art method message me... My current best is 100 nodes optimality for simpler problems with 1 vehicle .... Generally improving and check of a route of 20-30 points with time, capacity and profit take less than a millisecond.... so you can try 1000's improvements each second.
I'm in the middle of the video, so I'm not sure if you clarified the actual definition of "shallow copy". A shallow copy is a copy of a variable or array of variables that point to the same address in memory, thus, if you change a value of the original, you change the value of the copy. conversely, a deep copy will actually copy the original to a new address in memory, and allows you to change one of the variables without changing the other.
You spoke about providing the Processing code to this example as well. Unfortunately, I didn't find is on github (github.com/CodingRainbow/Rainbow-Code/tree/master/challenges/CC_35_TSP/CC_35.1_TSP). Would you be so nice to provide the Processing code for TSP? Awesome!
Prim's is slightly different. Prim's will give you the Minimum Spanning Tree, which will be the shortest path that connects all cities to at least one other city, however, it may not be the shortest when traversing all cities as you may have to double back on yourself. Think of Prim's as a way of connecting all cities so all cities can be traversed using the least amount of road, however traversing that road may not be the shortest route as going directly.
Where are u programming this? Are you using an text editor or something else? I would appreciate so much if u can answer me. Excelent video, greetings from Mexico :)
Try some of these workflow videos! (let me know if they are helpful) sublime text: ruclips.net/video/UCHzlUiDD10/видео.html atom editor: ruclips.net/video/d3OcFexe9Ik/видео.html brackets: ruclips.net/video/nmZbhManVcY/видео.html codepen: ruclips.net/video/5gfUgNpS6kY/видео.html
could you please make a video to code a system that use GA for navigating the customer of supermarket when they are doing their grocery shopping task. The system should use the shelf's coordinate and the result will display a list of shelf label of the selected shelf from the distance calculated from the supermarket front door. tq
I can´t get the first part to work. I´m new to this. When I write cities.length it appears all red. I have the code exactly as in the video but it does not work :/ var cities = []; var totalCities = 5; function setup() { createCanvas(400, 300); for (var i = 0; i < totalCities; i++) { var v = createVector(random(width), random(height)); cities[i] = v; } function draw() { background(0); fill(255); for (var i = 0; i < cities.length; i++) { ellipse(cities[i].x, cities[i].y, 8, 8); } }
"in the future, *some many years from now*, people will be complaining about how pokemon go is irrelevant." LOL, pokemon go has become irrelevant literally after a few weeks
why does he do some challenges in p5 and others in processing? Is it just because one is better for certain things than the other, if so what's better for what?
Hey! shameless plug here, but I actually have a traveling salesman problem solution with dijkstra implementation, some backtracking and a couple of branch and bound solutions here: github.com/drkztan/javasalesman :)
Wouldn't using a algorithm be better than using a randomizer or trying every possibilty. Like maybe the Greedy Algorithm or the Bellman-Ford Algorithm.
You explain very well But i have a question on another day i was watching your A* search algorithm video whats the difference between this concept and that A* search ? Secondly can i make code of this in c++? Please do reply
A* is for calculating the shortest distance between a node pair... but for tsp, it is tour that starts and end at the same node. That makes the problem hard and can't be solved by exact methods.
6 лет назад
Hello! I'm working with TSP and genetic algorithms and now I'm trying to integrate local search into my algorithm. Can you provide me with a reference where I can find information about this problem? I already have some significant results from my genetic algorithm but to those results I want to apply local search to try to improve my results. Thanks for your attention!
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
As a software engineer I enjoy watching these videos. I find them relaxing. You are really good at teaching. Keep up the good work!
That's so nice to hear thank you!
Derick Hess Me too! Actually it is relaxing but at the same time it makes you feel the need to code!
I would call this new way of relaxing: "prograxing"
Derick Hess Same here. Makes me feel better to not be alone in that feeling. :-)
@@TheCodingTrain Does Derick look like the guy who wrote this paper : ruclips.net/video/goUlyp4rwiU/видео.html @DerickHess
@@TheCodingTrain choo choo , abey bada ho ja bhai. choo choo
I took the formula for line intersection from your Ray Casting video and I just made the TSP algorithm swap the tails of two random intersecting lines in the path. Then I gave it 999 points, and it unscrambled the path in a matter of ten minutes or so. It's not the shortest path, but the amount of progress for that many points is amazing.
I come from the future to let you know that this is still interesting.
Jared Fairchild and Pokémon go is relevant again
Welp it’s 2020
Not anymore buddy
TSP needs to get back to its initial position and in this case, it is not
, am i right?
Further in the future here, can confirm its still interesting
Seriously Dan, I luv, luv, luuuv the way you teach. I am a software developer in training and you make it so much more palatable to digest. I truly hope you continue this great work you're doing man. You're my go to resource when I need ANYTHING for coding.
1:10: "Oh a Pokémon Go analogy, this will be easy to follow!"
1:15: "N-dimensional? I'm lost"
I love that you chose to use 'salesperson' as opposed to traditional 'salesman' term - obviously not all sales persons are 'men'. Thank you for thinking at that level! Makes a huge difference for mental processing!
i know this is late, but i think the travelling salesman problem requires you to go back to your starting location after visiting every city.
yeah otherwise its just a minimum spanning tree problem
isn't that a hamilton cycle?
TSP is shortest hamiltonian cycle yes
Sally has 12 boyfriends. In order to keep them from finding out about each other, she insists on having her visits at the guy's houses. What route does she visit them in that saves her the most travel time so she can maximize the time she spends with each guy?
Damn, Sally is even worse than Chuck, who's always trying to spy on Alice and Bob.
@@MrCmon113 eve?
@@MrCmon113 we used to have Darth spying on alice and bob when the love birds wanted to talked :p
Thanks u inspired me a lot
_why? Just why?_
I created a presentation in university based on this video, thanks a lot :)
I used a traveling salesman in a CNC application, when milling a bunch of pockets, to choose the order of the pockets.
7:13 The bell was a hilariously unexpected touch.
I yelled "SUM!!!" at the screen for like 4 min lol
Came here for my uni course. Stayed for the flamboyancy
I really love these videos, they are super informative. I'm a Sophomore in college earning my degree in Computer Science. Even though I haven't learned Java or JavaScript, I really appreciate these videos.
how to take input from user for the dist bw points ??and then do this??
Your enthusiasm is priceless :) nice video
Thank you!
"What are the things in your world that you need to find the path way through?" everything in my room I guess
If you don't have the restriction of returning to the starting city, then you have leftover combinations. A B C would be the same as C B A, and so on.
Man, that's awesome! So simple, yet so neat.
i come from 2020 and your video is still awsome
These videos are both priceless information and entertainment
I think one way of avoiding the trap that you see at 21:18 is to sometimes swap more than 2 points. Though that actually isn't a two point trap now that I look at it.
patient, adequately funny, and informative, please continue this as long as you can --tokyo
You can actually reach an upper bound of n^2*2^n which is a better bound than n factorial.
you're a great teacher and thanks for being so enthusiastic about programming, it really keeps me going!
2020 it is! Travelling back in time to understand Travelling Sales Person problem...
I plan to use this to find the optimal route while shopping for various items at Walmart!
Haha, look forward to hearing how that goes!
does the salesman have to end up at home after hitting each point once or does he travel from job to job forever? #2 if you had a short repeatable solution. how would a person responsibly disseminate their findings?
Perfect! I am studying it for a project in my R coding class. Your logic explanation was clear, didatic and easy to understand. I enjoyed it :) Keep making videos like that!
Hey Dan!
Just wanted to say
its 2022
about 6 years later
Pokemon Go is still relevant enough for this video hahaha
For the latest thing, the points would be shops where the Nintendo switch is possibly present...
instead of writing 'bestEver = cities.slice();', you can just write 'bestEver = cities;'. It copies the array exactly
He did it that way first and then "corrected" it. XD
Noob here, what does the index.html file look like. I have it, but when i try to open it in my browser all i get is a black box. PLZ HELP!
first channel ive ever subscribed to!! Really worth it :) Thanks! Apreciate it!!
I finally downloaded processing! Very cool and easy to install plus allows me to follow along and use all github projects. Thanks!
traveling salesman problem is one of the hardest problem in math having no exact method/equation for finding the EXACT shortest route and its is one of the NP problems.... if you can find a quick way to solve this problem for any number of points, it will proof that P = NP and that will get you million dollars as it is one of the 1million$ millennium problem
5:29 I am here because I'm trying to make a program that can come up with the optimal arrangement for a bunch of chunks of music to form a song, such that the arrangement follows some given rules (e.g., what chunks are allowed to follow what other chunks, minimal repetition of chunks)
Love these videos! Been binge watching while I'm off work the past couple of days :p Keep it up man, you're inspiring
I want to use this algorithm but where can I find the listing that explains the Java functions in basic command set
don't you need to return to the starting point?
No. The salesman left his wife and family and never plans to go back.
That’s called something else.
@@Caleb-zj9xi no its not
Fascinating video - always enjoy your channel - your enthusiasm is infectious :)
how do u make that animation part??what do u use??
The dynamic network graph is amazing. I wonder how to create those dynamic animation. Is it a special drawing software or particular packages of some languages?
I know this is 4 years ago, but just in case you didn't find it, this is p5js! It's a free JavaScript library that makes it easy to create these drawings, and it also has an in-browser editor you can use to get started. It's a fantastic tool and this channel has lots of tutorials for it.
Hey I’m from the future and this is actually really useful for solving shwolobatata-hmm problems
22:21 The bell makes a sound, or you might understand it better as follows:
class Bell{
static void makeSound(){
System.out.println("Ding");
}
}
Interesante gracias... aplicare ahora la heuristica anneling para calcular mas rápido la ruta mas corta
How to stop this prog after iterations are completed..?
Help! At 10:05 , I don't see index (element?) [3]... I only see [0] to [2] . Did I miss something?
For the different path calculations the formula is actually n!/2 as ABC is the same path as CBA
Still, since when talking about time and space complexities we are referring to very large N counts, the problem's upper bound is still called n! or factorial, since any constant (in your comment's case = (1/2) * n! ) multiplying the n is "irrelevant"
I am a simple man. I see your videos in my recommendations. I watch. LMBO @16:11 "shmoley-patat-in"?
your videos are amazing, thank you Daniel
as you said we want the total sum of all distances,then why haven't you returned the sum from calcDistance function?
Is there a video for this solution using DP, not brute force ?
The time complexity can be reduces from n! to (n-1)! since we can fix a point and permute the remaining (n-1) points.
And assuming the distance from A to B equals the distance from B to A, you can divide (n-1)! by 2.
So it turns out Windows 10's calculator can handle some pretty big numbers, 3000! is ~4.19^9130. Not bad.
My Android calculators max is 13547! = 1.085^50089
4,1493596034378540855568670930866 with 9130 zeros
@@lumschente the biggest on windows 10 is 3248
About 3:00, shouldn't it be n!/2? ABC and CBA is the same path but reversed? I like your videos, keep up the good work!
And so are ACB, BAC, BCA, and CAB. WIth three cities all paths are the same! You must return to the starting city.)
I like your approach of programming!!! , understood more clearly than what teachers teach in my college thanks 😃
What this video needs is.... more talking with the arms and hands.
;-)
interesting stuff! though a lot flies over my head. You're an enthusiastic teacher.. fun watch.
Pokemon Go was actually the real reason I got interested in this problem... ^^'
Is this a case where a genetic algorithm could do a "good enough" job in a much shorter time for large lists of coordinates? I.e.you could feed it an acceptable total distance, or time to travel, and it could quickly evolve a decent route.
yes :)
I don't know about that. I just finished doing a branch&bound implementation of the traveling salesman problem and I can't see why you'd go the genetic algorithm path on this one (for anyone interested, look up my github and I've done 3 different branch and bound implementations for different heuristics: github.com/drkztan/javasalesman). I've also used dijkstra's algorithm to create some tables to fetch distance data in linear time instead of calculating it at every solution node. Neural network or a very well thought out heuristic+preparation work for a branch and bound type algorithm seems much, much better.
think something someone can try, is instead of making each gene to be just one city, and mutation changes that city, they can try to make a gene to start with every city, and randomly let every agent select randomly between the possibilities in the gene, and make mutation randomly delete a city in that gene.
in a way, this will be the reverse way most genetic algorithm work
the idea is that wrong a wrong city in gene x, will make that gene less fit, then a gene without that city.
hope that make some sense, english is not my language
Probably not, unless your approximation is really coarse. A property of NP-hard problems is that they cannot be approximated very well. This is because a good approximation yields a precise solution (follows from the PCP theorem, if you want to look it up)
maybe, one thing i am pretty sure of, is that my code will be very slow :-)
partly because of it can't use crossover, and has to have a mutation rate that are extremely low.
Why did you do linear paths instead of round trips? All of the examples I've seen of the TSP use round trips
can you please make a video about VRP algorithm?
Sorry, I'm new here. Is it possible to open his completed java travelling salesperson project to try something out?
Isn't it a good idea to cache parts of the system? So when it hits again, it is just to look it up instead of calculating everything all the time?
I work with TSP problems with capacity, multiple time windows, service times and profit. The problem escalates so much faster but with some smart meta heuristics, you can get a nice solution really quick. If someone wants the state-of-the-art method message me...
My current best is 100 nodes optimality for simpler problems with 1 vehicle .... Generally improving and check of a route of 20-30 points with time, capacity and profit take less than a millisecond.... so you can try 1000's improvements each second.
Great Video. Wanna see more
I'm in the middle of the video, so I'm not sure if you clarified the actual definition of "shallow copy".
A shallow copy is a copy of a variable or array of variables that point to the same address in memory, thus, if you change a value of the original, you change the value of the copy.
conversely, a deep copy will actually copy the original to a new address in memory, and allows you to change one of the variables without changing the other.
Thanks for this info!
The Coding Train this channel is pretty cool! Keep up the good work!
well you can narrow down possible paths by just working out which are "edge" vertices and starting from them.
You spoke about providing the Processing code to this example as well. Unfortunately, I didn't find is on github (github.com/CodingRainbow/Rainbow-Code/tree/master/challenges/CC_35_TSP/CC_35.1_TSP). Would you be so nice to provide the Processing code for TSP? Awesome!
Would Prim's algorithm work better? I searched up and this is an O(V^2), and Prim's is O(|E| log |V|). (V = vertex, E = edge/path b/w points)
Prim's is slightly different. Prim's will give you the Minimum Spanning Tree, which will be the shortest path that connects all cities to at least one other city, however, it may not be the shortest when traversing all cities as you may have to double back on yourself. Think of Prim's as a way of connecting all cities so all cities can be traversed using the least amount of road, however traversing that road may not be the shortest route as going directly.
You're right. Prim's could lead to having to travel the same path again because it doesn't guarantee a linear path.
One thing i dont get is why the upper boundary in the loops use to be < and not
Why not computing greedy algorithm (visiting the closest city...) giving you the upper bound ?
because we want the optimal answer.
What library would be good to use in Python to take care of drawing the lines and visually representing this algorithm?
Check out pyGame. It's a Python library aimed at game developers, so it has a lot of drawing/graphics functions.
How would you going about adding obstacles?
I think you forgot to put console.log(recordDistance); between line 69 and line 70 in #35.3 in the web editor on the website.
Where are u programming this? Are you using an text editor or something else? I would appreciate so much if u can answer me. Excelent video, greetings from Mexico :)
Try some of these workflow videos! (let me know if they are helpful)
sublime text: ruclips.net/video/UCHzlUiDD10/видео.html
atom editor: ruclips.net/video/d3OcFexe9Ik/видео.html
brackets: ruclips.net/video/nmZbhManVcY/видео.html
codepen: ruclips.net/video/5gfUgNpS6kY/видео.html
You should use something like this to solve the Maze Generator you made ; )
Great video! But tsp requires to return to initial citie
could you please make a video to code a system that use GA for navigating the customer of supermarket when they are doing their grocery shopping task. The system should use the shelf's coordinate and the result will display a list of shelf label of the selected shelf from the distance calculated from the supermarket front door. tq
Please do more in Processing!
I can´t get the first part to work. I´m new to this. When I write cities.length it appears all red. I have the code exactly as in the video but it does not work :/
var cities = [];
var totalCities = 5;
function setup() {
createCanvas(400, 300);
for (var i = 0; i < totalCities; i++) {
var v = createVector(random(width), random(height));
cities[i] = v;
}
function draw() {
background(0);
fill(255);
for (var i = 0; i < cities.length; i++) {
ellipse(cities[i].x, cities[i].y, 8, 8);
}
}
How you making the animations any source to learn this
"in the future, *some many years from now*, people will be complaining about how pokemon go is irrelevant."
LOL, pokemon go has become irrelevant literally after a few weeks
Not anymore! It used a Max Revive and brought generation 2 out! :D
and... stil irrelevant
and... now i actually had forgotten it ever existed.
I think it took a few months, but yeah, it blew over pretty fast.
It's gone
It should be renamed to "Catching-Pokemon-Problem"😂👌
why does he do some challenges in p5 and others in processing? Is it just because one is better for certain things than the other, if so what's better for what?
Favorite part: 22:52. "Shruntinpatatadahmmm.... *DING"
16:51*
Simple and easy as always.
Keep go on.
I wish I was one of your students in your class. );
Are u gonna use Dijikstras algorithm?
Oh damn, getting heavy with the graph theory on Coding Rainbow haha! I'd love to see him tackle advanced topics like that.
+Kyle Amoroso never really watched before but really cool, he's a great teacher!
Yeah I love his videos, no one can present an idea and illustrate how to code it up like he can!
Hey! shameless plug here, but I actually have a traveling salesman problem solution with dijkstra implementation, some backtracking and a couple of branch and bound solutions here: github.com/drkztan/javasalesman
:)
Wouldn't using a algorithm be better than using a randomizer or trying every possibilty. Like maybe the Greedy Algorithm or the Bellman-Ford Algorithm.
How long to resolve 100 points? I have one that resolves in 20mins for 100!
Do you have graph partition
i cant find the code in the description :(
Could you please show what's in your index.html so far?
Wow, I hope I knew about your channel earlier!
Energetic.... and lots of love for you
You explain very well
But i have a question on another day i was watching your A* search algorithm video
whats the difference between this concept and that A* search ?
Secondly can i make code of this in c++?
Please do reply
A* is for calculating the shortest distance between a node pair... but for tsp, it is tour that starts and end at the same node. That makes the problem hard and can't be solved by exact methods.
Hello! I'm working with TSP and genetic algorithms and now I'm trying to integrate local search into my algorithm. Can you provide me with a reference where I can find information about this problem?
I already have some significant results from my genetic algorithm but to those results I want to apply local search to try to improve my results.
Thanks for your attention!
is that have a relation with the chinese postman problem ?
Scwalla Vatatan! The next new thing!
I'm going to create it, just to prove Shiffman right!
15:50 the newest thing still is pokemon