Traveling Salesman Problem (TSP) Using Dynamic Programming

new
Extreme
Typescript
Oct 22, 2023
2,500
-
3,500

Objective:

The Traveling Salesman Problem (TSP) is a classic optimization problem. Given a list of cities and the distances between each pair of cities, your task is to find the shortest possible route that visits each city exactly once and returns to the original city. This problem is known to be NP-hard and has no known efficient solution other than brute force for small input sizes.

Requirements:

  1. Implement a TypeScript function calledtspthat takes an array of cities and a 2D array representing the distances between each pair of cities.

  2. The function should return an array representing the optimal order in which to visit the cities to minimize the total distance traveled.

  3. You should use dynamic programming or another efficient algorithm to solve the TSP.

Example:

const cities = ["A", "B", "C", "D"];
const distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
];
console.log(tsp(cities, distances)); // Output: ["A", "B", "D", "C"]

Your challenge is to implement thetspfunction in TypeScript to find the optimal order to visit the cities, minimizing the total distance traveled in the Traveling Salesman Problem.

Fork the Code Sandbox, do notupdateit in the website here, because Code Sandbox doesn't recognize you unless you open it in the website.
Supports markdown syntax.
You can submit your answer only once, so make sure you have the correct answer before submitting.