No video :(

Coding Challenge #35.1: Traveling Salesperson

Подписаться 1,7 млн

Просмотров 288 тыс.

50% 1

In Part 1 of this multi-part coding challenge, I introduce the classic computer science problem of the Traveling Salesperson (TSP) and discuss the pitfalls with a brute force solution. In Part 2, I discuss Lexicographic Ordering and demonstrate one algorithm to iterate over all the permutations of an array. In Part 3, I apply this algorithm to a brute-force solution of the TSP problem. Every single route permutation is checked one by one. In Part 4, I attempt to create a solution to the TSP problem with a genetic algorithm, and then I add a “crossover” algorithm in Part 5. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): editor.p5js.org/codingtrain/s...
🕹️ Part 2: Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 3: TSP with Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 4: TSP with Genetic Algorithm: editor.p5js.org/codingtrain/s...
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 2: Lexicographic Order: • Coding Challenge #35.2...
📺 Part 3: TSP with Lexicographic Order: • Coding Challenge #35.3...
📺 Part 4: TSP with Genetic Algorithm: • Coding Challenge #35.4...
📺 Part 5: TSP with Genetic Algorithm and Crossover: • Coding Challenge #35.5...
🎥 Previous video: • Coding Challenge #34: ...
🎥 Next video: • Coding Challenge #36: ...
🎥 All videos: • Coding Challenges
References:
🌐 Traveling Salesman on Wikipedia: en.wikipedia.org/wiki/Travell...
🗨️ Permutation Algorithm Using Lexicographic Ordering: www.quora.com/How-would-you-e...
📝 Array on MDN: developer.mozilla.org/en/docs...
📝 Array.includes() on MDN: developer.mozilla.org/en/docs...
📝 Array.reverse() on MDN: developer.mozilla.org/en/docs...
📝 ES6 Sets on MDN: developer.mozilla.org/en/docs...
💾 The Nature of Code Part 2: github.com/shiffman/NOC-S17-2...
📕 The Nature of Code: natureofcode.com/
Videos:
🎥 Improved Pool Selection: • 9.8: Genetic Algorithm...
🎥 Genetic Algorithm Playlist: • 9: Genetic Algorithms ...
🔴 Live Stream Archive #57: • Live Stream #57 - Trav...
Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: • Coding Challenge #29: ...
🚂 #51 A* Pathfinding Algorithm: • A* Pathfinding Algorit...
🚂 #69 Evolutionary Steering Behaviors: • Coding Challenge #69: ...
🚂 #70 Nearest Neighbors Recommendation Engine: • Coding Challenge #70: ...
Timestamps:
00:00 Welcome to this coding challenge!
00:50 What is the Traveling Salesperson problem?
04:50 Code! Placing random cities on the canvas
07:30 Go through the cities in order
08:13 Shuffling the array with swaps
11:35 Computing the distance and saving the shortest one
15:20 Oups! Fixing an array index error
17:00 How to make a copy of an array?
19:43 Storing a copy of the best cities path ever
20:24 Drawing the best cities path ever
21:00 The limits of this brute force algorithm
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: ru-vid.comjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js

Опубликовано:

12 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 339

@neomage2021 7 лет назад

As a software engineer I enjoy watching these videos. I find them relaxing. You are really good at teaching. Keep up the good work!

@TheCodingTrain 7 лет назад

That's so nice to hear thank you!

@insidioso4304 7 лет назад

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"

@ericowens9050 6 лет назад

Derick Hess Same here. Makes me feel better to not be alone in that feeling. :-)

@Pradeep.Poonia 4 года назад

@@TheCodingTrain Does Derick look like the guy who wrote this paper : ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-goUlyp4rwiU.html @DerickHess

@amandixit3555 3 года назад

@@TheCodingTrain choo choo , abey bada ho ja bhai. choo choo

@clementbuchanan587 3 года назад

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.

@manurok1901 8 лет назад

Love these videos! Been binge watching while I'm off work the past couple of days :p Keep it up man, you're inspiring

@Lehiannel 7 лет назад

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!

@kevnar 3 года назад

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.

@nowar9220 7 лет назад

first channel ive ever subscribed to!! Really worth it :) Thanks! Apreciate it!!

@jhokeypokey 5 лет назад

I come from the future to let you know that this is still interesting.

@pretzels3273 5 лет назад

Jared Fairchild and Pokémon go is relevant again

@Seedx 4 года назад

Welp it’s 2020

@t__v_____290 4 года назад

Not anymore buddy

@bechirjamousi6696 4 года назад

TSP needs to get back to its initial position and in this case, it is not , am i right?

@jetison333 3 года назад

Further in the future here, can confirm its still interesting

@bikachu_ 3 года назад

you're a great teacher and thanks for being so enthusiastic about programming, it really keeps me going!

@mihaitmf 5 лет назад

Man, that's awesome! So simple, yet so neat.

