Спиридонова Н. А.

Одесский национальный политехнический университет

Сравнительный анализ различных алгоритмов

решения задачи о коммивояжере.

Большое количество практических задач можно сформулировать и решить как сетевые модели. Недавние исследования показывают, что не менее 70% реальных задач математического программирования можно представить в виде сетевых моделей [1]. В том числе часто решение реальной задачи сводится к решению задачи коммивояжера.

Приведем несколько конкретных примеров:

- проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода;

- поиск кратчайшего маршрута между двумя городами по существующей сети дорог;

- определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.

Существует множество подходов к решению задачи о коммивояжере. Наиболее распространенным методом решения задачи коммивояжера является алгоритм Литтла [1]. Он относится к числу точных алгоритмов, однако при решении задач коммивояжера большой размерности, когда разброс данных невелик (т.е. расстояния между городами отличаются, но не намного) этот алгоритм сходится, но очень медленно.

Постановка задачи коммивояжера заключается в следующем: имеются n городов, расстояния (стоимость проезда, расход горючего на дорогу и т.д.) между которыми известны. Коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, из которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние (стоимость проезда и т.д.) будет минимальным.

Пусть рассматривается задача коммивояжера в формальной постановке:

(1)

(2)

(3)

(4)

v (5)

(6)

где n – размерность задачи, – элементы матрицы расстояний.

Основным методом решения задачи о коммивояжере является метод ветвей и границ. Данный метод опирается на следующие построения:

- вычисление верхней границы значений целевой функции, либо на множестве, либо на некотором его подмножестве (оценивание);

- постепенное разбиение множества на подмножества (ветвления);

- пересчет оценок при постепенном разбиении множеств;

- нахождение конкретных вариантов решения;

- проверка вариантов на оптимальность.

Одной из модификаций метода ветвей и границ является алгоритм Литтла, позволяющий найти точное решение задачи коммивояжера.

Сформированный в методе Литтла признак оптимальности является довольно слабым, и при решении задачи уходит много времени на доказательство оптимальности давно полученного оптимального решения [2].

Для качественного ускорения получения решения задачи коммивояжера было рассмотрен ряд методов, и выбран наиболее подходящий – метод Дейкстры [3]. В классическом варианте данный алгоритм используется для поиска кратчайшего пути между заданным исходным узлом и любым другим узлом сети. Для его применения при решении задачи коммивояжера необходимо произвести выбор двух узлов таким образом, чтобы кратчайший путь между ними, во-первых, включал все имеющиеся узлы, во-вторых, являлся оптимальным. Но в отличие от метода Литтла, этот алгоритм относится к приближенным. В данном случае проведены исследования и разработана модификация алгоритма Дейкстры для получения более точного решения.

В процессе выполнения этого алгоритма при переходе от узла к следующему узлу используется специальная процедура пометки ребер. Обозначается через кратчайшее расстояние от исходного узла до узла , – длина ребра . Тогда для узла определяется метка следующим образом: , .

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

Вычислительная схема алгоритма Дейкстры состоит из следующих этапов:

– исходному узлу присваивается постоянная метка . Полагаем .

– вычисляются временные метки для всех узлов , которые можно достичь непосредственно из узла и которые не имеют постоянных меток. Если узел уже имеет метку , полученную от другого узла , и, если , тогда метка заменяется на .

– если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка с наименьшим значением расстояния среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем и повторяем этап .

Модификация алгоритма заключается в том, что на начальном этапе выбираются и запоминаются, так называемые, первые минимальные начальные отправные точки (номера узлов, имеющих кратчайшие расстояния) и вторые начальные отправные точки (номера узлов, расстояние до которых следующее по величине относительно первого минимума). Именно из выбранных узлов ведется дальнейший поиск кратчайших расстояний в сети – применяется алгоритм Дейкстры. Затем полученные в результате работы алгоритма расстояния сравниваются между собой и выбирается минимальное, являющееся оптимальным. После этого восстанавливается порядок посещения узлов, который и является оптимальным маршрутом.

Эффективность алгоритмов Дейкстры и Литтла исследовались экспериментальным путем. Разработан программный продукт, который реализован на персональном компьютере.

При проведении экспериментальных исследований для каждой размерности задачи было сгенерировано 25 задач, максимальная размерность решенной задачи 5050. В результате проведенных исследований выяснилось, что модифицированный метод Дейкстры примерно в 2-3% случаев из исследованных, не дает оптимального решения, но одну и ту же задачу решает быстрее, чем алгоритм Литтла. Результаты проведенного эксперимента приведены в таблице 1.

Таблица 1. Экспериментальные данные скорости сходимости точного и приближенного алгоритмов решения задачи коммивояжера.

Размерность задачи, n×n	Алгоритм Литтла		Модифицированный алгоритм Дейкстры
	Время сходимости, с	Число итераций	Время сходимости, с	Число итераций
3×3	0,08	2	0,00	1
5×5	0,11	4	0,05	2
10×10	0,71	10	0,29	7
15×15	1,93	20	0,62	10
20×20	2,62	25	0,97	14
25×25	3,47	31	1,50	16
30×30	4,24	37	1,93	19
35×35	5,10	43	2,30	23
40×40	6,33	49	2,67	25
45×45	7,16	55	3,28	29
50×50	7,95	62	4,00	33

Исходя из полученных результатов, приходим к выводу о том, что скорость сходимости разработанного алгоритма выше (примерно в 2,5 раза), что особенно заметно для задач большой размерности.

Литература

1. Хемди А. Таха Введение в исследование операций, 7-е издание. С.-Петербург: Вильямс, 2005. – 901 с.

2. Ф. А. Новиков Дискретная математика для программистов. С.-Петербург: Питер, 2002. – 304 с.

3. Р. Сэджвик Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер. с англ./ Р. Сэджвик. – С.-Петербург: ДиаСофт ЮП, 2002. – 496 с.