Comments 8
Я почти ничего не понял. Есть несколько вопросов/комментариев.
Могли бы вы описать, что конкретно вы сделали? Нашли полиномиальное приближенное решение? Придумали эвристику, ускоряющую перебор?
Стоит в начале указать, почему задача NP-трудна. Вы во введении обещаете рассмотреть этот вопрос, но забываете о нем. Например, надо какую-нибудь известную задачу свести к этой.
Потом вы какую-то рыбу вводитите и тут я нить повествования потерял. Что вы вкладываете в термин "релаксация"?
Нашли ускоренный переборный (точный) алгоритм и потом переделали его в метаэвристику (с потерей оптимального решения в обмен на быстрое получение достаточно хорошего).
Релаксация это снятие или ослабление каких-то условий, тут мы условие на непересекаемость пути по вершинам заменили на "рыбковость" и крутили дальше.
NP трудность для 2 вершин доказывается очень непросто, когда число обязательных вершин является элементом входа, можно свести напрямую к 3cnf через хитрый и красивый трюк (о котором, возможно, я сделаю отдельный разбор в будущем). Более того, можно доказать (если число обязательных вершин - это элемент входа), что задача неаппроксиммируема с любым множителем (как Кромивояжёр без метрики), доказательство основано на NP трудности и конструкции похожей на то, чем тут доказывается неограниченность ЦЛП-ЛП зазора. Возможно, в будущем сделаю на это всё разбор.
Определенно не хватает информации о том что такое несамопересекающийся путь в графе - без пересечения ребер? без повторных входов в ту же вершину? Да и в общем полноценной постановки задачи нет.
Примеры на КДПВ не сказать чтобы сильно поясняют ситуацию. Если речь таки про рёбра, то получается появялются неназыванные ограничения на геометрию графа, о которых ничего не рассказывается. Если нет, то непонятно почему не изобразить адекватный нормализованный граф без подобных пересечений - для всех вышеприведённых примеров это вполне реально, насколько я могу видеть?
На картинки с "решением ЦЛП/ЛП" происходит что-то непонятное - какие-то двойки на одном и том же ребре, какие-то буквы у некоторых вершин, какие-то цифры. Закодированных примеров графов на которых решалась бы проблема тоже не представлено.
Выглядит что нас в основном интересует красный путь, но непонятно зачем нам видеть ещё и синий. S и T я так понимаю это начало и конец которые мы соединяем, но опять же - нигде нет легенды с пояснением маркеров. Зачем на графах появляются 1 и 2 на двукружковых вершинах тоже не рассказывается.
чтобы алгоритм при застревании слишком долгом на одном подграфе
про разделения графа на подграфы нигде речи не шло, так что непонятно когда они появляются. Детекцию шипов и рыбок тоже опустили, кейсы типа сиамской рыбки - когда в голове n рёбер между пивотом и точкой исхода или из пивота торчит n хвостов - тоже не рассмотрено.
Идея с добавлением дополнительных ребер/вершин напоминает эвристики для A* с вложенными рассечениями, но для чего оно используется в вашем случае - я так и не понял.
Согласен, слишком уж сократил.
Путь может пройти через одну и ту же вершину только один раз.
Без пересечений путь будет допустимым, допустимый+оптимальный -> np-h, мы же немного ослабляем допустимость, с этой постановкой ковыряется и получаем необычный ускоренный переборщик (который потом перестраиваем в метаэвристику по поиску просто хорошего решения).
1,2 - это порядок обхода обязательных вершин, путь получается как s->1->2->3->t с промежуточными вершинами без маркеров.
Разделения на подграфы и нет, я просто описываю как алгоритм ложится (он находит подграф-ловушку, зацикливается на него и начинает люто ветвиться по рёбрам, в таком случае мы настраиваем веса новые так, чтобы такой подграф-ловушка перестал его интересовать). В самом деле, напоминает немного A*, только у них оптимальность не ломается, а тут он как бы отказывается постепенно смотреть какие-то подграфы, где вообще-то могло спрятаться оптимальное решение. Например, если вы в хорошем разреженном графе воткнёте посредине клику с малыми весами и подгоните пути, то алгоритм застрянет на переборе рёбер клики, пытаясь выжать лучше и лучше, мы же его потихоньку успокаиваем и говорим, что в клике этой он и так хорошо поковырялся уже и надо начинать её избегать, это позволяет выводить ветвление из таких нехороших подграфов.
Если очевидную ЦЛП перевести в ЛП, то целочисленный зазор в худшем случае станет неограниченно большим, что показано на примере (если путь может разбиться на нецелочисленные, то он пойдёт дешёвым путём, а вот просто путь без этого допущения не пройдёт там и пойдёт в обход по дорогому пути).
С детекцией - да, надо было объяснить получше, но, в принципе, можно догадаться, что если я не акцентирую внимание на конкретной рыбке, то можно брать для ветвления любую (я брал первую встретившуюся). Но тут вы правы - я зря про это не рассказал.
если вы в хорошем разреженном графе воткнёте посредине клику с малыми весами и подгоните пути, то алгоритм застрянет на переборе рёбер клики
а как это происходит? пока что звучит, что автомагически. zoom out из ноды в клики статья не затрагивает, просто описывается, что оно там как-то по какому-то непонятному критерию понимает, что всё, пора валить в соседнюю клику. Как выглядит это ваше "успокаиваем"?
Если очевидную ЦЛП перевести в ЛП
вот кстати отдельный вопрос, что же кроется под ЦЛП/ЛП. Я знаю только целочисленное линейное программирование, но в контексте статьи это не очень имеет смысл. целочисленный линейный поток? Но тогда что такое ЛП-округление? Какой-нибудь лоботомизированный подграф или что это?
Верно, это происходит автоматически, мы на "голове рыбки" увеличиваем веса и если рыбка часто формируется на одном месте, то добавляется достаточно большой добавок на рёбра чтобы подграф-ловушка перестал перетягивать на себя рыбку.
Варьируя этот добавок, можно поставить разную силу "успокаивания", чтобы подграф получал на рёбра довесок и становился непривлекательным.
Были и более аккуратные способы, позволяющие, например, получить результат не более r*opt (перебор немного упрощается в обмен на смещение оптимума, такой регуляризатор как бы) где r-гиперпараметр, но на практике смысла в них оказалось не много.
Можно записать задачу как ЦЛП булевую и если решать её как ЛП на [0,1], то решения будут выглядеть как разноцветные потоки суммарной мощности 1 (поток мощности 1 отправляется по s->t, поток мощности 1 из 1->2, мощности 1 из 2->t), но из-за того что у нас решается ЛП, то может поток разбиться, например, на два потока 0.5+0.5 и пойти по разным рёбрам и так соединиться с другими 0.5 потоками. Изначально пытались получить приближённый алгоритм перестройкой ЛП в допустимое решение и поняли, что за счёт того трюка можно получить неограниченную оценку на зазор целочисленности.
Построение кратчайшего вершинно непересекающегося пути, проходящего через обязательные вершины