Coding Challenge #35.1: Traveling Salesperson

hello welcome to another coding challenge in this coding challenge I'm going to explore the traveling salesperson algorithm it's a classical algorithm that you'll find from kind of this thing known as computer science I want to talk about what the algorithm is I want to build a quick JavaScript example to demonstrate how to kind of program the problem and then I'm going to do a several follow-up videos to look at different solutions to that's particular problem and for you the viewer I want you to think about what are some creative applications could you make some kind of interesting line drawing visual art with it could you create a musical system could you use it for some sort of data visualization scientific simulation creative project in your field of interest so I hope that you'll watch these videos get the example code play with it and make an application with it and share that application with me which I might share then with other people but whatever that's not the point the point is let's talk about this algorithm so this is currently a processing sketch I'm going to program this in JavaScript which is true checking every single possible solution to what so let me walk the traveling salesperson so you know I think that a Pokemon go within the future some many years from now and somebody's watch this video poke event goes the most irrelevant thing it'll be so annoying to watch this but the problem is let's say you have a space and this could be a two-dimensional or three-dimensional or an n-dimensional space but we're gonna work or the two-dimensional space and the problem is usually framed as they're a bunch of cities so here are several city a map of a bunch of cities or perhaps they're a map of a bunch of pokemons that you want to catch but you're a salesperson and you want to go sell your you know coding rainbow stickers or t-shirts or whatever in every city so you know I could go here and then I could go here and then I could go over here and then it could take the Train here and I could fly here and I could go here and I could go here you can see that would be a path that hits every single city but it wouldn't be the shortest path and I could try to eyeball it and this might be an interesting application by the way idea what if you build a computer algorithmic system solving the optimal fastest solution and you have it compete with a person trying to draw that solution that could be an interesting interactive exhibit but you know we could try to say like oh well maybe the optimal solution is something like this but you know that's just kind of a guess so we don't have to guess I could go back over here and this is a program that checked every single possible solution for and this is 12 points so you might think big deal how many possible ways are there to explore how many possible ways are there to connect 12 points well there's actually quite a few and it and let's kind of explore that for a second so let's say there are only three points and the points are a B and C well let's look at all the possible ways a b c a c b b a c b:c a I'm doing this in a specific order for a reason which will become relevant in a future video c a b c b a and if I did this correctly these are actually sorted in alphabetical order which is a kind of piece of this that's going to come up as I explore this further so you can see did I do this right there are three possibilities and there there are three cities or three Pokemon there are one two three four five six six possibilities so the way you can actually calculate how many possibilities is 3 times 2 times 1 which is also known as 3 factorial and why is that because there are there are 3 possibilities for the first let for the first letter and with each one of those there are 2 possibilities for the second and for each one of those there's one possibility for the third so actually if you were to if there are 12 points there are 12 factorial possible ways of connecting all of those dots which if you pull up your calculator is a really really big number and when you would go to 13 it's a really big number so actually like if I change this program right now to try to use like 20 points watch how slowly it's going to complete all the possibilities we are going to be here till the dawn till the time the Sun envelops the earth we we won't be alive then I guess but you know you get the point this is going to take a really long time and if I even just go let's just go from 12 to 13 just this point a little bit more explicit you can see now come on computer you can see that it's still checking all the possibilities but even just to get to one percent of the possibilities is taking quite a while and this is a program that's written in Java that's running relatively fast okay so um people in the chat are posting the answers to these factorial questions I'm glad because I don't have them I don't have those numbers in my head so now let's let's start to program how do we think about this program in a visual simulation of this idea in a visual simulation so I'm going to move out of processing you'll be able to get this Java based processing code also in this video's description but I'm going to quit processing here I'm gonna don't save that and I'm gonna work in the browser which admittedly JavaScript html5 kit this is not the place where you're going to find your greatest power and speed from your computer but it's a place that we can kind of explore this idea and so what I have here is a simple JavaScript program it makes a canvas and it has a draw loop so what I'm going to do is I'm going to create an array and I'm going to call that array cities but this could be anything please think more creatively what are the what are the things in your world that you need to find a pathway through and then what I'm going to do is I'm going to say let's just have three just to be simple about this I'm going to have three cities I'm gonna say cities index cities index I equals create vector and I'm going to create a random vector and I'm going to do this as a separate line of code random with random height so a vector is just an object in p5.js I mean it's you know the concept extends beyond p5.js but that stores an x and y position it does more than that but that's what we're using it for and so I want to create a bunch of those and then I just want to see those points in the window so I'm going to do that same exact loop but I'm going to say here cities dot length and I'm going to actually make that a variable like total cities so it's something we can vary equals three and then instead and then what I want to do is say I want to draw a circle at cities index a dot X city's index i dot y we'll make it circle 4x4 pixels will say fill 255 so it's white and I just want a little bit more room to write my code and then I'm gonna hit refresh here whoops it refresh here and you can see there are three cities picked randomly refresh the page I get three random cities so and you can see here you know if I just now go and say total cities 20 now I have 20 but I want to work with a small number so I can sort of visually see that things are working okay am i recording this yes excellent all right so um let's go back to three cities let's make these a little bit bigger so you can see them and let's also whoops let's make this a little bit bigger and it can make the Consul a little bit smaller okay so now what I want to do is start exploring possible orders well I have an order already actually the order that I have is in this cities array so I could sort of say this is an order and what I might actually do beyond just draw those cities is draw a path between them so I'm going to say a begin shape and shape and instead of drawing a circle at each point I'm going to say vertex cities X Y and I'm going to say a stroke 255 I'm just a stroke weight - just to give it a little bit of thickness so it's a little easier to see I'm also going to say no fill and so now I'm going to run this and we can see there we go now I just realize I know what I want to do is shuffle the array so what I want to do is I want to try these are now I'm getting I'm getting random every time i refresh but what I want to do in draw in that draw loop is I want to shuffle that array to try different random orders so how do I do that so I have a feeling if I go and look up the Mozilla documentation for the array object in JavaScript there might be a kind of function as part of the array prototype well what's a prototype did I just say prototype in a video but in other words when I say prototype prototype being this sort of like thing that is in charge of every array it's ever made ever in JavaScript and there are some functions that I've explored in other videos like remove or splice or push that allow you to manipulate that array I'm wondering if there's one that's called shuffle whether or not there is I'm going to write my own function so I'm going to write a function and I'm actually going to call it swap not shuffle and you'll see what it's going to do in a second it needs an array and it needs to into index things so something that's going to be very useful in just about every scenario that I explore the traveling salesperson is this idea of a swamp and this comes up all the time in different things you might want to program and do so in other words a swap is if I have an array that says ABC what if I want to pick two random elements like oh this one and this one and I want to swap their position so now the array is CB and I might use this if I do this with a genetic algorithm as later as a mutation so the mutation of a path through all the cities is swapping to ranch cities randomly so let's look at how I might do that and I am going to say well so what you would think you might do is say a index I equals a index J and a index J equals a index I right this is the idea of a swaps a index I this is the idea of taking an array and swapping two elements right put the element number three at element zero and put element number zero at element three the problem is if I set a index J equal to a index I I just reset I and excitable J so I'm actually setting a index J to itself so in order to perform a swap I need to say this actually I need to have some temporary variable which is holds a index I so I keep track of what a index I is and then later once I replace a index I with J and then J could be equal to temp so this is just a really simple really simple algorithm for taking two elements of the array and swapping them and let's look at what happens now if what I do every time through draw at the end is I say swap cities and then oh I need two random index indices so I'm going to say I equals floor random city's length and J is also a random value so I'm gonna swap I and J and of course I you know I'm not guaranteeing that I don't pick the same one and swap an M with itself but big deal it's going to do this a bunch of times let's run this program again and you can see you know with three things there's not a lot of order possibilities but if I make this total Cities ten you can see now you can see how elements are being swapped and so it's doing this very fast but I'm exploring a whole lot of possibilities okay so now what can I do what I want to do just just kind of explore this in a brute-force way is as I'm trying all these different possibilities I want to calculate what is the distance traveled through this particular order and if that distance is the best one I've gotten so far let's save it so let's do that as the following so one thing I need to do I think it might be useful to write a function that calculates the distance between every point in an array so I'm going to write another function down here at the bottom and I'm going to call this function calc distance and it's going to get a list of points all right so I'm getting a function it gets an array of points and the whole point of this function is now to return the total distance between all those points in the order that they are so I need some sort of sum that starts at zero I need a loop where I start at zero I go all the way through the length of that array and I say what so if this is my this is my order I want to know this distance Plus this distance Plus this distance Plus this distance so I always want to know the distance between I and I plus 1 and then this becomes I and this becomes I plus 1 etc etc so if I come back here I'm going to say var D equals distance between points index I X points index I Y points index i + 1 dot X points index i + 1 dot y okay and then I'm going to add that sum + equals D and then I'm just going to return the sum so by the way this is a function in p5 that calculates the distance for you between two points so I'm giving it points index I X&Y points index i + 1 x + y so that should be that is now later i'm going to optimize this because this is actually going to be kind of a slow operation to calculate distance and there's a way later that i mean i could speed this up but when i'm trying to do this zillions and gazillions of times speeding it up could be a good thing ok now what i'm going to do is i'm going to say i want to have a variable called record distance now so the first thing i want to do is whatever order this array is calculated first i want to know calc distance of cities right calculate the distance for this array cities and then the record distance is that first distance so i'm going to try and again a random set of points i'm going to get a distance between those and that's my best so far then remember down here i did a swap so I shuffled it around so once I did a swap let's calculate that distance again of cities and then if that distance is less than the record distance then record distance equals that distance so this is me just checking all like randomly swapping things around this again is not going to be an efficient algorithm for solving the traveling salesperson I'm building it this way just to show what the problem is and how kind of impossible it is to find that optimal solution with a certain number of points so what I want to do here is just say console whoops what I want to say is console dot log record distance so we can kind of look at these values as I'm finding them so let's run this program now oops sketch j/s line 55 what mistake did I make points okay again a list of points ah of course I meant to I made this mistake on purpose and because I wanted to correct it later and then I forgot about it so what's the problem here remember I'm checking in the array element I and the next one I plus one so I can't go to the end of the array if I go to the end of the array there's no I plus one there's no element after the end of the array I don't actually care because that's the end of my journey that's the end of my traveling to catch all my pokemon or whatever I'm doing later somebody will dub this video over with whatever is to do a thing like um never mind I don't know what the newest thing will be won't be Pokemon it'll be cool about that huh okay so I need to add a minus 1 here so I don't go to the last one ok now we can see I'm getting these nice so far I had a distance of 105 which was the record and at some point it got a distance of 76 and then they got a distance of 19 pixels through all of those points that seems kind of insane to me not unless I don't know if we're ever going to beat that record in a while so let's run this one more time and see like yeah so you can see this optimizing I'm not saving what that optimal what that optimal path is so that's the next step that I want to look at so I might need your help in the chat here I'm not really a JavaScript programmer that's a confession I have to make to you and I know I feel like in the let's look actually so there must be a way I went what did one thing I want to do is make a copy of an array I'm going to need to be able to do that because if I have an array with an ordered list of vectors I want to be able to like save a version of that if it's a really good one and I could write my own function to copy an array and I'm kind of tempted just do that to know that it works but let's let's take a minute in this video to and somebody in the chat will oh did I forget return some oh thank you no wonder this is a big bug I just had by the way somebody in the chat just mentioned another bug where I was returning D which makes no sense at all because I'm just returning the last distance which of course Y that value didn't make any sense so return sum is correct let's run this again to take a look at it there we go these values make much more sense right so you can see like it's you know thousands of pixels between all these points and you can see that the best one that I've gotten so far okay so I'm running that now let me go back to what I was doing is I'm going to go to a mozilla developer dock array something like this I'm googling that to get to here and what I want to look for is like what are all of the available functions things that I've used I've used push which is a function in array that adds an element to an array reverse whoo I might need to use reverse later on shift oh there's so many things I might use but I'm looking for one I think slice might do this for me the slice method returns a shallow copy of a portion of an array into a new array object let's explore if this is what's going to work for me so I'm just going to go over here this is how I like to figure things out I'm going to go into the console here while this is running I'm just going to make an array that's like 1 5 6 and I'm going to look at that array it's 1 5 6 now I want to say B equals a dot slice what does that give me B is also 1 5 6 that's good that's what I need what if I say now B index 2 equals 7 1 5 7 and a is still 1 5 6 so this should work for me and I believe shallow means because I'm actually not putting numbers in there I'm actually gonna put a raise and sorry vectors in there that though those it will copy the vectors it just going to copy the array and that's exactly what I want because I want to keep that same list of vectors it's just the arrays are pointing to the same vector object but in a different position in the array so this is going to work poor perfectly for me so hopefully I got that explanation right things are gonna work people in chat are giving me good advice about shallow copy I might have messed up that explanation I'll correct it as I continue to talk in this video you yes you are watching a video of a person teaching about programming who really does not know what he's doing okay so let's come back and let's say what I want to do is I'm going to say best-ever and what I want to say here is uh best you know you know there was a show that I used to watch back when I watch television we don't have time for anymore which was called best week ever so this is best I guess that's from you know there's the whole Simpsons thing best anyway whatever never my best cities path ever is cities to start and then every time I find a record oh no it's uh I want to actually say dot slice I want a copy of it and then every time I get a record I want to say best ever is city's slice so just to see if this is working what I want to do is I want to draw the path twice I want to draw the current cities and I want to draw the best ever and I'm going to make the best ever thicker and some pinkish purplish color and I'm to make the current cities thinner and white so let's run this yeah this is working so I think it's I believe this is doing what I wanted to do which is just randomly swapping things and every time we can look here and see that oh I took the print line out but you can see the pink path is currently the best path that it's got now with ten points I can see here like this is no good like over here this part is like terrible because look at that crossing I could easily myself just design like go here I can't I can't do this like this people who do the weather on television are like so good at this I could go here then I could go here then I could go there than anyway you could see how you could easily design a more efficient path so this isn't going to get us that most efficient path that's what future videos that I'm going to go into the next steps are going to explore but let's just see that this program is working by just having four points because I think we can probably visually see that looks like the best path between those four points saying there it looks like it's kind of finding it rather quickly right you can kind of imagine you know arguably is it going to be better I don't think so but you can see it's going to randomly kind of try every possibility with just four points rather quickly we can even try five cities and you can see that it's kind of finding it so you know you know if I slow this down if I draw it more artistically if I allow the user to interact with it by adding points and that's sort of an interesting thing right DRI I don't you know these are might be some things that you can explore so I'm kind of finished with this first video demonstrating the traveling's know what the Bell does but it's a thing with this traveling salesperson problem in the next video what I'm going to do is show you how to not just randomly swap points to try a bunch of different possibilities but actually sort an array of numbers with every single possible permutation so we can actually just try every single possibility in order which I think has some kind of interesting creative applications to it as well so I'm going to do that in the next next video okay so thanks for watching this one and the the next video will follow up on this okay talk to you soon

Channel: The Coding Train

Views: 239,600

Keywords: shiffman, p5js, p5.js tutorial, processing tutorial, creative coding, traveling salesman, traveling salesperson, permutation, lexical ordering, lexicographic ordering, nature of code, coding challenge, genetic, genetic algorithms, genetic algorithm, algorithm, evolution, challenge, patreon, brute force, factorial, swap, javascript swap, lexicographical ordering, coding, salesperson, traveling, p5.js, TSP, TSP algorithm, TSP brute force, traveling salesman problem

Id: BAejnwN4Ccw

Length: 22min 55sec (1375 seconds)

Published: Wed Aug 24 2016