旅行商问题python代码回溯法

旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，目标是找到一条路径，使得旅行商能够访问给定的一组城市，并且总路径长度最短。

下面是使用回溯法解决旅行商问题的Python代码示例：

import sys

def tsp(graph, visited, curr_pos, n, count, cost, ans):
    if count == n and graph[curr_pos][0]:
        ans[0] = min(ans[0], cost + graph[curr_pos][0])
        return

    for i in range(n):
        if not visited[i] and graph[curr_pos][i]:
            visited[i] = True
            tsp(graph, visited, i, n, count + 1, cost + graph[curr_pos][i], ans)
            visited[i] = False

def solve_tsp(graph):
    n = len(graph)
    visited = [False] * n
    visited[0] = True
    ans = [sys.maxsize]
    tsp(graph, visited, 0, n, 1, 0, ans)
    return ans[0]

# 示例使用
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15,35, 0, 30],
    [20, 25, 30, 0]
]

min_cost = solve_tsp(graph)
print("最短路径长度为:", min_cost)

这段代码使用了递归的回溯法来解决旅行商问题。它通过遍历所有可能的路径，并计算路径的总长度，最后返回最短路径的长度。