Источник: http://www.inf.tsu.ru/Library/Publications/1999/Zhikharev_1999_1.pdf
Задача коммивояжера заключается в нахождении такого маршрута точек с заданными положительными расстояниями между ними, который дает минимальное суммарное расстояние.К задаче ком-
мивояжера сводится ряд задач, решаемых в геоинформационных системах, в
частности составление кратчайших транспортных маршрутов в дорожной сети.
Во многих случаях задача является метрической (когда выполняется неравенство треугольника для расстояний между всеми точками). В ряде случаев задача
не просто метрическая, а двумерная евклидова.
Ввиду NP-полноты задачи коммивояжера (даже двумерной евклидовой)
на практике при числе точек n > 100 используют приближенные алгоритмы ее
решения. Известны алгоритмы с временными оценками ( ) 2 O n и погрешностью
2 (максимальным отношением длин приближенного и оптимального маршрутов
в наихудшем случае). К ним относится алгоритм ближайшего города [1] и алго
ритм дерева [1,2]. Известен ряд алгоритмов, основанных на паросочетаниях с
временными оценками ( ) 3 O n . К ним относится алгоритм Кристофидеса [1,2] с
погрешностью 1,5 и алгоритм на основе решения задачи о назначениях [3].
Улучшение приближенных решений задачи коммивояжера возможно ме-
тодом локального поиска по окну, когда для всех i вдоль маршрута выбираются
наилучшие перестановки множеств из k точек с номерами i+1, i+2, ..., i+k. Ве
личина k – константа, поэтому общее время работы алгоритма возрастает на
линейную составляющую.
В статье рассматриваются различные варианты применения локального
поиска для приведенных выше и некоторых других приближенных алгоритмов.
Измерение качества получаемого решения ведется путем статистического мо-
делирования в двумерном евклидовом пространстве.
Алгоритм дерева содержит следующие этапы:
1) построение минимального остовного дерева T;
2) построение мультиграфа G путем удвоения ребер в T;
3) нахождение эйлерова цикла в G, а по циклу – вложенного в него мар-
шрута коммивояжера.
Здесь и далее будем считать, что n точек являются вершинами полного
графа, расстояния между точками суть длины ребер в этом графе.
Время работы алгоритма определяется первым этапом, так как время вы-
полнения этапов 2-3 является линейным. Алгоритм Прима [1] строит мини-
мальное остовное дерево на полном графе за ( ) 2 O n шагов. Для случая двумер-
ного евклидового пространства минимальное остовное дерево можно построить
алгоритмом Крускала по триангуляции Делоне за общее время O(n log n) [2]
или даже O(n) [4].
Рассмотрим две модификации алгоритма дерева, отличающиеся этапом 3
построения маршрута коммивояжера по минимальному остову.
Алгоритм в первой модификации выполняется следующим образом. Пер-
воначально в маршрут включается одна (любая) вершина. Затем добавляется
вершина, имеющая общее ребро с первой, причем это ребро удваивается, в ре-
зультате чего получается замкнутый маршрут. Далее на каждом шаге в мар-
шрут добавляется по одной новой вершине, соединенной ребром с какой-либо
вершиной маршрута. При этом новая вершина включается в маршрут либо до,
либо после этой вершины маршрута, вариант включения выбирается по мини-
муму приращения общей длины маршрута, как это показано на рис. 1. Время
выполнения этапа 3 в данной модификации алгоритма остается линейным.
Вторая модификация алгоритма дерева состоит в том, что на очередном
шаге из ранее не вошедших в маршрут вершин включается та, которая соеди-
нена самым коротким ребром дерева с одной из вершин маршрута. При этом
будет строиться в точности маршрут ближайшего города.
Для двумерного евклидового пространства этап построения маршрута по
минимальному остову во второй модификации алгоритма можно выполнить за
время O(n log n) . Для этого из ребер, соединяющих вершины маршрута и
смежные с ними вершины вне маршрута, необходимо сформировать пирамиду с кратчайшим ребром наверху. Пирамида строится так же, как в пирамидальной
сортировке Уильямса [5]. Тогда каждое исключение ребра из вершины пирами-
ды и каждое включение нового ребра в пирамиду можно выполнить за время
O(n log n) . Таким образом, справедлива следующая теорема.
Алгоритм Кристофидеса содержит следующие этапы:
1) построение минимального остовного дерева T;
2) построение минимального взвешенного паросочетания P на вершинах
дерева T с нечетной степенью;
3) нахождение эйлерова цикла в графе G =T P , а по циклу – вложен-
ного в него маршрута коммивояжера.
Время работы этого алгоритма определяется вторым этапом. Алгоритм
Габова [1] строит требуемое паросочетание за время ( ) 3 O n . В случае двумерно-
го евклидового пространства минимальное взвешенное паросочетание можно
построить алгоритмом Вайды за время O(n2,5 log4 n) [6]. (Заметим, что в прак-
тических случаях, когда n < 109 , такой алгоритм не дает никаких преиму-
ществ!)
Общий эйлеров цикл в графе G можно представить совокупностью от-
дельных циклов из неповторяющихся вершин, которые соприкасаются друг с
другом в некоторых общих точках. Первая модификация алгоритма Кристофи-
деса состоит в том, что вначале из графа G выбираются те циклы, которыеимеют общие точки, а затем производится их объединение. Как показано на
рис. 2, возможно 4 варианта объединения циклов с одной общей точкой, при
этом в двух случаях приходится «разворачивать» один из циклов. В случае, ко-
гда два цикла имеют более одной общей точки, в одном из циклов удаляются
все общие точки, кроме первой, и выполняется то же объединение, что и на рис.
2. Удаление точек из цикла осуществляется посредством их «пропуска», т.е. пу-
тём замены двух ребер, смежных по удаляемой точке на одно, соединяющее
концы этих двух ребер.
Вторая модификация алгоритма использует другой способ объединения
двух циклов с несколькими общими точками. Рассматривается несколько вари-
антов объединения, окончательно из них выбирается тот, который дает мини-
мальный прирост общей длины маршрута. Любой вариант объединения выпол-
няется путем разрыва циклов в каждой из общих точек. Производится он так,
что вначале фиксируется одна из их общих точек. Разрыв в ней выбирается из
четырех вариантов, подобных изображенным на рис. 2. Во всех остальных об-
щих точках разрыв выбирается из двух вариантов, что объясняется тем, что вы-
бранный способ разрыва в фиксированной точке ограничивает выбор способа
разрыва в остальных общих точках. Так как в качестве фиксированной пробу-
ются все k общих точек, то будем иметь k вариантов объединения циклов. На
рис. 3 показан случай объединения циклов 1 L и 2 L с двумя общими точками.
Время этапа 3 в модификации 1 с таким улучшением остается линейным.
Практическая проверка алгоритмов проводилась на случайных точках,
независимо равномерно распределенных в единичном квадрате. В табл. 1 при-
ведены относительные длины маршрутов, нормированные на n . При модели-
ровании генерировалось такое количество наборов случайных точек, которое
было достаточно для вычисления статистических оценок с погрешностью менее
0,01 при доверительной вероятности 0,95. При этом все алгоритмы обрабатыва-
ли одни и те же наборы случайных точек. В качестве оценки снизу оптимально-
го маршрута вычислялась величина, равная сумме длин минимального остова и
удвоенного максимального ребра.
Результаты моделирования показывают существенное влияние локально-
го поиска (как по внутреннему, так и по внешнему окну) на качество маршрута.
Далее будем рассматривать только окно размером 11, так как оно дает наилуч
шие результаты. В случае умолчания о виде окна в локальном поиске считает
ся, что данные как по внутреннему, так и по внешнему окну почти одинаковы.
Для алгоритма дерева и его модификаций при использовании окна разме
ром 11 время вычислений возрастает в несколько десятков раз по сравнению с
соответствующим алгоритмом без локального поиска при улучшении качества
решения примерно на 15-20%. Дальнейшее увеличение размера окна резко
снижает соотношение «выигрыш в длине маршрута» – «время вычисления» и
имеет смысл лишь в случаях предъявления повышенных требований к качеству
маршрута. При этом внутреннее окно оказывает большее влияние, чем внеш
нее. Этот выигрыш составляет порядка 3%. Применение локального поиска од-
94 С. А. Жихарев,Ю. Л. Костюк
новременно по внутреннему и внешнему окну к модифицированному алгорит-
му дерева дает дополнительный выигрыш примерно в 2%, но тем не менее даже
в этом случае остается разница в 2-3% с классическим алгоритмом Кристофи-
деса, к которому применено внешнее окно.
У алгоритма Кристофидеса «модифицированный-1» выигрыш по длине
маршрута в результате применения локального поиска меньше, чем в алгорит-
мах дерева (здесь он составляет 5-10%) при том же увеличении времени. Хотя
поиск по внутреннему окну здесь даёт меньший эффект, чем поиск по внешне-
му окну, но, будучи примененным одновременно с внешним окном, такой по-
иск дает дополнительный выигрыш в 0,5-1,5%.