Python动态编程TSP要打印路由

Question

我通过以下算法得到了tsp的最短路径长度

如何修改此算法以获得最短路径

def tsp_helper(W,i,S,mem):
if S == 0:
return 0
elif mem[i][S] != None:
return mem[i][S]
else:
mem[i][S] = float('infinity')
for j in range(len(W)):
if S & (1<<j) != 0:
best = W[i][j] + tsp_helper(W,j,S^(1<<j),mem)
if best < mem[i][S]:
mem[i][S] = best        
return mem[i][S]
def tsp_memoized(W):
mem = [[None]*(1<<len(W)) for _ in range(len(W))]
return tsp_helper(W,0,(1<<len(W))-2,mem)
C = [[0,3,6,7],
[5,0,2,3],
[6,4,0,2],
[3,7,5,0]]
print(tsp_memoized(C))

我正在尝试添加一个best_path列表来包含路由节点

Answer 1

您可以存储如何计算每个路径权重及其值。这样，当你想要找到一条路径时，你可以每次后退一步，直到你到达你开始的地方。

代码看起来像这样:

import sys
def tsp_helper(W,i,S,mem):
if S == 0:
return (0, None)
elif mem[i][S] != None:
return mem[i][S]
else:
mem[i][S] = (sys.float_info.max, None)
for j in range(len(W)):
if S & (1<<j) != 0:
best = W[i][j] + tsp_helper(W,j,S^(1<<j),mem)[0]
if best < mem[i][S][0]:
mem[i][S] = (best, j)        
return mem[i][S]
def tsp_memoized(W):
mem = [[None]*(1<<len(W)) for _ in range(len(W))]
S = (1<<len(W))-2
result = tsp_helper(W,0,S,mem)
cur = result
path = [0]
while cur is not None:
path.append(cur[1])
S ^= (1<<cur[1])
cur = mem[cur[1]][S]
return result[0], path

C = [[0,3,6,7],
[5,0,2,3],
[6,4,0,2],
[3,7,5,0]]
print(tsp_memoized(C))

另外，我认为值得一提的是，你现在计算的是哈密顿路径，而不是循环。