[FEATURE REQUEST] Adding the Travelling Salesman Problem

DBasu2610 commented 4 days ago

What would you like to Propose?

Problem Statement: Given a set of cities and the distances between each pair, the objective is to find the shortest possible route that visits each city exactly once and returns to the starting point.

Input: A list of cities and the distance (or cost) between each pair of cities.

Output: The shortest route that covers all cities once and returns to the start.

Type: NP-hard problem, meaning it's computationally difficult to find an exact solution for larger inputs in polynomial time.

Brute Force Approach: Check all possible permutations of cities (factorial time complexity, O(n!)).

Dynamic Programming Approach: More efficient than brute force, using memoization to store intermediate results (O(n² * 2ⁿ)).

Approximation Algorithms: Used for larger instances, such as the Nearest Neighbor and Christofides' Algorithm.

So, we would use the Dynamic Programming Approach since it is more efficient.

Issue details

Problem Statement: Given a set of cities and the distances between each pair, the objective is to find the shortest possible route that visits each city exactly once and returns to the starting point.

Test Case Input: Number of cities: 4 Distance matrix:

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0 Explanation: There are 4 cities numbered from 0 to 3. The distance between each pair of cities is represented in the matrix, where dist[i][j] is the distance between city i and city j. For example:

Distance from city 0 to city 1 is 10. Distance from city 0 to city 2 is 15. Distance from city 1 to city 3 is 25, and so on. Expected Output: The minimum cost of the tour is: 80

Shortest Path: The optimal path is: 0 → 1 → 3 → 2 → 0, with a total distance of 80.