Почему TSP в NetworkX не возвращает кратчайший путь? ⇐ Python

[Anonymous]

Я пытаюсь использовать Travel_salesman_problem NetworkX, чтобы найти кратчайший путь между узлами, но, похоже, он возвращает более длинный путь, чем необходимо. Вот минимальный пример:

Код: Выделить всё

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 неправильным алгоритмом для этого?


Изменить, чтобы вернуться к исходной точке:
Если я запустил travel_salesman_problem с помощью цикла =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 и (более короткий) внизу справа для моего ручного маршрута:



Подробнее здесь: https://stackoverflow.com/questions/791 ... rtest-path