为何NetworkX的traveling_salesman_problem未返回最短路径？

我尝试使用NetworkX的traveling_salesman_problem寻找节点间的最短路径，但返回的路径长度却大于手动规划的路径。以下是最小复现示例：

import shapely
import networkx as nx
import matplotlib.pyplot as plt

# Make a 10x10 grid

vert = shapely.geometry.MultiLineString([[(x, 0), (x, 100)] for x in range(0, 110, 10)])
hori = shapely.affinity.rotate(vert, 90)
grid = shapely.unary_union([vert, hori])

# Turn it into a graph

graph = nx.Graph()
graph.add_edges_from([(*line.coords, {"distance": line.length}) for line in grid.geoms])

# Select nodes and visit them via TSP and manually

nodes = [(20., 20.), (30., 30.), (20., 80.), (80., 20.), (50., 50.), (60., 10.), (40., 40.), (50., 40.), (50, 30)]

tsp_path = nx.approximation.traveling_salesman_problem(
    graph,
    weight="distance",
    nodes=nodes,
    cycle=False,
    method=nx.approximation.christofides
)

tsp_path = shapely.geometry.LineString(tsp_path)

manual_path = shapely.geometry.LineString([(20, 80), (50, 80), (50, 30), (40, 30), (40, 40), (40, 30), (20, 30), (20, 20), (60, 20), (60, 10), (60, 20), (80, 20)])

# Plot results

fig, axes = plt.subplots(1, 2, figsize=(10, 5), sharey=True)

for ax in axes:
    for line in grid.geoms:
        ax.plot(*line.xy, c="k", lw=.25)
    ax.scatter(*zip(*nodes), c="k")
    ax.set_aspect("equal")
axes[0].plot(*tsp_path.xy, c="b")
axes[0].set_title(f"TSP solution length={tsp_path.length}")
axes[1].plot(*manual_path.xy, c="r")
axes[1].set_title(f"manual length={manual_path.length}")

我遗漏了什么？TSP是解决此问题的错误算法吗？

返回起点的补充测试：
当我设置cycle=True让路径返回起点，并修改手动路径为：

manual_path = shapely.geometry.LineString([(20, 80), (50, 80), (50, 30), (40, 30), (40, 40), (40, 30), (20, 30), (20, 20), (60, 20), (60, 10), (60, 20), (80, 20), (80, 80), (20, 80)])

NetworkX返回的路径仍长于手动规划路径。

1. TSP的核心约束被忽略了 #

旅行商问题（TSP）的核心要求是：必须访问每个目标节点，且每个节点只能被访问一次（仅cycle=True时允许起点与终点重合）。但你的手动路径明显违反了这个规则——比如重复访问了(40,30)、(60,20)这些节点，通过绕路重复节点来“缩短”总长度，这已经不是TSP要解决的问题了。

NetworkX的traveling_salesman_problem严格遵循TSP约束，返回的路径会确保每个指定节点仅被访问一次，所以两者的路径没有可比性。

2. 算法场景匹配错误 #

如果你的需求是允许重复访问非目标节点，甚至重复访问目标节点来获取更短的总路径，那你需要的不是TSP，而是中国邮递员问题（CPP），或者基于最短路径的多节点路径规划（比如先计算所有目标节点间的最短路径，再组合成最优路径）。

3. 正确使用TSP的方式 #

如果你确实需要用TSP解决“访问所有目标节点各一次的最短路径”，正确步骤如下：

• 第一步：计算所有目标节点之间在网格图中的最短路径长度，构建一个以目标节点为顶点的完全图，边权为对应节点间的最短路径长度。
• 第二步：在这个完全图上运行TSP算法，得到目标节点的最优访问顺序。
• 第三步：把这个顺序对应的原图最短路径拼接起来，得到最终完整路径。

示例代码片段：

# 计算目标节点间的最短路径矩阵
dist_matrix = {}
for u in nodes:
    dist_matrix[u] = {}
    for v in nodes:
        if u != v:
            dist_matrix[u][v] = nx.shortest_path_length(graph, source=u, target=v, weight="distance")
        else:
            dist_matrix[u][v] = 0

# 构建完全图
complete_graph = nx.Graph()
for u in nodes:
    for v in nodes:
        if u < v:  # 避免重复添加边
            complete_graph.add_edge(u, v, weight=dist_matrix[u][v])

# 运行TSP
tsp_order = nx.approximation.traveling_salesman_problem(complete_graph, weight="weight", cycle=False)

# 拼接原图中的最短路径
final_path = []
for i in range(len(tsp_order)-1):
    path_segment = nx.shortest_path(graph, tsp_order[i], tsp_order[i+1], weight="distance")
    final_path.extend(path_segment[:-1])  # 避免重复添加节点
final_path.append(tsp_order[-1])

final_path_line = shapely.geometry.LineString(final_path)
print(f"优化后的TSP路径长度：{final_path_line.length}")

总结 #

你的手动路径不符合TSP的约束条件，不能用来和TSP结果对比。如果需求是允许重复访问节点，TSP确实不是合适的算法；如果需要严格访问每个目标节点一次，应该先构建目标节点的最短路径完全图，再运行TSP。

内容的提问来源于stack exchange，提问作者user2950747