‎Gemini - Solving the Travelling Salesman Problem

Provide the Python code for the Travelling Salesman Problem

Python
import numpy as np

def travelling_salesman_problem(graph):
    """
    Solves the Travelling Salesman Problem using dynamic programming.

    Args:
      graph: A 2D numpy array representing the adjacency matrix of the graph, 
             where graph[i][j] is the distance between city i and city j.

    Returns:
      A tuple containing:
        - The minimum distance to travel to all cities and return to the starting city.
        - The optimal path (list of city indices).
    """
    n = len(graph)
    all_visited = (1 << n) - 1  # all_visited represents all cities visited

    # Initialize a memoization table
    dp = [[None] * n for _ in range(1 << n)]

    def tsp(mask, pos):
        """
        Recursive function to calculate the minimum distance.

        Args:
          mask: An integer representing the set of visited cities (bitmask).
          pos: The current city.

        Returns:
          The minimum distance to visit the remaining cities and return to the starting city.
        """
        if mask == all_visited:
            return graph[pos][0]  # Return to the starting city

        if dp[mask][pos] is not None:
            return dp[mask][pos]

        min_cost = float('inf')
        for city in range(n):
            if mask & (1 << city) == 0:  # If city is not visited
                new_cost = graph[pos][city] + tsp(mask | (1 << city), city)
                min_cost = min(min_cost, new_cost)

        dp[mask][pos] = min_cost
        return min_cost

    # Start from city 0 with no other city visited
    min_distance = tsp(1, 0)

    # Backtrack to find the optimal path
    path = [0]
    mask = 1
    current_city = 0
    while mask != all_visited:
        for next_city in range(n):
            if mask & (1 << next_city) == 0:
                if dp[mask][current_city] == graph[current_city][next_city] + dp[mask | (1 << next_city)][next_city]:
                    path.append(next_city)
                    mask |= (1 << next_city)
                    current_city = next_city
                    break

    path.append(0)  # Return to the starting city
    return min_distance, path

# Example usage:
graph = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
])

min_distance, path = travelling_salesman_problem(graph)
print("Minimum Distance:", min_distance)
print("Optimal Path:", path)

Explanation:

Initialization:
- graph: Represents the distances between cities.
- n: The number of cities.
- all_visited: A bitmask to indicate when all cities have been visited.
- dp: A memoization table to store calculated results and avoid redundant calculations.
tsp(mask, pos) function:
- This recursive function explores all possible paths.
- mask: Keeps track of visited cities using a bitmask (e.g., 1011 means cities 0, 1, and 3 are visited).
- pos: The current city.
- Base Case: If all cities are visited (mask == all_visited), return the distance from the current city to the starting city (graph[pos][0]).
- Memoization: If the result for the current mask and pos is already calculated, return it from dp.
- Recursive Step: Iterate through unvisited cities, calculate the cost of going to the next city and recursively call tsp with the updated mask and position.
- Store the minimum cost in dp[mask][pos].
Main part:
- min_distance = tsp(1, 0) starts the process from city 0 (mask = 1 means only city 0 is visited).
- Backtracking: The code then backtracks through the dp table to reconstruct the optimal path.

Example Usage:

The provided example uses a graph with 4 cities. The output will be:

Minimum Distance: 80
Optimal Path: [0, 1, 3, 2, 0]

This means the shortest route starts at city 0, goes to city 1, then city 3, then city 2, and finally returns to city 0, with a total distance of 80.

Note: This dynamic programming solution has a time complexity of O(n^2 * 2^n), which is better than the brute force approach (O(n!)) but still computationally expensive for large numbers of cities. For larger instances of the TSP, you might need to consider approximate algorithms like simulated annealing or genetic algorithms.