Построение кратчайшего вершинно непересекающегося пути, проходящего через обязательные вершины / Хабр

Сегодня мы разберём мою бакалавровскую дипломную работу о построении кратчайшего вершинно несамопересекающегося пути, проходящего через обязательные вершины (задача NP‑трудна).
Текст диплома довольно сложный, поэтому я постараюсь изложить его попроще и уберу доказательства вспомогательных утверждений.

Давайте же пройдём путь от рассмотрения ограничений задачи и её полиномиальных аналогов до ускоренного переборного алгоритма, который добьём метаэвристиками.

Начнём с того, что посмотрим, что вообще в задаче такого сложного, и как она не решается за полином (в чём её NP‑трудность).

У нас есть набор обязательных вершин, которые надо посетить в заранее заданной последовательности, при этом на каждую вершину можно зайти не более одного раза (как раз такая связка ограничений и даёт NP‑трудность).
Заметим интересное замечание:
При первом ограничении задача решается за полином (просто кратчайшие пути находим и всё).
При втором ограничении задача решается за полином (один кратчайший путь и так по определению не содержит циклов).
При объединении условий задача становится NP‑трудной (в случае, когда вершин 2 и больше, для 1 вершины есть полиномиальный алгоритм на основе потока минимальной стоимости).

Попробуем временно убрать одно ограничение и потихоньку возвращать его на место.
Интересный результат дал следующий подход, который мы назвали «рыбковой релаксацией»:
Ограничение на посещение вершины не более одного раза заменяется на то, что вход и выход на обязательных вершинах происходит через разные рёбра.
То есть, путь может быть только $x\rightarrow c_i \rightarrow y$ , но не $x \rightarrow c_i \rightarrow x$ .
Такое необычное свойство помогло усилить релаксацию, оставив трудоёмкость практически нетронутой.
По итогу куча подграфов «шиповых» исчезают и на их место приходят «рыбковые», с которыми уже можно работать. В «рыбковых» подграфах больше от допустимого решения, так как любое допустимое решение входит и выходит по разным рёбрам в любую вершину.

Рассмотрим идею алгоритма, псевдокод и прогоним на небольшом примере.

Идея такая, что мы делаем много копия графа, соединяем специальными рёбрами обязательные вершины между соответствующими порядку их обхода уровнями.
Потом прогоняем на каком‑то уровне алгоритм Дейкстры на всех вершинах кроме вершины обязательной цвета перехода на новый уровень, и тут же прогоняем шаг Дейкстры на соседях этой вершины на текущем и следующем уровне с условием рыбковости (вход и выход по разным рёбрам). Получается $\theta(deg(c_i)^2)$ итераций.
Так крутим все уровни снизу вверх и под конец получаем рыбково‑допустимое решение (нет «шиповых» подграфов, все недопустимости из‑за «рыбковых»).

Просто на всякий случай приведём псевдокод, хотя он скорее запутывает.
Но главное, что идея теперь понятна!

В будущем мы будем называть разные части «рыбки» своими терминами, поэтому давайте сейчас их все и определим: Голова, Тело, Позвонок (pivot) и Хвост. Вполне логичные обозначения, чтобы не использовать громоздкие «на пути между схождением последнего разветвления и первым с конца циклом».

Части рыбки - Голова, Тело, Позвонок (pivot) и Хвост. — Части рыбки — Голова, Тело, Позвонок (pivot) и Хвост.

Пока будем рассматривать задачу для 1 обязательной вершины, чтобы понаблюдать некоторые интересные результаты, которые будут полезны в дальнейшем при точечном подгоне эвристик.
Рассмотрим «редукцию рыбки» — попытку сделать решение допустимым, убрав какие‑то рёбра на рыбково‑допустимом (но недопустимом) решении.
Будем удалять правое или левое ребро (которое справа или слева от позвонка по голове рыбки) в следующем порядке:
Если удаляется любое ребро, удаляем как хотим, если удаляется только одно (а удаление другого влечёт отсутствие рыбково‑допустимого решения), то удаляем то, которое можно.
Подобное «Жадное» условие для выбора обладает одним интересным свойством.

