Youtor
Coding Challenge 351 Traveling Salesperson
>> YOUR LINK HERE: ___ http://youtube.com/watch?v=BAejnwN4Ccw
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: https://thecodingtrain.com/challenges... • p5.js Web Editor Sketches: • 🕹️ Part 1: Traveling Salesperson (TSP): https://editor.p5js.org/codingtrain/s... • 🕹️ Part 2: Lexicographic Order: https://editor.p5js.org/codingtrain/s... • 🕹️ Part 3: TSP with Lexicographic Order: https://editor.p5js.org/codingtrain/s... • 🕹️ Part 4: TSP with Genetic Algorithm: https://editor.p5js.org/codingtrain/s... • 🕹️ Part 5: TSP with Genetic Algorithm and Crossover: https://editor.p5js.org/codingtrain/s... • Other Parts of this Challenge: • 📺 Part 2: Lexicographic Order: • Coding Challenge #35.2: Lexicographic... • 📺 Part 3: TSP with Lexicographic Order: • Coding Challenge #35.3: Traveling Sal... • 📺 Part 4: TSP with Genetic Algorithm: • Coding Challenge #35.4: Traveling Sal... • 📺 Part 5: TSP with Genetic Algorithm and Crossover: • Coding Challenge #35.5: TSP with Gene... • 🎥 Previous video: • Coding Challenge #34: Diffusion-Limit... • 🎥 Next video: • Coding Challenge #36: Blobby! • 🎥 All videos: • Coding Challenges • References: • 🌐 Traveling Salesman on Wikipedia: https://en.wikipedia.org/wiki/Travell... • 🗨️ Permutation Algorithm Using Lexicographic Ordering: https://www.quora.com/How-would-you-e... • 📝 Array on MDN: https://developer.mozilla.org/en/docs... • 📝 Array.includes() on MDN: https://developer.mozilla.org/en/docs... • 📝 Array.reverse() on MDN: https://developer.mozilla.org/en/docs... • 📝 ES6 Sets on MDN: https://developer.mozilla.org/en/docs... • 💾 The Nature of Code Part 2: https://github.com/shiffman/NOC-S17-2... • 📕 The Nature of Code: http://natureofcode.com/ • Videos: • 🎥 Improved Pool Selection: • 9.8: Weighted Selection (for Genetic ... • 🎥 Genetic Algorithm Playlist: • 9: Genetic Algorithms - The Nature of... • 🔴 Live Stream Archive #57: • Live Stream #57 - Traveling Salesperson • Related Coding Challenges: • 🚂 #29 Smart Rockets in p5.js: • Coding Challenge #29: Smart Rockets i... • 🚂 #51 A* Pathfinding Algorithm: • A* Pathfinding Algorithm (Coding Chal... • 🚂 #69 Evolutionary Steering Behaviors: • Coding Challenge #69: Evolutionary St... • 🚂 #70 Nearest Neighbors Recommendation Engine: • Coding Challenge #70: Nearest Neighbo... • 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: http://thecodingtrain.com/ • 👾 Share Your Creation! https://thecodingtrain.com/guides/pas... • 🚩 Suggest Topics: https://github.com/CodingTrain/Sugges... • 💡 GitHub: https://github.com/CodingTrain • 💬 Discord: / discord • 💖 Membership: http://youtube.com/thecodingtrain/join • 🛒 Store: https://standard.tv/codingtrain • 🖋️ Twitter: / thecodingtrain • 📸 Instagram: / the.coding.train • 🎥 Coding Challenges: • Coding Challenges • 🎥 Intro to Programming: • Start learning here! • 🔗 p5.js: https://p5js.org • 🔗 p5.js Web Editor: https://editor.p5js.org/ • 🔗 Processing: https://processing.org • 📄 Code of Conduct: https://github.com/CodingTrain/Code-o... • This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecod... • #travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js
#############################
