Главная

Точный

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

Карта

Поиск точного решения




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

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

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

Вначале немного определений:

  • Мультиузел: инкапсулированная группа узлов.
  • Мультиребро: инкапсулированная группа рёбер. Мы употребляем также термины пучок или канал, при этом рёбра между узлами одного мультиузла образуют внутренний канал, остальные - внешний, пучок рёбер между двумя мультиузлами образует межгрупповой канал. Как правило, под мультиребром понимается именно межгрупповой канал.

Понятие "мультиузел" очень гибкое: это может быть и отдельный узел, и субграф, и весь граф в целом. То есть общее количество мультиузлов, их размер и степень вложенности могут сильно различаться для разных графов или для одного графа в разные моменты времени. Единственный разумный критерий этого количества - удобство обработки: их должно быть столько, сколько нам нужно в данный момент. Так, в начале работы точного алгоритма мы считаем каждый узел графа отдельным мультиузлом, а дальнейшая их конфигурация будет определяться слиянием соседних по туру мультиузлов.

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

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

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

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

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

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

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

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

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

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


Рис. 5

  1. Оба новых ребра подходят к тем же узлам, что и старые рёбра привязки (концевым узлам цепочек). Искажения тура не требуется, сборка нового тура завершена.
  2. Новые рёбра подходят к смежным по туру узлам цепочки. Соединяющее их ребро удаляется, а концевые узлы цепочки соединяются ребром. Одно ребро искажения тура, сборка нового тура завершена.
  3. Новые рёбра подходят к одному и тому же узлу цепочки. Если исследуемый мультиузел состоит более, чем из одного узла (иначе это вариант 1), сборка нового тура невозможна.
  4. Одно из новых рёбер подходит к концевому узлу цепочки, а второе - к внутреннему её узлу (несмежному с первым - это вариант 2). Одно из рёбер внутреннего тура этого узла (которое идёт на цепочку, ведущую к первому узлу) удаляется, а второй узел этого ребра соединяется с концевым узлом второй цепочки. Одно ребро искажения тура, сборка нового тура завершена.
  5. Новые рёбра подходят к несмежным по туру внутренним узлам цепочки. У каждого из этих узлов удаляется по ребру, ведущему на их общую цепочку, а сама эта цепочка соединяется ребрами с концевыми узлами старых рёбер привязки. Два ребра искажения тура, сборка нового тура завершена.

Иногда (не так уж и редко!) пересобранный тур сразу имеет меньшую длину, чем текущий. В этом случае точный алгоритм немедленно прерывает свою работу (тот самый "несчастный случай"), новые рёбра тура приглаживаются скоростным, и процесс повторяется. Но в большинстве случаев рёбра искажения тура уводят его длину за бета-границу. Это ещё не означает, что выбор рёбер-кандидатов неудачен - ведь полученный тур, возможно, удастся пригладить, оставив его длину ниже бета-границы. Что и делается - полным перебором всех возможных вариантов (каскадной рекурсией). Здесь мы приходим в самую опасную точку нашего алгоритма с точки зрения его полиномиальности - ведь рекурсивный алгоритм экспоненциален! Но это "в теории". Реально же мы работаем по альфе даже не всего графа, а только привязываемого мультиузла, и диапазон этот ничтожен! В результате наша "экспонента" почти всегда затухает естественным образом на первом же ребре, и лишь в редких случаях (обычно это происходит на графах, у которых имеется множество рёбер одинаковой длины - например, г2319 или pla85900) поиск уходит достаточно глубоко. Однако даже в этих случаях дерево перебора получается, хотя и большим, но чрезвычайно узким (коэффициент ветвления почти никогда не превосходит 1.5), и потому даже варианты улучшения текущего тура с одновременной заменой 10, 20 и более рёбер находятся буквально за секунды, что мы неднократно наблюдали в своих экспериментах.

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

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

Существуют ли другие способы ускорения процесса поиска решения? Да, и немалые! Хотя эта область слабо исследовалась, и здесь я могу высказывать лишь самые общие соображения, которые ещё не реализованы в работающей пограмме. Соображения такие:

  • На длинных рёбрах (особенно у кластеризованных графов, которые общепризнанно считаются самыми трудными для расчёта) по-прежнему происходят неприятные рекурсивные трепыхания, когда две или более связанных такими рёбрами группы мультиузлов лихорадочно пытаются отвязаться друг от друга. Если бы такая группа была уже объединена в единый мультиузел, вся эта возня была бы запрещена, поскольку это было бы перестроением его внутреннего тура. Но такого объединения пока не произошло, и заведомо бесполезные расчёты раздражают, хотя каскадирование по таймеру и не позволяет алгоритму слишком долго "заниматься глупостями". Можно, конечно, просто прорейтинговать мультиузлы по количеству у них рёбер-кандидатов (в таких случаях их всегда МНОГО), но хотелось бы какого-то более красивого и более эффективного решения.
  • Нередко множество пар рёбер-кандидатов фактически представляют собой единое мультиребро с одного мультиузла на другой, т.е. это на самом деле не множество, а один вариант перепривязки. Следовательно, нужно просто почистить пучок на предмет удаления сводимых друг к другу вариантов привязки, а не обсчитывать каждый из них по вышеописанному алгоритму.
  • Нужно активнее использовать базу данных, запоминая те состояния, которые потребовали значительных затрат процессорного времени.

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

18.08.2019 18:28
 
`