Нижняя граница длины оптимального пути

Введение

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

Поясним это утверждение. Предположим, происходит перебор вариантов перемещения, при котором часть пути фиксирована и это не обязательно его начальный участок (существуют способы перебора, фиксирующие отдельные, до поры до времени не связанные между с собой различные куски всего пути коммивояжёра). Из такого частично построенного пути, далее получают возможные варианты его "продления". В процессе перебора известно лучшее (кратчайшее) к этому моменту решение с длиной minLen. Для каждого, частично построенного пути несложно вычислить его длину len1 (сумма длин рёбер попавших в куски пути). Если эта длина оказывается больше или равной minLen ≤ len1, то дальнейший перебор вариантов продления этого пути смысла не имеет (они заведомо окажутся длиннее). Такое "отсечение веток" перебора существенно сокращает пространство поиска.

Однако, использовать только длину накопленного пути не эффективно, так как в него должно попасть достаточно много городов, прежде чем выяснится дальнейшая бесперспективность перебора. Пусть мы можем вычислить нижнюю границу оставшегося пути, т.е. число, заведомо меньшее (или равное) длине оставшегося пути при его оптимальном формировании. Зная такое число len2, можно усилить условие отсечение: minLen ≥ len1 + len2. Если len2 максимально близко (снизу) к реальной длине оставшегося участка пути, то такая оценка окажется очень эффективным способом сокращения перебора.

Ниже рассмотрено два метода получения нижней оценки длины пути. Первый имеет наглядный геометрический смысл но применим только для евклидовой задачи коммивояжёра. Второй способ, основанный на анализе матрице расстояний Dij, более абстрактный, но "работает" и для асимметричной матрицы.

Геометрические соображения

Окружим каждый город (жёлтые круги) не пересекающимися окружностями, так как это сделано на рисунке голубым цветом:



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

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

Часто при построении окружностей происходит разделение городов на кластеры (группы). Внутри каждого кластера хотя-бы две окружности касаются друг друга, а между собой кластеры не имеют общих точек. Выше на рисунке получилось два таких кластера по три окружности в каждом. Для улучшения нижней оценки минимального пути, радиусы окружностей внутри данного кластера увеличивают на одинаковую величину, что приводит к появлению бордюра вокруг кластера (выше он изображён зелёным цветом). Размеры бордюров для каждого кластера делают максимальными, но так, чтобы они не пересекались друг с другом. Любой путь в задаче коммивояжёра должен зайти в каждый кластер и выйти из него (по меньшей мере один раз). Поэтому к нижней границе, полученной по сумме диаметров окружностей, можно добавить удвоенную ширину бордюра всех кластеров.

Линейное программирование

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

Обозначим через xi радиусы окружностей, где i=0,...,N-1 - номера городов и Dij = Dji - расстояния между ними. Чтобы оценка нижней границы пути была наибольшей, необходимо найти максимум суммы всех радиусов. При этом окружности не должны пересекаться, поэтому сумма радиусов двух городов не должна превышать расстояния между ними. Наконец, радиусы - это неотрицательные величины:

x0 + x1 + ... + xN-1 = max,     xi + xj ≤ Dij,    xi ≥ 0.

Поиск максимума линейной функции N переменных xi (первое соотношение) при наличии ограничений (следующие неравенства с i < j = 0, ..., N-1) и является предметом линейного программирования. Существуют достаточно эффективные способы решения этой задачи (например, симплекс метод). Ниже приведен результат для 50 городов (без построения бордюров):



Оценка по матрице

Перейдём теперь к менее наглядному способу вычисления нижней границы длины оптимального пути. Представим матрицу расстояний между восьмью городами в виде таблицы, не указывая конкретных значений (не заполняя клеточки). По вертикали находятся номера начальных городов, а по горизонтали - конечных (для каждого шага перемещения вдоль пути). Там где стоит прочерк - переход запрещён. Пометим звёздочками путь минимальной длины, который, для карты, приведенной ниже, равен 0,3,2,6,7,1,4,5. Для любого допустимого пути, из некого города можно перейти только в один город и попасть в него можно только из одного города. Поэтому в каждой строчке таблицы и в каждом столбике всегда стоит одна и только одна звёздочка. Сумма чисел (расстояний) "под" звёздочками равняется длине пути коммивояжёра.

0 1 2 3 4 5 6 7
0 - *
1 - *
2 - *
3 * -
4 - *
5 * -
6 - *
7 * -