Правое и левое ребро, о которых будет вестись речь.

Теорема: Алгоритм, описанный только что выдаст либо допустимое решение для задачи с одной обязательной вершиной, либо в противном случае можно будет утверждать, что допустимого решения не существует.
Доказательство будет упущено из‑за его громоздкости, однако спойлерну, что идея там в том, чтобы рассмотреть, как допустимое решение может зайти в рыбку и выйти из неё, и можно ли его переделать в случае, если удалённое ребро было на допустимом пути.

Доказательство упирается как раз на рыбковую допустимость и то же самое с «шипом» провернуть не получится.

Что толку от допустимого решения, давайте попробуем оптимальное выжать. Очень хочется рассчитывать, что оптимальное решение можно получить путём срезания правых и левых рёбер в рыбке. Интуитивно это кажется вполне логичным.
Оказывается, что есть
Теорема: При оптимальном выборе срезаний направо/налево можно получить оптимальное решение.
Доказательство ещё более громоздкое, но идея та же — предположить, что оптимальное решение мы повредили и посмотреть, можно ли его через оставшуюся часть рыбки восстановить. Трудность будет в том, что теперь необходимо так же смотреть за тем, чтобы решение не потеряло оптимальности (это делается путём поддержания следствия [полученное решение неоптимально $\rightarrow$ исходная рыбка не была оптимальна], а наш алгоритм по определению нашёл оптимальное решение среди рыбково‑допустимых).

Теперь логично всё это переделать в переборный алгоритм, так как пространство перебора мы значительно подрезали уже.
Составим «расписание срезаний» направо/налево (ассоциируем с 0 и 1) и если встаёт выбор о том, куда резать, будет сверяться с расписанием. Каждый раз, когда алгоритм релаксации (поиска рыбково‑допустимого решения по расписанию срезаний) останавливается (из‑за того, что рыбково‑допустимое решение стало допустимым или из‑за того, что рыбково‑допустимое решение перестало существовать), мы на глубине на 1 меньше бинарно к расписанию добавляем 1 и ставим везде на позициях дальше 0. Это будет эквивалентом того, что мы в поиске в глубину (DFS) шагнули с левого ребра на 1 направо
То есть $LLLLL\rightarrow_{4} LLLRL\rightarrow_{4} LLRLL\rightarrow_{2} LRRLL$ . Это позволит пробежать всё дерево перебора в порядке DFS (поиск в глубину).

С учётом того, что самое неприятное мы завернули в готовые функции, псевдокод уже становится хорошо читаемым.

Алгоритм ведёт себя хорошо, однако часто застревает в переборе очевидно худших решений, чем он уже нашёл. На практике такую проблему решают добавлением границ к ветвлению, однако для этого надо придумать какое‑то правило, да ещё и так, чтобы оно не поломало оптимальность лучшего найденного решения.

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

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

Для этого при каждом перезаходе на элемент расписания, мы будем обновлять соответствующую ему случайную величину, дальше для вычисления того, куда же резать, мы сложим оба значения по модулю 2 и посмотрим. Это эквивалентно тому, что мы наш поиск в глубину (DFS) иногда будем разворачивать в порядке обхода (не $L \rightarrow R$ , а $R \rightarrow L$ ).

Интуиция того, как связаны DFS(поиск в глубину) и стохастика, и почему случайные величины обновляются именно при перезаходе (мы попадаем в совершенно новое поддерево и корреляции с другими поддеревьями никому не нужны)

Например, в расписании стояло , а в соответствующих случайных величинах . Тогда расписание, которое увидит алгоритм при решении куда же резать будет

С таким бустом появился смысл рестарта алгоритма, и в самом деле, некоторые нехорошие постановки алгоритм раскусывал, когда заходил с правильного пути. Без стохастики он бы всегда шёл по одной и той же траектории, а теперь может поискать что получше, чтобы быстренько границами обрезать весь перебор и завершиться.

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

