[已解决]有序最短路径问题求助，具体问题如下

小甲鱼

1. import sys
   
2. 
   
3. def tsp(distances):
   
4.     n = len(distances)
   
5.     all_points_set = set(range(n))
   
6. 
   
7.     # memo keys: tuple(sorted_points_in_path, last_point_in_path)
   
8.     # memo values: tuple(cost_thus_far, next_to_last_point_in_path)
   
9.     memo = {(tuple([i]), i): tuple([0, None]) for i in range(n)}
   
10.     queue = [(tuple([i]), i) for i in range(n)]
    
11. 
    
12.     while queue:
    
13.         prev_visited, prev_last_point = queue.pop(0)
    
14.         prev_dist, _ = memo[(prev_visited, prev_last_point)]
    
15. 
    
16.         to_visit = all_points_set.difference(set(prev_visited))
    
17.         for new_last_point in to_visit:
    
18.             new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))
    
19.             new_dist = prev_dist + distances[prev_last_point][new_last_point]
    
20. 
    
21.             if (new_visited, new_last_point) not in memo:
    
22.                 queue += [(new_visited, new_last_point)]
    
23.             memo[(new_visited, new_last_point)] = min(
    
24.                 memo.get((new_visited, new_last_point), (float('inf'), None)),
    
25.                 (new_dist, prev_last_point))
    
26. 
    
27.     optimal_path, optimal_cost = retrace_optimal_path(memo, n)
    
28. 
    
29.     return optimal_path, optimal_cost
    
30. 
    
31. def retrace_optimal_path(memo: dict, n: int) -> [[int], float]:
    
32.     points_to_retrace = tuple(range(n))
    
33. 
    
34.     full_path_memo = dict((k, v) for k, v in memo.items() if k[0] == points_to_retrace)
    
35.     path_key = min(full_path_memo.keys(), key=lambda x: full_path_memo[x][0])
    
36. 
    
37.     last_point = path_key[1]
    
38.     optimal_cost, next_to_last_point = memo[path_key]
    
39. 
    
40.     optimal_path = [last_point]
    
41.     points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))
    
42. 
    
43.     while next_to_last_point is not None:
    
44.         path_key = (points_to_retrace, next_to_last_point)
    
45.         _, next_to_last_point = memo[path_key]
    
46. 
    
47.         optimal_path = [path_key[1]] + optimal_path
    
48.         points_to_retrace = tuple(sorted(set(points_to_retrace).difference({path_key[1]})))
    
49. 
    
50.     return optimal_path, optimal_cost

复制代码

在这段代码中，distances是一个二维数组，表示每两个城市之间的距离。tsp函数返回一个元组，第一个元素是一个列表，表示最优路径（城市的顺序），第二个元素是这个路径的总成本。

这个算法的时间复杂度是O(n^2 * 2^n)，空间复杂度是O(n * 2^n)。这是因为算法需要枚举所有可能的路径，并且需要记住之前计算过的路径的成本。其中，n是城市的数量。

请注意，这个算法假设距离矩阵是对称的，也就是说，从城市A到城市B的距离和从城市B到城市A的距离是相同的。如果这个假设不成立，那么你需要修改这个算法，使其可以处理这种情况。

小甲鱼

旅行商问题噢~