Главная

Алгоритм

Главная
Комми
Алгоритм
Быстрый
Средний
Точный
Эксперимент

Карта

Есть такая партия!




Назад...   Далее...

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

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

Собственно, уже сказанного вполне достаточно, чтобы понять, что наш подход очень напоминает классический Lin-Kernighan-Johnson метод, как и его разновидность LKH, которая вот уже много лет подряд находит чуть ли не все best-known решения. Однако есть важнейшее отличие: мы используем его для поиска не только приближённого, но и точного решения. Весь инструментарий для этого уже имеется, осталось только выбросить "мутации" и все остальные "ideas from tabu search and evolutionary computing", заменив их (хотя бы) каскадной рекурсией. Ведь любая ускоряющая эвристика на этом этапе лишь переводит задачу из разряда точных в приближённые! Оно нам надо?

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

Атомарные алгоритмы

Алгоритм минимально возможной модификации тура путем замены двух рёбер (2-opt) известен, видимо, очень давно - чуть ли не со времени постановки задачи. Википедия приписывает авторство Lin & Kernighan, но верится в это с трудом: мы придумали его самостоятельно (у нас он называется "разворот цепочки"), и это буквально первое, что приходит в голову. Алгоритм элементарен: из текущего тура удаляются два ребра, затем две полученные цепочки вновь соединяются в тур противоположными концами (рис. 1), но очень эффективен - это главная "рабочая лошадка" при скоростной модификации тура - именно на него падает основная доля падения бета-границы: до 90% и более.


Рис. 1

Передача узла ребру (3-opt): из текущего тура удаляются два ребра, принадлежащие одному узлу. Ответные части (узлы, на которые указывали отброшенные рёбра) соединяются ребром. После чего одно из оставшихся рёбер тура удаляется, а соединенные им ранее узлы соединяются новыми рёбрами с исследуемым узлом. При уменьшении длины тура предыдущее решение заменяется найденным вариантом (рис. 2).


Рис. 2

Передача цепочки ребру: модификация предыдущего алгоритма, но ребру передается не отдельный узел, а произвольная цепочка узлов тура (рис 3).


Рис. 3

Есть ещё один алгоритм, который имеет замечательное "официальное" название - "двойной мост". Алгоритм изменяет сразу 4 ребра тура (4-opt), что позволяет перейти по этому "мосту" в другой (в т.ч. несмежный) контур обхода. Суть: как и в предыдущем алгоритме, из тура удаляются два ребра, а полученные цепочки соединяются в два "кольца". Затем у каждого из этих "полутуров" удаляется ещё по одному ребру, и получившиеся цепочки вновь связываются в тур (рис 4).


Рис. 4

Алгоритм, изменяющий 3 ребра тура, считается "наиболее популярным из k-opt методов". На самом деле он вообще не нужен: это либо два "разворота" с общим ребром, либо кастрированный "мост", когда одно из новых рёбер тут же и удаляется. Частный случай этого алгоритма (когда два ребра смежны) используется у нас совместно с "разворотом" при скоростном поиске, да и то лишь потому, что практически не требует накладных расходов. Не нужны, кстати, и все остальные k-opt методы, поскольку эти два алгоритма уже обеспечивают возможность "атомарного" искажения текущего тура без нарушения его целостности путем замены 2, 3 или 4 рёбер и, следовательно, возможность замены любого числа рёбер путем рекурсии. Строго говоря, достаточно и одного "моста" (если удалить одно новое ребро, получится "передача узла", если два - "разворот"), беда лишь в том, что "мост" - удовольствие дорогое (не говоря уже о рекурсии), поэтому везде, где это возможно, выгоднее использовать "чистый" разворот. В реальной рабочей программе мы используем все вышеперечисленные алгоритмы... кроме "моста"! Его время придёт много позже, во время финальной процедуры падения бета-границы, наряду с ещё более сложными алгоритмами, требующими одновременной замены большего числа рёбер.

Для детальной проверки всех концепций нашего подхода мы проведём масштабный эксперимент: решим заново все известные задачи, решённые и не решённые на данный момент. Кроме того, поскольку все известные задачи "неприлично малы" (кроме разве что World TSP на 1904711 узлов), мы дополним список задач собственными графами, образованные генератором узлов со случайными координатами, а также "синтетическими", образованными из известных задач, например: pla_all - все графы серии "pla" (127107 узлов), tsplib - все графы, представленные в TSPLIB (238698 узлов), pict_all - все графы серии "Art TSP" (899159 узлов) и т.д. Кроме того, сюда включены все графы из DIMACS TSP Challenge. В итоге получился набор из 395 задач коммивояжёра для графов от 3 до 123456789 узлов. Детальные результаты экспериментов приведены в сводной таблице, там же дана интегральная статистика по группам графов разной размерности.
Назад...   Далее...

18.08.2019 10:38
 
`