@TheDogn 7 лет назад

7:13 The bell was a hilariously unexpected touch.

@per1sher 8 лет назад

Fascinating video - always enjoy your channel - your enthusiasm is infectious :)

@nataliekidd2135 7 лет назад

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.

@Hyuts 5 лет назад

I finally downloaded processing! Very cool and easy to install plus allows me to follow along and use all github projects. Thanks!

@sherhy3689 7 лет назад

patient, adequately funny, and informative, please continue this as long as you can --tokyo

@golfball_diver 5 лет назад

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.

@alirizvi710 2 года назад

yeah otherwise its just a minimum spanning tree problem

@themanwiththeplan8404 2 года назад

isn't that a hamilton cycle?

@charpencil 2 года назад

TSP is shortest hamiltonian cycle yes

@heavencanceller1863 3 года назад

These videos are both priceless information and entertainment

@davidstephen2219 8 лет назад

Simple and easy as always. Keep go on. I wish I was one of your students in your class. );

@ronraisch510 6 лет назад

I yelled "SUM!!!" at the screen for like 4 min lol

@nraynaud 4 года назад

I used a traveling salesman in a CNC application, when milling a bunch of pockets, to choose the order of the pockets.

@omaryahia 2 года назад

your videos are amazing, thank you Daniel

@Ensii 7 лет назад

Your enthusiasm is priceless :) nice video

@TheCodingTrain 7 лет назад

Thank you!

@omshrisn2909 7 лет назад

I like your approach of programming!!! , understood more clearly than what teachers teach in my college thanks 😃

@deathvall3y 5 лет назад

Energetic.... and lots of love for you

@seanhudson8453 5 лет назад

Came here for my uni course. Stayed for the flamboyancy

@anonymousvevo8697 4 года назад

i come from 2020 and your video is still awsome

@sina-qh8wm 3 года назад

I created a presentation in university based on this video, thanks a lot :)

@sairamankilambi5007 3 года назад

2020 it is! Travelling back in time to understand Travelling Sales Person problem...

@josbex1684 7 лет назад

Interesante gracias... aplicare ahora la heuristica anneling para calcular mas rápido la ruta mas corta

@kevnar 6 лет назад

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?

@MrCmon113 6 лет назад

Damn, Sally is even worse than Chuck, who's always trying to spy on Alice and Bob.

@Violet-tb8xo 5 лет назад

@@MrCmon113 eve?

@kyokarson8233 5 лет назад

@@MrCmon113 we used to have Darth spying on alice and bob when the love birds wanted to talked :p

@arumifitria5433 4 года назад

Thanks u inspired me a lot

@kavinbharathi 3 года назад

_why? Just why?_

@DodaGarcia Год назад

1:10: "Oh a Pokémon Go analogy, this will be easy to follow!" 1:15: "N-dimensional? I'm lost"

@dibibob1474 6 лет назад

smart and helpful. thanks sir :)

@gadeichhorn 5 лет назад

great stuff! would like to see ant colony simulation for the same problem or event multiple sales doing each multiple visits.

@LorenzoLeonardini 8 лет назад

"What are the things in your world that you need to find the path way through?" everything in my room I guess

@amateuraaron6972 2 года назад

Hey Dan! Just wanted to say its 2022 about 6 years later Pokemon Go is still relevant enough for this video hahaha

@gunot5656 7 лет назад

this guy is incredibly entertaining, lol

@Thijs-Kuiken 5 лет назад

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.

@Mosch822 7 лет назад

Great Video. Wanna see more

@oskarkrogsgard3014 7 лет назад

Diiiing. You are so silly. I love it! :-D

@assimez-zaky8363 3 года назад

This is relaxing

@nickgooch6928 7 лет назад

You should use something like this to solve the Maze Generator you made ; )

@exorcistgg9833 5 лет назад

lol I was trying to design a program that calculate the shortest distance to go to all pokestop😂 And then I found your vid

@glenneric1 2 года назад

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.

@aryamankejriwal5959 7 лет назад

For the latest thing, the points would be shops where the Nintendo switch is possibly present...

@-rXr- 8 лет назад

Hi denial, love your vids, can you make a video on A* path finding algorithm plz

@Nerdthagoras 7 лет назад

I plan to use this to find the optimal route while shopping for various items at Walmart!

@TheCodingTrain 7 лет назад

Haha, look forward to hearing how that goes!

@jschoete3430 7 лет назад

Hi ! Can I ask what studies you did, and what kind of work you do? I'm myself studying IT, and I love these videos and I would like to code like this all day long. also if it's not too much to ask, how much do you make with your job? I know it's a bit of a taboo question, so feel free to ignore ^^

@earthx7463 5 лет назад

informative and funny XD

@pqazx1 3 года назад

how to take input from user for the dist bw points ??and then do this??

@michaellazar9078 6 лет назад

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?