Число под каждой звёздочкой неотрицательно и оно больше или равно минимальному значению всех чисел в строке, где стоит звёздочка. Поэтому суммарная длина пути должна быть не меньше суммы минимальных значений каждой строки, которое мы обозначим как Dsup_r. Если минимальные значения строк вычесть из всех расстояний в каждой строке, то получится новая матрица, а суммарная длина того-же пути уменьшится на Dsup_r. Теперь, рассуждая аналогично, можно вычесть минимальные значения в каждой колонке, сумма которых равна Dsup_c. Суммарная длина снова уменьшится на Dsup_c. Так как при поиске минимальных значений игнорируются прочерки, после всех этих действий длина пути останется неотрицательной. Поэтому нижняя граница длины пути равняется Dsup_r + Dsup_c.

Рассмотрим этот алгоритм на конкретной матрице расстояний, соответствующей карте городов приведенной выше (синим помечены ячейки через которые проходит оптимальный путь):

Минимальное значение первой строки (город 0) равно 42, во второй (город 1) равно 14 и т.д. Соответственно нижняя граница по строкам равна Dsup_r = 42 + 14 + 12 + 12 + 14 + 17 + 16 + 72 = 199. После вычитания минимумов из каждой строки, получается левая матрица, приведенная ниже. Справа от неё дан результат вычитания (уже из новой матрицы!) минимальных значений по колонкам: Dsup_c = 25 + 2 + 58 = 85:

Таким образом, длинна оптимального пути не превышает значения Dsup = Dsup_r + Dsup_c = + = . Аналогично можно сначала минимизировать колонки, а затем строчки:

Результат для нижней границы длины пути не поменяется: Dsup = Dsup_c + Dsup_r = + = , хотя финальная матрица будет выглядеть несколько иначе. Обратим внимание также на то, что после вычитания минимальных значений из каждой строки или столбца, матрица расстояний перестаёт быть симметричной и удовлетворять неравенству треугольника.

Оценка оставшейся длины пути

Пусть известно начало пути, например 0,3,2,6. Для оставшегося пути также можно найти нижнюю границу, включая возврат город 0. Для этого построим матрицу, у которой первая строчка соответствует последнему городу 6 (из которого куда-то можно ещё перейти), а первая колонка - городу 0 (куда в конце необходимо попасть). Остальные строчки и колонки связаны с ещё не посещёнными городами 1,4,5,7. Кроме этого, прочерком блокируем переход 6 → 0, который запрещён, так как путь пока не окончен:

0 1 4 5 7
6 - 67 81 84 74
1 51 - 14 20 72
4 57 14 - 17 76
5 42 20 17 - 91
7 119 72 76 91 -
0 1 4 5 7
6 - 0 14 17 7
1 37 - 0 6 58
4 43 0 - 3 62
5 25 3 0 - 74
7 47 0 4 19 -
0 1 4 5 7
6 - 0 14 14 0
1 12 - 0 3 51
4 18 0 - 0 55
5 0 3 0 - 67
7 18 0 4 16 -

Нижняя граница по строчкам равна Dsup_r = 67+14+14+17+72 = 184 (вторая таблица). По столбикам без нулей Dsup_c = 25+3+7 = 35. Соответственно, нижняя граница оставшегося пути равна Dsup = 184+35 = 219. Накопленная длина пути 0,3,2,6 равна D = 58+12+16 = 86. В этом примере нижняя граница пути является точной. Соответственно, сумма D + Dsup = 86 + 219 = 305 равна длине кратчайшего пути коммивояжёра. В общем случае, можно утверждать, что D + Dsup ≤ minLen.

Если при движении по некоторому пути, выясняется, что оценка нижней границы суммарной длины этого пути D + Dsup превышает минимальное значение minLen, найденное к этому моменту, то дальнейший анализ вариантов развития маршрута смысла не имеет. Коммивояжёр находится на неправильном пути :).

В классе Salesman оценка нижней границы длины оставшегося пути way в котором сделано n шагов, вычисляется в функции supDistance(way, n):

Сравнение методов

Ниже в таблице приведено значение длины кратчайшего пути коммивояжёра для различного числа городов N и его сравнение с нижней границей, полученной геометрическим методом Dcirc (рисование окружностей) и путём анализа матрицы Dmatr:

N 10 20 30 40 50
minLen 1442 2148 2450 2907 3112
Dcirc 1243 1801 2002 2551 2582
Dmatr 1117 1725 1934 2432 2389

Карта с городами имеет размеры 500 x 500 и seed=1. Видно, что во всех случаях геометрический метод построения окружностей (без бордюра!) оказывается лучше анализа матрицы расстояний. К тому же он заметно быстрее при оценке нижней границы оставшегося пути (естественно после однократного применения методов линейного программирования).