Для начала сделаем важное замечание, что поиск рыбково‑допустимого оптимального решения может поломаться, если реализовать его без рассмотрения случаев, когда существовало ребро между обязательными вершинами, следующими по порядку друг за другом (то есть ребро $c_i-с_{i+1}$ ). Либо надо ту самую вторую фазу Дейкстровых операций между уровнями проводить и для таких рёбер тоже, либо можно препроцесснуть граф в самом начале (что рекомендуется сделать) и на все такие рёбра добавить посередине вершину.

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

Теперь мы будем смотреть не два, а три ребра — добавим ребро от позвонка вверх по телу к хвосту. Это ребро назовём верхним и будем обозначать H.
Оказывается, что с рёбрами L,R,H можно восстановить результат про полный перебор и оптимальное решение.

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

Какие рёбра смотреть в нестандартных рыбках

Расписание теперь будет тернарное (по модулю трёх), а остальное всё так же.
Теорема: Если запустить перебор по трём рёбрам по тернарному расписанию, то лучшее найденное решение будет оптимальным.
Доказательство довольно простое и строится на том, что оптимальный путь в позвоночную вершину (как и в любую кроме начальной и конечной) входит и выходит по двум разным рёбрам, а значит, что для любых трёх различных рёбер у одной вершины точно существует хотя бы одна такая, которую можно вырезать без последствий.

И вот теперь хитрый трюк — как сделать стохастику, первая мысль — добавить по модулю трёх случайное число. Однако мы знаем, что есть сильные результаты для одной обязательной вершины без удаления ребра H. Мы будем надеяться, что куски доказательств тех результатов (для одной обязательной вершины) бустанут алгоритм и он быстрее пролетит начало перебора, собрав неплохие результаты, плюсом — может границ хороших понабрать, чтобы весь перебор быстрее завершить.
На практике так и оказалось, достаточно хорошие решения состояли, в основном, из срезов L, R с редкими вкраплениями H. На удивление, то же коснулось и оптимальных решений, они так же предпочитают в расписании L, R, чем H.
Именно поэтому мы будем случайные величины брать из и тем самым ребро H будет резаться всегда третьим. То есть, $0 \rightarrow [RLH], 1 \rightarrow [LRH]$ .

При исследовании постановки ЦЛП выяснилось, что она имеет неограниченный целочисленный зазор, о чём стоит точно упомянуть.

Почему это важно? Потому что это объясняет, на чём ложатся алгоритмы, основанные на переходе между ЛП‑ЦЛП. ЛП‑округления, прямо‑двойственные и все их друзья будут ломаться именно из‑за неограниченности целочисленного зазора. А так же именно за счёт этого пакетные решатели ложатся на больших размерностях — не могут понять, как этот зазор пробить.

Не буду усложнять всё вываливанием не очень компактной ЦЛП сюда, просто опишу, что там описывается довольно несложными ограничениями.
Постановка ЦЛП такая, что строятся копии графа (прямо как при рыбковой релаксации) и с самого низа из вершины входа запускается поток мощности 1, который заканчивается в самом верху в выходной вершине, при этом максимально в вершину может заходить поток мощности не более 1.
ЛП (без ограничения целочисленности) может решить разбить поток надвое (что недопустимо для булевых переменных) и тем самым протащить его через узкое место, сделанное так же половиной другого потока. Чтобы доказать неограниченность зазора, надо всего лишь придумать такой граф, в котором поток бы просочился, а путь — не смог. Тогда мы сделаем обход через очень дорогое ребро и ЛП пройдёт через наши баррикады напрямую, а ЦЛП будет вынужден проходить через дорогое ребро.
Например, такой граф можно использовать:

Так же стоит рассмотреть необычную модификацию, касающуюся ориентированных графов.
В них изменение такое, что путь может пройти по некоторым рёбрам только в одну сторону.
Алгоритм такой модификации задачи не переживёт и при первом же заходе на первую обязательную вершину сломается. На удивление, его можно поправить, только надо немного переписать то, как алгоритм постороения рыбково‑допустимого оптимального решения видит ориентацию рёбер.

Вот такая необычная модификация задачи, где тут рыбки - непонятно... — Вот такая необычная модификация задачи, где тут рыбки — непонятно...