@ruyuehong2392 6 лет назад

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?

@DodaGarcia Год назад

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.

@Tin98Tin 7 лет назад

Please do more in Processing!

@stephfong4577 7 лет назад

Wow, I hope I knew about your channel earlier!

@memporium240 3 года назад

You can actually reach an upper bound of n^2*2^n which is a better bound than n factorial.

@sensei0101 7 лет назад

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?

5 лет назад

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!

@luiginotcool 3 года назад

Hey I’m from the future and this is actually really useful for solving shwolobatata-hmm problems

@eldiagrama 7 лет назад

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); } }

@jwbonnett 6 лет назад

How would you going about adding obstacles?

@amit_awadhi 3 года назад

It should be renamed to "Catching-Pokemon-Problem"😂👌

@maxkolbl1527 7 лет назад

Pokemon Go was actually the real reason I got interested in this problem... ^^'

@zyzo99 6 лет назад

One thing i dont get is why the upper boundary in the loops use to be < and not

@bhavyabhatia2337 6 лет назад

Is there a video for this solution using DP, not brute force ?

@hymntosea 4 года назад

Thanks

@rodneyjohnson9476 Год назад

I want to use this algorithm but where can I find the listing that explains the Java functions in basic command set

@wardiofficial6945 7 лет назад

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

@makarandlahane3904 7 лет назад

as you said we want the total sum of all distances,then why haven't you returned the sum from calcDistance function?

@muhammadzeeshan6965 6 лет назад

very good

@rafageist Год назад

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.

@arhabersham 6 лет назад

Help! At 10:05 , I don't see index (element?) [3]... I only see [0] to [2] . Did I miss something?

@RetroGamingClashOfClans 6 лет назад

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

@izoumashka 7 лет назад

well you can narrow down possible paths by just working out which are "edge" vertices and starting from them.

@Invenitive 6 лет назад

Why did you do linear paths instead of round trips? All of the examples I've seen of the TSP use round trips

@ErikHarloff 7 лет назад

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!

@cesarrios3449 7 лет назад

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 :)

@TheCodingTrain 7 лет назад

Try some of these workflow videos! (let me know if they are helpful) sublime text: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-UCHzlUiDD10.html atom editor: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-d3OcFexe9Ik.html brackets: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-nmZbhManVcY.html codepen: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-5gfUgNpS6kY.html

@Teth47 7 лет назад

So it turns out Windows 10's calculator can handle some pretty big numbers, 3000! is ~4.19^9130. Not bad.

@lumschente 5 лет назад

My Android calculators max is 13547! = 1.085^50089

@Tuberex 4 года назад

4,1493596034378540855568670930866 with 9130 zeros

@Tuberex 4 года назад

@@lumschente the biggest on windows 10 is 3248

@unchaynd7266 Год назад

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)

@tythedev9582 3 года назад

I am a simple man. I see your videos in my recommendations. I watch. LMBO @16:11 "shmoley-patat-in"?

@yerkoantonioalvarez 5 лет назад

Great video! But tsp requires to return to initial citie

@joesmith2715 7 лет назад

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?

@epicmonckey25001 7 лет назад

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!

@DinGDonGvideoProduction 6 лет назад

finlly got u

@sudhamahajan2272 3 года назад

How to stop this prog after iterations are completed..?

@davatron5000 8 лет назад

👍🏻 for "schmullivatatani"

@florianreichelt 6 лет назад

cool!:)

@ea1thy 5 лет назад

Could you please show what's in your index.html so far?

@johnkarippery9919 4 года назад

can you please make a video about VRP algorithm?

@sujals7108 5 лет назад

instead of writing 'bestEver = cities.slice();', you can just write 'bestEver = cities;'. It copies the array exactly

@rankail 5 лет назад

He did it that way first and then "corrected" it. XD

@felc_9415 6 лет назад

is that have a relation with the chinese postman problem ?

@sudhamahajan2272 4 года назад

how do u make that animation part??what do u use??

@kaal_bhairav_23 4 года назад

The time complexity can be reduces from n! to (n-1)! since we can fix a point and permute the remaining (n-1) points.

@BradHouser 3 года назад

And assuming the distance from A to B equals the distance from B to A, you can divide (n-1)! by 2.

@Codie__ 7 лет назад

What library would be good to use in Python to take care of drawing the lines and visually representing this algorithm?

@funxiobolic 7 лет назад

Check out pyGame. It's a Python library aimed at game developers, so it has a lot of drawing/graphics functions.

@Gegellibu 8 лет назад

For the different path calculations the formula is actually n!/2 as ABC is the same path as CBA

@vernonalbayeros4719 7 лет назад

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"

@Habbxor 7 лет назад

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)

@stoobertb 7 лет назад

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.

@Habbxor 7 лет назад

You're right. Prim's could lead to having to travel the same path again because it doesn't guarantee a linear path.