如何修改代码实现起点终点不同的旅行商问题（TSP）求解？
2026-8-19
非闭合路径旅行商问题（TSP）求解修改指导
问题描述
这是旅行商问题（Travelling Salesman Problem，TSP），需要实现起点与终点不同的求解逻辑，现有常规闭合路径（起点终点相同）的Python求解代码和JavaScript全排列求解代码，以下是针对性修改方案。
现有闭合路径TSP代码
Python实现（闭合路径）
def Min(lst,myindex): return min(x for idx, x in enumerate(lst) if idx != myindex) def Delete(matrix,index1,index2): del matrix[index1] for i in matrix: del i[index2] return matrix def PrintMatrix(matrix): print("---------------") for i in range(len(matrix)): print(matrix[i]) print("---------------") n=int(input()) matrix=[] H=0 PathLenght=0 Str=[] Stb=[] res=[] result=[] StartMatrix=[] for i in range(n): Str.append(i) Stb.append(i) for i in range(n): matrix.append(list(map(int, input().split()))) for i in range(n):StartMatrix.append(matrix[i].copy()) float(inf) for i in range(n): matrix[i][i]=float('inf') while True: for i in range(len(matrix)): temp=min(matrix[i]) H+=temp for j in range(len(matrix)): matrix[i][j]-=temp for i in range(len(matrix)): temp = min(row[i] for row in matrix) H+=temp for j in range(len(matrix)): matrix[j][i]-=temp NullMax=0 index1=0 index2=0 tmp=0 for i in range(len(matrix)): for j in range(len(matrix)): if matrix[i][j]==0: tmp=Min(matrix[i],j)+Min((row[j] for row in matrix),i) if tmp>=NullMax: NullMax=tmp index1=i index2=j res.append(Str[index1]+1) res.append(Stb[index2]+1) oldIndex1=Str[index1] oldIndex2=Stb[index2] if oldIndex2 in Str and oldIndex1 in Stb: NewIndex1=Str.index(oldIndex2) NewIndex2=Stb.index(oldIndex1) matrix[NewIndex1][NewIndex2]=float('inf') del Str[index1] del Stb[index2] matrix=Delete(matrix,index1,index2) if len(matrix)==1:break for i in range(0,len(res)-1,2): if res.count(res[i])<2: result.append(res[i]) result.append(res[i+1]) for i in range(0,len(res)-1,2): for j in range(0,len(res)-1,2): if result[len(result)-1]==res[j]: result.append(res[j]) result.append(res[j+1]) print("----------------------------------") print(result) for i in range(0,len(result)-1,2): if i==len(result)-2: PathLenght+=StartMatrix[result[i]-1][result[i+1]-1] PathLenght+=StartMatrix[result[i+1]-1][result[0]-1] else: PathLenght+=StartMatrix[result[i]-1][result[i+1]-1] print(PathLenght) print("----------------------------------") input()
代码运行示例
- 输入：
4 - 输入4×4矩阵：
0 10 1 1 10 0 1 5 1 1 0 10 1 5 10 0
- 输出结果：
[1,4,4,2,2,3,3,1]，总长度8（闭合路径：1->4->2->3->1）
JavaScript全排列实现（闭合路径）
let towns = [ [0, 28, 58, 13, 24, 25, 31, 64], [28, 0, 82, 15, 52, 27, 33, 54], [58, 82, 0, 67, 82, 64, 49, 97], [13, 15, 67, 0, 37, 12, 18, 69], [24, 52, 82, 37, 0, 49, 53, 40], [25, 27, 64, 12, 49, 0, 15, 81], [31, 33, 49, 18, 53, 15, 0, 70], [64, 54, 97, 69, 40, 81, 70, 0], ]; let path = []; let counter = 0; let minPath = 10000; let minCounter; for (let i1 = 0; i1 <= 7; i1++) { for (let i2 = 0; i2 <= 7; i2++) { for (let i3 = 0; i3 <= 7; i3++) { for (let i4 = 0; i4 <= 7; i4++) { for (let i5 = 0; i5 <= 7; i5++) { for (let i6 = 0; i6 <= 7; i6++) { for (let i7 = 0; i7 <= 7; i7++) { for (let i8 = 0; i8 <= 7; i8++) { if ( i1 != i2 && i1 != i3 && i1 != i4 && i1 != i5 && i1 != i6 && i1 != i7 && i1 != i8 && i2 != i3 && i2 != i4 && i2 != i5 && i2 != i6 && i2 != i7 && i2 != i8 && i3 != i4 && i3 != i5 && i3 != i6 && i3 != i7 && i3 != i8 && i4 != i5 && i4 != i6 && i4 != i7 && i4 != i8 && i5 != i6 && i5 != i7 && i5 != i8 && i6 != i7 && i6 != i8 && i7 != i8 ) { path[counter] = i1 + 1 + " → " + (i2 + 1) + " → " + (i3 + 1) + " → " + (i4 + 1) + " → " + (i5 + 1) + " → " + (i6 + 1) + " → " + (i7 + 1) + " → " + (i8 + 1); console.log(path[counter]); if ( towns[i1][i2] + towns[i2][i3] + towns[i3][i4] + towns[i4][i5] + towns[i5][i6] + towns[i6][i7] + towns[i7][i8] < minPath ) { minPath = towns[i1][i2] + towns[i2][i3] + towns[i3][i4] + towns[i4][i5] + towns[i5][i6] + towns[i6][i7] + towns[i7][i8]; console.log(minPath); minCounter = counter; } counter += 1; } } } } } } } } } console.log( "Shortest Way: " + path[minCounter] + "(" + minPath + " KM.)" );
修改方案
一、Python代码修改（支持非闭合路径）
原代码核心是生成闭合回路，需去掉回到起点的逻辑，具体修改如下：
- 路径长度计算修改
删除原代码中添加回到起点的路径长度部分，只计算线性路径的相邻节点距离和：
# 替换原路径长度计算代码 for i in range(0, len(result)-1, 2): PathLenght += StartMatrix[result[i]-1][result[i+1]-1]
- 路径输出修改
原result数组是闭合回路的节点对，需移除最后一个回到起点的节点对，生成线性路径：
# 在生成result后添加 if len(result) >= 2: result = result[:-2] # 移除最后一步回到起点的节点对 print(result)
- 可选：指定固定起点和终点
若需固定起点S和终点E，可在输入阶段增加参数，并限制闭环路径：
# 添加起点终点输入 start = int(input("请输入起点编号：")) - 1 end = int(input("请输入终点编号：")) - 1 # 禁止从终点回到起点，避免闭环 matrix[end][start] = float('inf')
二、JavaScript代码修改（支持非闭合路径）
原JS代码的全排列逻辑本身已计算线性路径（无回到起点步骤），只需优化为指定固定起点和终点即可：
- 固定起点和终点
比如指定起点为1（索引0）、终点为8（索引7），修改循环条件：
// 固定起点为索引0 for (let i1 = 0; i1 <= 0; i1++) { // ...保留中间循环逻辑 // 固定终点为索引7 for (let i8 = 7; i8 <=7; i8++) { // 保留原节点不重复判断 if ( i1 != i2 && i1 != i3 && ... && i7 != i8 ) { // 原逻辑不变 } } }
- 通用化递归实现
将多层嵌套循环改为递归，适配任意数量节点的非闭合路径求解：
function findShortestPath(towns, startIdx, endIdx) { let path = []; let minPath = Infinity; let bestPath = ""; let n = towns.length; function permute(current, used) { if (current.length === n) { if (current[0] === startIdx && current[n-1] === endIdx) { let currentPath = current.map(i => i+1).join(" → "); let currentLength = 0; for (let i = 0; i < n-1; i++) { currentLength += towns[current[i]][current[i+1]]; } if (currentLength < minPath) { minPath = currentLength; bestPath = currentPath; } } return; } for (let i = 0; i < n; i++) { if (!used[i]) { used[i] = true; permute([...current, i], used); used[i] = false; } } } permute([], Array(n).fill(false)); return { path: bestPath, length: minPath }; } // 调用示例：起点1（索引0），终点8（索引7） let result = findShortestPath(towns, 0, 7); console.log(`Shortest Way: ${result.path} (${result.length} KM.)`);
内容的提问来源于stack exchange，提问作者Akira Frank
相关产品推荐
相关产品推荐
