Главная

Средний

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

Карта

Просмотр всех рёбер




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

Погрешность туров после окончания работы алгоритма, который рассматривает все рёбра (мы называем его "средний") обычно уже укладывается в 5%. Но это, так сказать, "финальная" характеристика. А что за алгоритм такой? Напрашивающееся решение - повторить скоростной метод, рассматривая уже не только "окрестности" текущего узла, а все рёбра. Так и было вначале, но нам стало грустно смотреть, как, после великолепно отработавшего скоростного метода, сбросившего бета-границу в десятки, сотни, тысячи раз управление вдруг передаётся его унылому аналогу, работающему во много раз медленнее, и при этом почти не находящего новых решений - алгоритм ведь прежний! Переход же к замене по схеме 3-opt сразу после скоростного (то есть от линейной сложности прыгать сразу на кубическую, минуя квадратичную) и вообще смотрится "варварством". Тем не менее, именно этот механизм у нас и был реализован. Вернее, эффективность 3-opt мы сохранили, а сложность осталась квадратичной. Почему? Да всё из-за тех же "нюансов реализации". Рассказываю:

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

Работа "среднего" алгоритма каскадируется по таймеру (1 тик на ребро, 2, 4, 8 и т.д.), что позволяет основную массу решений выявлять на младших каскадах, не уходя "в глубокую задумчивость" в сложных случаях, однако основное приращение скорости работы алгоритма (в десятки раз!) дал категорический запрет на рассмотрение новых, обнаруженных в процессе поиска рёбер. Задачей "среднего" алгоритма более не является падение бета-границы, он должен лишь взломать текущий тур (одним или несколькими каскадами, чтобы набрать достаточное количество новых рёбер) и передать управление скоростному, который, напротив, теперь работает только по новым рёбрам и действительно роняет бета-границу весьма ощутимо (нередко больше самого "среднего"), являясь, таким образом, достойным ему напарником.

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

18.08.2019 10:38
 
`