Challenge: The Traveling Salesman Problem
Explore how to solve the Traveling Salesman Problem by calculating the minimum distance to visit all cities exactly once and return to the start. Learn to create a basic algorithm and then optimize it using dynamic programming techniques to improve efficiency in complex pathfinding challenges.
We'll cover the following...
Problem statement
You are given a map that has cities on it. All of the cities are connected directly to each other via distinct routes of variable lengths. You, being a salesman, have to travel to each of these cities on a business trip. But your company wants you to be very careful with the travel expenses and wants you to spend the least amount possible. Expenditure is a function of the distance traveled, so you want to minimize the total distance traveled. Find the length of the shortest path to travel all the cities.
Input
You will be given a 2-d matrix, distances, of size ...