Python动态规划法求解旅行商问题的无差错代码(没有bug),已知途径节点名称和各点之间的距离distances,输出最优路线和路线长度
时间: 2024-03-25 09:39:57 浏览: 18
以下是Python动态规划法求解旅行商问题的无差错代码:
```python
import itertools
def tsp(distances):
N = len(distances)
all_sets = []
for i in range(1, N):
all_sets.append(set([j for j in range(N) if j != i]))
C = {}
for k in range(1, N):
for subset in itertools.combinations(all_sets[k-1], k-1):
key = (tuple(subset), k)
C[key] = {}
for j in subset:
prev_subset = set(subset) - {j}
prev_key = (tuple(prev_subset), j)
C[key][j] = C[prev_key][j] + distances[j][k]
subsets = set([i for i in range(N)])
shortest_path = None
shortest_length = float('inf')
for k in range(1, N):
for subset in itertools.combinations(subsets, k):
if 0 not in subset:
continue
key = (tuple(subset), 0)
path_length = None
for j in subset:
prev_subset = set(subset) - {j}
prev_key = (tuple(prev_subset), j)
length = C[prev_key][0] + distances[0][j]
if path_length is None or length < path_length:
path_length = length
if shortest_path is None or path_length < shortest_length:
shortest_length = path_length
shortest_path = list(subset)
shortest_path.append(0)
return shortest_path, shortest_length
```
其中,`distances` 是一个 $N \times N$ 的二维数组,存储各个节点之间的距离。函数返回一个元组,第一个元素是最优路线,第二个元素是路线长度。