Главная

Быстрый

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

Карта

Скоростной алгоритм




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

Итак, перед нами граф, для которого мы должны найти оптимальный тур. О самом графе и текущем туре мы не знаем пока ничего: возможно, тур уже оптимальный (такие "чудеса" иногда встречаются - например, у графа pr2392 узлы заботливо заданы именно в такой последовательности, что, соединяя на старте рёбрами первый со вторым, второй с третьим, ... последний с первым мы как раз и получаем оптимальный тур). Возможно, погрешность составляет сотые доли процента (если, например, мы попытаемся улучшить best-known решение для графа w1904711), возможно - многие тысячи процентов (скажем, погрешность для того же w1904711 на старте составляет более 50000%) - алгоритму об этом ничего не известно. Поэтому он "предполагает худшее", и главная задача скоростного алгоритма - уронить бета-границу как можно быстрее и как можно ниже. При этом крайне желательно рассматривать не все рёбра графа (которых всё у того же w1904711 несколько триллионов), а лишь весьма небольшую их часть, но именно ту, которая позволить уменьшить бета-границу. Напомним, что о рёбрах у нас тоже нет никакой информации - они даже могут быть заданы таблично. Так есть ли хоть какие-то критерии для выбора "нужных" рёбер? Такие критерии есть!

На старте, при загрузке исходных данных, считаем длину текущего тура и, поделив её на число узлов графа, получаем среднюю длину ребра. Таким образом, каждое рассматриваемое ребро тура может быть меньше, больше, много больше этой самой текущей средней длины. Именно эта информация и управляет перебором: чем длиннее ребро, тем внимательнее оно рассматривается: при увеличении длины ребра на каждые 5% (реально у нас чуть больше - на 1/16) глубина рассмотрения (т.е. количество рёбер тура, начиная с текущего, с которыми проверяется возможность атомарных изменений тура) удваивается. Короткие же рёбра (у нас это рёбра средней длины и менее) рассматриваются лишь на минимальную глубину, которая определяется текущей итерацией (этап поиска решения каким-либо алгоритмом для всех рёбер тура), и вообще изначально задана нулевой. Фактически, это и есть разбиение исходного графа на подзадачи, но разбиение динамическое, по факту принадлежности элементов группы одному участку текущего тура.

Что это даёт? Очень многое! При таком подходе короткие рёбра на младших итерациях почти не рассматриваются, т.е. алгоритм не отвлекается на "мелочь", и смотрит лишь те варианты, которые могут дать серьёзное уменьшение бета-границы. С каждым найденным решением средняя длина ребра уменьшается, поэтому некоторые рёбра, считавшиеся ранее "короткими" переходят в разряд "длинных" и вовлекаются в перебор. Напротив, переход к следующей итерации никак не зависит от длины тура, и определяется отношением количества найденных за время итерации решений к числу узлов графа. Смысл очевиден: незачем "звать на помощь старших", пока дела идут хорошо. Более того, если отношение совсем уж велико (десятки процентов), значит, тур удалось хорошо "взлохматить", и есть смысл вернуть управление младшим (более скоростным) итерациям, поскольку вероятность их успешной работы весьма высока.

Вообще говоря, реально существующий скоростной алгоритм работает примерно в 10-100 раз быстрее, чем только что описанный, поскольку при поиске решения имеется множество технических нюансов. Перечислим важнейшие:

  • Львиную долю производительности обеспечивает так называемый "добор". После окончания каждой итерации, если при этом было найдено хотя бы одно решение, она повторяется, но только для новых рёбер, появившихся именно на этой итерации. Таких рёбер обычно совсем немного, но они ещё не рассматривались, и вероятность новых решений среди них довольно высока. В результате "добор" выполняется во много раз быстрее, а его эффективность нередко даже превышает эффективность основной итерации. Таким образом, каждая итерация снижает бета-границу приблизительно вдвое сильнее, и почти всё её снижение (90% и более) приходится на 2-3 самых младших итерации, что заметно ускоряет прохождение и всех остальных итераций. Программно "добор", разумеется, реализован в рамках одной итерации, которая заканчивается не после рассмотрения всех рёбер тура, а после того, как все они, включая вновь появившиеся, получат статус "рассмотрен".
  • Введено понятие "минимальной базовой глубины" (у нас она составляет 64 ребра) - это означает, что скоростной алгоритм не имеет права закончить работу даже при полной неудаче с поиском решений, пока все рёбра не будут рассмотрены на эту минимальную глубину. Такой подход практически гарантирует, что скоростной алгоритм не передаст следующему обработчику тур с погрешностью в сотни и тысячи процентов. Для графов с большими погрешностями стартового тура эта минимальная глубина может расти "естественным образом" (если итерациям будет удаваться находить достаточно много улучшений тура) - реально встречалось увеличение глубины до 1024 и даже 8192, но это уже для графов-"миллионников". В любом случае, даже такая глубина пренебрежимо мала по сравнению с количеством узлов графа, поэтому время работы скоростного алгоритма растёт практически линейно по числу узлов, что и подтверждает эксперимент.
  • Введено понятие "абсолютного ребра". Если для какого-либо ребра глубина расчёта составит половину узлов графа или более, ребро обсчитывается полностью, на всю глубину, и помечается как "абсолютное", которое уже не будет рассматриваться ни на одной их последующих итераций скоростного поиска. Для некоторых типов графов эта техника позволяет уменьшить время поиска решения в разы.
  • При сверхмалой глубине расчёта текущего ребра (до 16) смотрим только "разворот цепочки", далее подключается "передача узла ребру", а на глубине 64 (минимальная обязательная глубина) более "тяжёлые" атомарные алгоритмы. Это сокращает время работы скоростного алгоритма примерно вдвое.
  • При обработка "сверхдлинных" рёбер (с длиной, превышающей среднюю в 8 и более раз) решение на изменение тура принимается лишь при уменьшении длины именно этого ребра, причём не менее, чем на 1%. Это не только сокращает время поиска на данной итерации, минимизируя "мышиную возню" на длинных рёбрах, но и нередко заметно сбрасывает бета-границу, ускоряя, таким образом, и прохождение всех остальных итераций.

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

Эксперимент показал, что скоростной алгоритм (который рассматривает, как правило, далеко не все рёбра - иногда намного меньше 1%) даёт вполне удовлетворительные результаты, пригодные даже для практического применения. Бета-граница с любой величины (обычно это 3-5 тысяч процентов погрешности) падает до 10-20%, редко выше, часто ниже. Эффективность работы алгоритма для сверхбольших графов и вообще не с чем сравнивать: ни одна известная нам программа не в состоянии даже начать расчет уже при сотнях тысяч узлов (по крайней мере, на обычном PC). Иными словами, мы не считаем нужным далее улучшать скоростной алгоритм. В конце концов, есть возможность использовать любой понравившийся эвристический алгоритм, а его результат "скормить" нашему в качестве входных данных. Что мы и делали при расчете решения без округления, подставляя в качестве исходного "оптимальный" тур из TSPLIB. Даже в этом случае основная доля найденных решений приходится тоже на скоростной алгоритм.

Но мы ведь ищем точное решение! Поэтому "передаём эстафету" следующему обработчику, который будет рассматривать уже все рёбра графа.
Назад...   Далее...

18.08.2019 10:38
 
`