Если после каждого посещения обязательной вершины мы будем для себя менять ориентацию рёбер, то на удивление алгоритм заработает как надо.

Вот так теперь выглядит рыбка, после перехода обязательной вершины мысленно меняем ориентацию каждый раз и всё будет хорошо.

Теорема о быстром поиске допустимого решения для одной обязательной вершины передоказывается в лоб, а вот теорема о поиске оптимального решения перебором (обе версии) передоказываются с немного более детальной проверкой корректности всех переходов.

А теперь перейдём от теории к практике и наконец прикоснёмся к метаэвристикам на основе всего того, что уже сделали!

Всё бы хорошо, но иногда оптимальное решение алгоритм ищет очень уж долго, попробуем его подтолкнуть на то, чтобы он максимально быстро выдавал хорошие решения, но за это заплатим тем, что он может потерять часть решений из перебора (в том числе и оптимальные). Для этого придумаем хитрые правила, которые обрежут перебор в «нелогичных» местах, но при этом будем допускать, что оптимальность решения может потеряться, главное — чтобы мы получили за относительно адекватное время хорошее решение.

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

Первая метаэвристика — изменение весов в графе таким образом, чтобы алгоритм при застревании слишком долгом на одном подграфе через какое‑то время вылазил из него, сказав, что там он всё «недалеко закопанное» нашёл.

Мы будем на каждой итерации брать и все входные и выходные рёбра вершин головы рыбки и увеличивать их на какое‑то небольшое число, которое оставим как гиперпараметр.

Вот пример работы алгоритма для решётки:

Нашёл OPT за одну итерацию, хотя чистый алгоритм бы довольно долго крутился

Рассмотрим ещё пример на решётке с дыркой.

Нашёл OPT+2 за 3 итерации, хотя чистый бы довольно долго крутился (но зато нашёл бы OPT)

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

$OPT[G’]=\sum_{OPT}ei+\varepsilon i=\sum_{OPT}ei+\sum_{OPT}\varepsilon i \geq \sum_{OPT}ei=OPT[G] \geq LB[G]$

$OPT[G’] \geq LB[G]$

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

Так же стоит обратить внимание, что при малых $\varepsilon$ можно пользоваться какой‑нибудь оценкой реального на от найденного в другую сторону.

$OPT[G]+\sum_{OPT}\varepsilon i \geq OPT[G’]$

$OPT[G] \geq OPT[G’]-\sum_{OPT}\varepsilon i$

Рассмотренный подход, конечно, бустит поиск хороших решений очень круто, но может, можно найти что‑то полностью другое и скомбинировать подходы, чтобы получилось убойную метаэвристику?

Вторая метаэвристика — вводим штраф за тело рыбки.
Мы будем во время построения рыбково‑допустимого оптимального решения менять веса при проталкивании весов так, чтобы за прохождение по ребру, по которому мы уже прошли на уровнях ранее начислялся штраф (да, это тоже будет гиперпараметр).

Важно заметить, что теперь рыбково‑допустимое решение может стать неоптимальным, однако мы вводим очень тонко настроенную штрафную функцию, которая будет тянуть алгоритм стараться перевести рыбковую допустимость в просто допустимость.
К сожалению, на эту метаэвристику никаких оценок нет, так как она цепляется куда глубже — влияет на то, что мы считаем рыбково‑допустимым оптимальным решением и поэтому оценок на полученный эффект теоретических нет.

Идея того, как делать такие штрафы на тело рыбки, чтобы его не было.

Дальше мы будем считать, что обе метаэвристики у нас подключены и мы будем говорить про их гиперпараметры (ведь если оба гиперпараметра 0, то алгоритм становится чистым).

Перейдём к численным замерам, чтобы наконец увидеть всю силу того, что же мы сделали!

Рассмотрим для начала равномерное распределение рёбер в графе, где $p=\frac{N}{aC^2_N\ln(N)}$ — вероятность добавления каждого ребра в граф).

2 обязательные вершины, 1000 вершин всего

