Главная

Новый

Главная
Комми
Новый
Модель
Заявка
Программа
Финал
Эпилог
Эксперимент

Карта

Мультиузлы




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

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

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

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

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

А как узнать, сколько же нам нужно мультиузлов и, главное, каких? Какие группы выгодно объединять в мультиузлы, а какие нет? Нужно ли объединить мультиузел с другим или, наоборот, его следует расщепить на более мелкие? Анализ или синтез? Two beer or not two beer? Даже в самых простых ситуациях, даже в грубом приближении, ответы на эти и некоторые другие вопросы отнюдь не очевидны. Попробуем предложить свои варианты ответов, организовав их в виде FAQ:

  1. А нельзя ли вообще обойтись без мультиузлов?
    Можно, но лишь для относительно малых графов, которые по силам методам brute force - это проще и, возможно, даже быстрее. Для больших графов (по нашим оценкам, эта граница лежит в диапазоне 100-1000 узлов) мультиузлы резко снижают объём вычислений. В самом деле, если считать длину мультиребра равной длине его самого короткого ребра, этого нередко уже достаточно, чтобы гарантировать невозможность вхождения мультиребра в оптимальный тур, что позволят удалять рёбра графа из рассмотрения целыми каналами. Тем более, что мультиузлы могут образовывать иерархическую структуру (как было показано выше в "космическом" примере), с ещё более "тяжёлыми" мультиребрами. Очевидно также, что объём самого мультиребра в большинстве случаев также может быть значительно уменьшен. Одним словом, число удаляемых рёбер даже для небольших графов многократно превышает число остающихся в рассмотрении.

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

  3. Есть ли другие критерии для расщепления?
    Сколько угодно! Даже группировка городов по алфавиту чрезвычайно упрощает вычисление внутренних туров. Но с обработкой мультирёбер, разумеется, возникнут серьёзные проблемы. Мы полагаем, что указанный нами способ формирования мультиузлов - наиболее естественный, и при последующем слиянии вероятность перестроения туров минимальная.

  4. В каких случаях расщепление нецелесообразно?
    Когда оптимальность внутреннего тура мультиузла доказана, или легко может быть доказана методом "грубой силы", т.е. для групп примерно до 20-30 узлов. Впрочем, и для них расщепление не помешает. Для больших групп целесообразно отделение даже отдельных узлов.

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

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

  7. Может ли процесс слияния мультиузлов вновь замениться процессом их расщепления?
    Да, и неоднократно. Слияние мультиузлов может потребовать перестройки их внутренних туров, и эта перестройка вновь может приводить к расщеплению.

  8. Можно ли формировать мультиузлы операцей слияния мультиузлов, начиная с отдельных узлов?
    А зачем? У нас ведь нет никакой информации о критериях такого слияния. Информация же о расщеплении содержится в самом туре, полученном к началу работы алгоритма, и она достаточно высокого качества, поскольку тур близок к оптимальному.

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

  1. Удаляется ребро 3-5. Граф разбит на мультиузел 2...5 и остальную группу узлов, причём ребро 1-3 теперь относится к внутреннему каналу мультиузла 1...4...3.
  2. Удаляется ребро 3-4. Граф разбит на мультиузел 1...4 и остальную группу узлов, причём ребро 1-3 теперь относится к внешнему (межгрупповому) каналу мультиузлов 1...4 и 2...5...3.

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

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

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

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

Неприятности на этом не заканчиваются: оказывается, очень важна даже последовательность обсчёта узлов и мультиузлов. Проиллюстрируем на примере: предположим, у нас есть граф, все узлы которого расположены более-менее компактной группой, а один из узлов отстоит очень далеко от неё. Предположим также, что наш тур уже наилучший, и мы сейчас фактически лишь доказываем его оптимальность (чтобы алгоритмы перестройки тура пока не "путались под ногами"). Тогда, если мы начнём расчёт с этого удалённого узла, мы быстро убедимся, что узел привязан оптимальным образом и объединим его с соседями по туру в единый мультиузел, как это и предписывает наш алгоритм. Но если мы начнём расчёт с одного из этих соседей, мы его никогда и не закончим: оба этих узла будут "согласны" на любое искажение тура - лишь бы не "терпеть" рядом с собой этого "выродка"! Но ведь мы не знаем заранее конфигурацию графа, и не можем определить "правильный" порядок рассмотрения узлов! Что будем делать? Золотое правило перебора (вернее, это я считаю это правило "золотым", но готов стереть в порошок любого, кто осмелится возразить) гласит: "Не знаешь, что делать - включай каскады"! В самом деле: если мы "поставим ограничитель" на количество интересных рёбер в мультиузле (тоже по степени двойки: вначале рассматриваем мультиузлы, у которых количество интересных рёбер менее 1, затем - менее 2, менее 4 и т.д.), то даже если мы начнём обсчитывать вначале узлы, смежные с "выродком", этот расчёт будет мгновенно прерван (отложен) при получении первого же интересного ребра, поэтому первым всё равно будет обсчитан именно "выродок", который и объединится с соседями в единый мультиузел, обрубив на хрен всю эту тупую комбинаторику.

