python TSP 深度搜索

您好！对于解决旅行商问题（TSP），深度搜索是一种常见的方法之一。下面是一个用深度优先搜索（DFS）解决TSP问题的示例代码：

import sys

def tsp(graph, visited, current_city, n, count, cost, ans):
    if count == n and graph[current_city][0]:
        ans.append(cost + graph[current_city][0])
        return
    
    for next_city in range(n):
        if not visited[next_city] and graph[current_city][next_city]:
            visited[next_city] = True
            tsp(graph, visited, next_city, n, count + 1, cost + graph[current_city][next_city], ans)
            visited[next_city] = False

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

# 示例输入
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

print("最小旅行商路径长度：", solve_tsp(graph))

上述代码使用了递归的深度优先搜索方法来解决TSP问题。它通过遍历每个未访问过的城市，计算当前路径的总成本，并继续向下一个未访问城市进行深度搜索。最后，它将找到的最小路径长度存储在`ans`列表中，并输出最小长度。

请注意，该代码仅解决了TSP问题的路径长度，而不是具体路径。如果需要求解具体路径，可以在`tsp`函数中添加一个列表来存储路径，并在找到更短路径时更新该列表。

希望对您有所帮助！如果您有任何其他问题，请随时提问。