В квадратных скобках будет время в секундах, рядом значение целевой функции, если обведено жёлтым — значит, получилось доказать оптимальность (помним, что доказывать оптимальность можно только с гиперпараметрами )
Значения гиперпараметров для каждого замера написаны сверху в квадратных скобках над каждым столбцом с замерами.
Каждая строка — это новая постановка задачи, некоторые ячейки пустые — там нет ничего интересного (информация оттуда не даст ничего нового, но запутает хорошо).
В самом конце строки указана нижняя оценка (для оценки точности).
Через 30 секунд, для честности замера, алгоритм останавливался.

6 обязательные вершины , 1000 вершин всего — 6 обязательные вершины, 1000 вершин всего

10 обязательных вершин, 1000 вершин всего

На равномерном графе справляется очень хорошо, достаточно часто даже оптимум находит, точность достаточно хорошая даже без метаэвристик, а с ними — и ещё лучше.

Посмотрим ещё UnitDisk граф, который будет брать случайно распределённые точки на квадрате 1×1 и ставить ребро с вероятностью p при условии, что расстояние между точками не превосходит r. Этот граф, судя по нашему опыту, должен положить алгоритм на некоторых постановках.

6 обязательных вершин, 1000 вершин всего

10 обязательные вершины, 1000 вершин всего

Как видно, после всех улучшений и модификаций, наш алгоритм справляется с поиском хорошего решения очень неплохо!

Закончим тем, что добавим HotStart — возможность начинать поиск с уже известного решения.
Это может быть полезным при сгибридивании с другими алгоритмами, так как можно то, что выдал другой алгоритм дать нашему на вход и он воспользуется этим, тем самым алгоритмы могут друг друга существенно усиливать.

Для этого возьмём какой‑нибудь допустимый путь (который нам дали, будем называть его target) и попробуем найти такое расписание срезаний, чтобы максимально приблизиться к этому пути.
Будем строить рыбки и резать любое из предложенных алгоритмом рёбер, которое не использовано в пути target (ранее выясняли, что так всегда можно сделать для любого допустимого пути).

В какой‑то момент мы придём к ситуации, что рыбок больше нет и решение стало допустимым, однако пути могут не совпасть, что кажется не совсем хорошим.
На самом деле это даже круто, ведь мы по‑сути в пространстве расписаний срезаний нашли такое расписание, что путь target туда попадает, а наш алгоритм среди всех рыбково‑допустимых путей нашёл оптимальный.

То есть, для этого расписания срезаний есть много допустимых путей и target — один из них, а мы нашли оптимальный на этом пространстве.
То есть уже на первой итерации есть шанс улучшить решение и дать второму алгоритму.

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

Рассмотрим эту «маску» более детально.
Если стохастика просто тернарно добавляется к расписанию срезаний, то на первой итерации принудительно означиваем все случайные значения (теперь уже не случайные, но только на первой итерации, при перезаходах опять будут случайные) так, чтобы получилось то, что нам надо.
Если ребро H у нас было всегда последним, то придётся действовать хитрее:
Если надо принудительно поставить R, L, то сделаем это за счёт случайных величин (сделав на первой итерации их не случайными), если же надо поставить H, то заведём инверторы, которые изначально все выключены и где нам надо поставить H — включены. Они будут менять порядок [H], [R, L] местами и при перезаходе ставиться на выключение (мы же уже поняли какой порядок лучше, если нет внешнего стимула как target, то зачем держать инвертор включённым).
$[LRLR] \rightarrow_? [RHRL]$
$[LRLR] + [1011] = [RRRL] \rightarrow_? [RHRL]$
$[LRLR] + [1011] +_{inv} [0100] = [RRRL] +_{inv} [0100] = [RHRL]$

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

Построение кратчайшего вершинно непересекающегося пути, проходящего через обязательные вершины

Как я, учась в айти, работаю на 15-тонном советском станке и автоматизирую его без CAM‑системы и комментариев

В России начали блокировать DoH и DoT от Google и Cloudflare

Wi-Fi научился видеть людей сквозь стены. Я полез в код, и там нашёлся подвох

410.chat — Одноразовый чат для двоих

Публикации