Задача коммивояжера.

Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — странствующий торговец) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), метрическая задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

Непременным условием и единственным смыслом задачи коммивояжёра является поиск самого выгодного пути. Для этого необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения. Если мы не просчитали все пути в выбранном варианте решения, то мы не можем утверждать, что найденное решение самое выгодное. Что такое проверка решения? — это поиск ошибки в процессе решения или сверка полученного результата с заведомо правильным. Второй вариант временно отбрасываем, так как нет практического смысла в решении задачи, если уже есть решение (в свою очередь, использование ранее выполненного верного решения для части имеющейся задачи — способ уменьшить решение). В рамках данной работы не ставилось целью сравнение различных методов и способов решения, поэтому принимаем, что проверяющий также считает выбранный способ решения оптимальным и проверяет его на правильность. Что нужно сделать проверяющему? — повторить работу, проделанную при решении, в полном объёме для поиска ошибки на каждом этапе решения. Если будет найдена ошибка, то проверяющему будет необходимо продолжить процесс решения для поиска более выгодного маршрута. Таким образом, мы получаем, что проверка решения задачи коммивояжёра равна или больше самого решения.

Представление в виде графа.

Рис. 3.2

Симметричная задача для четырёх городов.

Для возможности применения математического аппарата для решения проблемы, её следует представить в виде математической модели. Проблему коммивояжёра можно представить в виде модели на графе, то есть, используя вершины и ребра между ними. Таким образом, вершины графа соответствуют городам, а ребра (i, j) между вершинами i и j — пути сообщения между этими городами. Каждому ребру (i, j)>=0 можно сопоставить критерий выгодности маршрута, который можно понимать как, например, расстояние между городами, время или стоимость поездки. Маршрутом (также гамильтоновым маршрутом) называется маршрут на таком графе, в который входит по одному разу каждая вершина графа. Задача заключается в отыскании кратчайшего маршрута.

В целях упрощения задачи и гарантии существования маршрута, обычно считается, что модельный граф задачи является полностью связным, то есть, что между произвольной парой вершин существует ребро. В тех случаях, когда между отдельными городами не существует сообщения, этого можно достичь путем ввода рёбер с максимальной длиной. Из-за большой длины такое ребро никогда не попадет к оптимальному маршруту, если он существует.

В зависимости от того, какой критерий выгодности маршрута сопоставляется величине ребер, различают различные варианты задачи, важнейшими из которых являются симметричная и метрическая задачи.

Пример решения задачи коммивояжера на языке python на заданном графе (Рис. 3.2).

В листинге 2 приводится скрипт для решения данной задачи.

Данный скрипт находит самый «выгодный» путь от вершины 1 до вершины 4.

Рис. 3.2

Листинг 2.

import networkx as nx

import matplotlib.pyplot as plt

import numpy

G = nx.Graph();

for i in range(1,6):

G.add_node(i)

G.add_edge(1, 2, node_color = 'm', weight = 2) # Параметр weight задает вес ребра

G.add_edge(1, 3, node_color = 'm', weight = 1)

G.add_edge(1, 4, node_color = 'm', weight = 20)

G.add_edge(1, 5, node_color = 'm', weight = 10)

G.add_edge(1, 6, node_color = 'm', weight = 15)

G.add_edge(5, 4, node_color = 'm', weight = 1)

G.add_edge(1, 6, node_color = 'm', weight = 10)

G.add_edge(6, 1, node_color = 'm', weight = 4)

G.add_edge(2, 3, node_color = 'm', weight = 10)

G.add_edge(2, 5, node_color = 'm', weight = 5)

G.add_edge(2, 6, node_color = 'm', weight = 20)

G.add_edge(3, 6, node_color = 'm', weight = 6)

G.add_edge(4, 2, node_color = 'm', weight = 15)

G.add_edge(4, 3, node_color = 'm', weight = 40)

G.add_edge(5, 6, node_color = 'm', weight = 10)

G.add_edge(3, 5, node_color = 'm', weight = 3)

nx.draw(G) #Отрисовка графа

plt.show()

adjacency_matrix = nx.adjacency_matrix(G)

print('Матрица стоимости')

print(adjacency_matrix) #Вывод матрицы весов

print(nx.shortest_path(G, 1, 4)) #Вывод самого короткого пути

print(nx.dijkstra_path(G, 1, 4)) #Вывод самого "выгодного" пути

Выходные данные:

[1,4] – Кратчайший путь

[1,3,5,4] – Выгодный путь