Итак, на входе мы имеем граф с туром, достаточно близким к оптимальному, т.е. полученным после работы нашего "среднего" алгоритма (это минимум), случайного, или какого-либо внешнего. Это условие не обязательное, но на турах с большой бета-границей трудоёмкость работы этого алгоритма вырастет катастрофически - "сдохнет на первом же ребре". Главная задача - доказать оптимальность текущего тура. Побочная - улучшить тур, если текущий не оптимален. Никаких мультиузлов ещё не сформировано (точнее, каждый отдельный узел выступает ещё и в роли мультиузла). Предполагается также, что для каждого узла у нас посчитана альфа-граница (точнее, "рога") и бета-граница (тур), что позволяет нам легко посчитать эти границы для любого мультиузла и всего графа в целом. Мы должны рассмотреть все n(n-3)/2 рёбер (у нас же полный перебор!), не входящих в тур, на предмет возможности включения их туда. Очередной рассматриваемый кандидат на включение, во первых, не должен принадлежать внутреннему каналу какого-либо из мультиузлов (такие рёбра сразу отбрасываются) и, во-вторых, должен давать хотя бы теоретическую (оптимистическую) надежду на улучшение тура.

В общем случае, ситуация с перепривязкой выглядит так: ребро NC (рис. 3) соединяет рассматриваемый мультиузел N (связанный до этого межгрупповыми рёбрами с мультиузлами A и B), с мультиузлом C. Чтобы это ребро имело хотя бы теоретические шансы быть включённым в [более] оптимальный тур, как минимум, одно из межгрупповых рёбер мультиузла N (допустим, ребро NA) должно быть удалено (чтобы не нарушалась целостность тура). А то и оба: второе ребро NB после перестроения тура может быть заменено на некоторое ребро ND, связывающего мультиузел N с каким-то новым мультиузлом D. Аналогично, внешние рёбра мультиузлов A, B, C и D должны перестроиться так, чтобы их длина проходила по альфа-границе, а длина внутренних туров всех мультиузлов нисколько не увеличилась бы (тоже проходила бы по альфа-границе). Всё, больше нам надеяться не на что! Если рассматриваемое ребро NC не удовлетворяет этим условиям, оно никоим образом не может принадлежать оптимальному туру, и тоже отбрасывается. В противном случае, нам придётся подтвердить (или опровергнуть) гипотезу о наличии рассматриваемого ребра в оптимальном туре полным перебором всех вариантов. Отметим, кстати, что мультиузлы A, B, C и D вовсе не обязательно разные - нам придётся рассмотреть все возможные случаи. Условие необходимости рассмотрения ребра NC на предмет возможности включения в тур выглядит так:
NA + NB + AR(β) + BR(β) + CR1(β) + CR2(β) + DR1(β) + DR2(β) > NC + ND(α) + CR(α) + DR(α) + AR1(α) + AR2(α) + BR1(α) + BR2(α)

Что это даёт? Во-первых, совершенно дикое усложнение алгоритма - от одной только формулы включения ребра в рассмотрение в дрожь бросает! Зачем нам это нужно? Судите сами: мы рассматриваем не весь граф, а лишь относительно небольшую его часть, так что от исходного факториала вариантов остаются "рожки да ножки". Мало того: все межгрупповые рёбра "провешиваются" заранее, что не позволяет нам углубляться в бессмысленную рекурсию по внутренним турам мультиузлов - ведь альфа-граница в этом случае максимально приближена к бета-границе, и любой "шаг вправо, шаг влево" теперь немедленно "карается расстрелом". Одним словом, игра стоит свеч! Хотя, конечно, от логической сложности алгоритма крыша съезжает набекрень. Впрочем, львиную долю рёбер можно отбросить и "малой кровью", без этой "мышиной возни" с мелкими мультиузлами: есть рассматриваемый мультиузел N и "ответная часть" R - все остальные узлы графа. Где-то внутри ответной части находятся мультиузлы A и B, связанные межгрупповыми рёбрами с исследуемым, а также C и D, которые, возможно, будут с ним связаны после перестроения тура. Любой из этих мультиузлов можно рассматривать либо как самостоятельный мультиузел, либо как часть мультиузла R - как нам в данный момент удобнее. Попробуем?
Назад...   Далее...

19.06.2016 15:10
 
`