Вопрос или проблема
Я пытаюсь использовать traveling_salesman_problem из NetworkX, чтобы найти кратчайший путь между узлами, но кажется, что он возвращает более длинный путь, чем необходимо. Вот минимальный пример:
import shapely
import networkx as nx
import matplotlib.pyplot as plt
# Создание сетки 10x10
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])
# Превращение в граф
graph = nx.Graph()
graph.add_edges_from([(*line.coords, {"distance": line.length}) for line in grid.geoms])
# Выбор узлов и их посещение с помощью TSP и вручную
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)])
# Построение результатов
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={tsp_path.length}")
axes[1].plot(*manual_path.xy, c="r")
axes[1].set_title(f"длина вручную={manual_path.length}")
Что я упускаю? Является ли TSP неправильным алгоритмом для этого?
Редактировать, чтобы вернуться к началу:
Если я запущу traveling_salesman_problem с 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 и (более короткий) справа для моего ручного маршрута:
Ответ или решение
Когда речь заходит о решении задачи коммивояжера (TSP) с использованием библиотеки NetworkX, существует ряд факторов, которые могут привести к неоднозначностям и, как следствие, к тому, что алгоритм не возвращает самую короткую траекторию. Давайте подробно рассмотрим возможные причины, которые могут влиять на результат.
1. Природа задачи коммивояжера
Задача коммивояжера заключается в нахождении кратчайшего возможного маршрута, который проходит через заданные набор узлов (или точек) и возвращается в исходную точку. Однако многие методики для её решения, включая метод, использованный в вашей реализации (алгоритм Христофидеса), являются эвристическими и не всегда гарантируют нахождение оптимального решения. Эти методы часто стремятся найти "достаточно хорошее" решение за разумное время, что может привести к тому, что результат будет длиннее, чем идеальный маршрут.
2. Структура графа
Ваша реализация использует неориентированный граф, созданный на основе сетки, с длиной сторон, заданной параметром "distance". Важно отметить, что сложная структура графа, состоящая из множественных пересечений и длинных отрезков, может повлиять на выбор маршрута. Так как ваши узлы не размещены на равномерном сетчатом поле, TSP может игнорировать более короткие связи между узлами, находя более длинные пути, которые учитывают только доступные рёбра.
3. Выбор узлов
Вы также отметили, что узлы, которые вам необходимо посетить, представляют собой произвольные точки на графе. Алгоритм TSP находит кратчайший путь, но конечное решение зависит от порядка выбора этих узлов. Ошибки в выборе порядка могут привести к менее оптимальным маршрутам.
4. Параметры алгоритма
В предложенном вами коде параметр cycle установлен в False, и, следовательно, алгоритм не накладывает обязательство возвращаться к начальной точке. При установке этого параметра в True алгоритм должен более эффективно находить маршрут, так как теперь TSP ищет путь, возвращающийся к исходной точке. Однако это также может не гарантировать наименьшую длину, так как каждый вызов алгоритма может возвращать разное решение.
5. Ваш ручной маршрут
Нельзя не упомянуть, что ручной маршрут, который вы предоставили, также может быть оптимизирован. Если вы вручную соединяете узлы в порядке, который вам кажется более логичным или коротким, это может не отражать реального расстояния, сопротивления или сложности перемещения между точками в графе. Учитывайте, что ручное определение маршрута не исключает возможности человеческой ошибки или недоразумений, связанных с визуальной интерпретацией графа.
Заключение
Важным шагом в оптимизации и в поиске действительно кратчайшего маршрута является тщательный анализ структуры графа, выбор узлов и конфигурация алгоритма. Рекомендуется протестировать различные подходы и методы, включая изменение порядка узлов, применение других эвристических, метаэвристических алгоритмов (таких как генетические алгоритмы), а также использование точных методов (например, метод ветвей и границ), если размер задачи позволяет это.
Таким образом, если у вас есть цель сократить длину маршрута, стоит рассмотреть более комплексный подход или использовать дополнительные инструменты для анализа и визуализации графа, чтобы получить более точные результаты.