Скажите, а вы после каждого прохода вниз по иерархии ведёте локальный поиск на следующем уровне? Просто об этом не говорится, но интересно - вы локальный поиск с этим радиусом гоняете только на последнем уровне ради экономии итераций или на всех уровнях (возможно, сэкономив на радиусе поиска далее, так как логично предположить, что он будет меньше).
А так же встаёт интересный вопрос - не лучше ли ради пользовательских целей принудительно заставить алгоритм около старта меньше раз вливаться, смещая всё потери к середине или концу пути?
Логика такая, что сейчас пользователь едет по первым 10 рёбрам из 1000 и большая неточность далеко от пользователя слабо влияет на то, куда он прямо сейчас будет ехать (руль крутить), однако сравнивая с кратчайшим путём мы получим, что та неточность под конец из-за иерархической ошибки при декомпозиции практически не повлияет на его траекторию сейчас, главное - чтобы вокруг пользователя пути строились с достаточно высокой точностью (чтобы руль крутил куда надо), а потом путь можно пересчитать, так как он станет меньше и так логарифм раз до финиша.
Можно, например, насильно ронять иерархию на уровни ниже около пользователя и тем самым те самые неприятные артефакты при переходе между уровнями (которые полируются локальным перестроением потом) будут дальше (что хорошо, так как ошибка "самортизируется" при превращении в следующие 10 минут действий пользователя (кручении руля).
К сожалению, нельзя. Дело в том, что в конкретный момент времени ближайший вход может оказаться недостижим; всё те же чёртовы time-based
Не не, я немного не про это, я про то, что когда волна извне приходит на границу и мы понимаем, что она уже потрогала ближайший из допустимых входов (например, если к самому ближайшему подошла), то мы по нему и пройдём внутри и в этот момент (когда мы можем с уверенностью сказать, что мы вошли во внутренний подграф по разрезу оптимально) дерево внешнее растить смысла больше нет, так как вход по неоптимальному входу недопустим (условие ПДД на argmin(...)), в таком случае можно внешнее дерево больше не растить, так как любой другой вход сделает решение недопустимым.
Вот и получается странно - когда мы уже знаем, что вход выбран оптимально (покрыл всё множество argmin(...)), то можно дерево заморозить, а у вас ставятся тормозащие штрафы на разрез, чтобы при этом раздувать внешнее дерево (а вершина посередине пути штраф вообще не видит ведь). Проблема в том, что target в A* штука не совсем умная и, например, может быть какой-то мощный поворот или объезд, где геометрию околопрямого пути пришлось существенно нарушить, вот от туда как раз и могут пойти отростки огромные, так как модификатор рёбер думает, что вы это сделали зря (ведь закрытая на ремонт или стоящая в мёртвой пробке дорога модификатору не видна) и что надо вас поправить и попытается найти какое-то решение пооптимальнее, при этом делая огроменный фронт поиске, ведь из-за поворотов расстояние уже большое и он будет рассматривать немало "потенциально лучших" путей.
И начинается, по сути, брутфорс: перебираем пары въездов/выездов и пытаемся между ними построить проезд. При этом надо минимизировать сумму длин проездов внутри зон, поскольку именно в этом их административный смысл. И вот этот перебор - просто смерть для перформанса. Да, ситуация не столь частая, но кога она стреляла, было грустно.
Ой...да, не подумал, что выход тоже может быть из другого внутреннего графа. Но в таком случае ведь если запускать Дейкстру от Дейкстр (внутри стартового графа искать оптимальный и потом менее и менее оптимальный выход и с каждого такого менее оптимального выхода поочерёдно запускать A* во внешность, пока он не сломается (тупик) или не найдёт проезд), то граф плоский будет биться на компоненты связности (тупики) и одна из них всё-же дойдёт до второго графа внутреннего и для неё это будет корректный argmin, а значит решение будет допустимым. Если есть решение лучше, то только в выборе выезда из первой компоненты, а мы помним, что условие на argmin и там и там есть, так что оптимальность очевидна.
Единственная сложность такого подхода - временные окна, ведь у вас на самом деле решается обычная задача на графе трёхмерном с ориентированными рёбрами (рёбра в какие-то моменты времени есть, в какие-то нет, по времени движемся вверх с таким-то переходом на каждом ребре, пройдя вперёд-назад по одному ребру на самом деле проходим по двум рёбрам, каждое из которых отправляет немного в будущее на уровни выше) делится не факт что всегда на несвязные секции, которые друг друга не включают (один A* застрял в тупике и его компонента больше не трогается, другой A* дошёл до моста после того, как тот был заблокирован и теперь стоит в очереди на открытие, а вот третий приехал прямо перед открытием моста и они одновременно стартовали с тем который ждал, и получается, что их пути объединились (что глупо, так как мы дважды считаем одно и то же)). Правило FIFO тут может подсказать кучу трюков, как этого избежать. Тут для разделения (и, соответственно, экономии вычислений) можно, например, сделать запрещающие интервалы по времени по типу "тут до тебя с 8:40 стоял предыдущий A* и по итогу приехал к закрытому шлагбауму и поэтому ты появился, ты тут в 8:50 даже не думай ехать, зачем тебе считать путь до закрытого шлагбаума". Например таким правилом со всего одной переменной на каждой вершине посещённой хоть кем-то, кого пришлось рестартнуть "кто проехал по ребру после 9:00 не доехал...кто поехал после 8:20 не доехал...кто поехал после 7:20 не доехал..." можно сделать так, чтобы трёхмерный граф разбился на независимые подграфы и, тем самым, не делал лишних вычислений.
А вот если делать штрафы на время, то вы как бы одновременно запускаете и того A*, который сможет дойти нормально (и на нём стоит остановиться, так как он выдаст min|argminANDargmin) и следующего и следующего и фронт растёт значительно, хотя какую-то его часть рассматривать смысла вообще нет. Более того, так как граф у вас трёхмерный (пусть и неявно), то эти деревья могут друг друга перекрыть (оба подъехали к мосту после закрытия и ждут, хотя логично что тот кто первый заехал успеет быстрее, либо оба не успеют).
Я так и не понял, как так получилось, что у вас существенное преимущество одного запуска большого. Это выглядит немного нелогично.
По-сути, весь граф разделён на (небольшую) внутренность, разрез и внешность (очень большую). Вы хотите найти путь min:s-p-t|p-t<p'-t, изначально вы запускали поиск от t до разреза, потом от s до входов на разрез (когда прошли все входы или лучший из доступных), дальше восстанавливали решение. Самое тормознутое - дерево от s до разреза (оно в ширь разрастись должно нормально так даже при использовании адекватных модификаторов весов как A*), так что как только он прошёл всё, что нужно, его тут же надо обрывать (так как ещё один шаг очень дорогой). Тут так и происходит, от границы внутрь решено всё уже, самое тяжёлое сейчас считается.
Во втором алгоритме вы вводите тормозящие штрафы, вот только пока алгоритм ждёт истечения штрафа на следующий вход, во внешности графа растёт огроменное дерево, которое его тормозит.
Если сравнить с первым алгоритмом, то вместо того, чтобы внешний поиск остановить, вы его продолжаете, при этом как бы запускаете внутренний поиск наоборот (от разреза в центр). Получается выигрыш на внутреннем графе (ведь вы не весь его считаете, а только кусочек, да и A* есть куда направить target. Но при этом проигрываете за счёт того, что огромное тяжеленное дерево всё это время растёт...и это при том, что если вы уже зашли с ближайшего входа, то внешнее дерево в принципе можно блокировать. Да, через границу из-за тормозящих штрафов ничего не пролезет, но при этом в остальной граф то оно всё полезет.
Но если внутренний граф такой уж плотный, может, стоит вместо перехода к этому огромному дереву объединить лучшее алгоритмов?
Например, дать дереву внешнему пройти до вершины номер 1 (или доказать, что пути нет и дойти до номера 2...и сказать, что лучше он найти не может и потом так же от этой вершины запустить поиск по внутреннему графу. По вычислениям получается в худшем случае так же (вам ведь нужно обосновать, что вход через разрез ближайший, иначе решение недопустимое), но скорее всего оно будет гораздо лучше, так как если он пройдёт 2 вход и 1 вход, внешнее дерево он как бы перестаёт постить (а оно огроменное).
Пока нет, сейчас мы готовим новую работу к публикации, потом займёмся подготовкой старой (этой) но более расширенной. Как опубликуем (примерно через год, может чуть раньше), постараюсь ссылку в комментариях выложить не забыть.
Верно, это происходит автоматически, мы на "голове рыбки" увеличиваем веса и если рыбка часто формируется на одном месте, то добавляется достаточно большой добавок на рёбра чтобы подграф-ловушка перестал перетягивать на себя рыбку.
Варьируя этот добавок, можно поставить разную силу "успокаивания", чтобы подграф получал на рёбра довесок и становился непривлекательным.
Были и более аккуратные способы, позволяющие, например, получить результат не более r*opt (перебор немного упрощается в обмен на смещение оптимума, такой регуляризатор как бы) где r-гиперпараметр, но на практике смысла в них оказалось не много.
Можно записать задачу как ЦЛП булевую и если решать её как ЛП на [0,1], то решения будут выглядеть как разноцветные потоки суммарной мощности 1 (поток мощности 1 отправляется по s->t, поток мощности 1 из 1->2, мощности 1 из 2->t), но из-за того что у нас решается ЛП, то может поток разбиться, например, на два потока 0.5+0.5 и пойти по разным рёбрам и так соединиться с другими 0.5 потоками. Изначально пытались получить приближённый алгоритм перестройкой ЛП в допустимое решение и поняли, что за счёт того трюка можно получить неограниченную оценку на зазор целочисленности.
Путь может пройти через одну и ту же вершину только один раз.
Без пересечений путь будет допустимым, допустимый+оптимальный -> np-h, мы же немного ослабляем допустимость, с этой постановкой ковыряется и получаем необычный ускоренный переборщик (который потом перестраиваем в метаэвристику по поиску просто хорошего решения).
1,2 - это порядок обхода обязательных вершин, путь получается как s->1->2->3->t с промежуточными вершинами без маркеров.
Разделения на подграфы и нет, я просто описываю как алгоритм ложится (он находит подграф-ловушку, зацикливается на него и начинает люто ветвиться по рёбрам, в таком случае мы настраиваем веса новые так, чтобы такой подграф-ловушка перестал его интересовать). В самом деле, напоминает немного A*, только у них оптимальность не ломается, а тут он как бы отказывается постепенно смотреть какие-то подграфы, где вообще-то могло спрятаться оптимальное решение. Например, если вы в хорошем разреженном графе воткнёте посредине клику с малыми весами и подгоните пути, то алгоритм застрянет на переборе рёбер клики, пытаясь выжать лучше и лучше, мы же его потихоньку успокаиваем и говорим, что в клике этой он и так хорошо поковырялся уже и надо начинать её избегать, это позволяет выводить ветвление из таких нехороших подграфов.
Если очевидную ЦЛП перевести в ЛП, то целочисленный зазор в худшем случае станет неограниченно большим, что показано на примере (если путь может разбиться на нецелочисленные, то он пойдёт дешёвым путём, а вот просто путь без этого допущения не пройдёт там и пойдёт в обход по дорогому пути).
С детекцией - да, надо было объяснить получше, но, в принципе, можно догадаться, что если я не акцентирую внимание на конкретной рыбке, то можно брать для ветвления любую (я брал первую встретившуюся). Но тут вы правы - я зря про это не рассказал.
Нашли ускоренный переборный (точный) алгоритм и потом переделали его в метаэвристику (с потерей оптимального решения в обмен на быстрое получение достаточно хорошего).
Релаксация это снятие или ослабление каких-то условий, тут мы условие на непересекаемость пути по вершинам заменили на "рыбковость" и крутили дальше.
NP трудность для 2 вершин доказывается очень непросто, когда число обязательных вершин является элементом входа, можно свести напрямую к 3cnf через хитрый и красивый трюк (о котором, возможно, я сделаю отдельный разбор в будущем). Более того, можно доказать (если число обязательных вершин - это элемент входа), что задача неаппроксиммируема с любым множителем (как Кромивояжёр без метрики), доказательство основано на NP трудности и конструкции похожей на то, чем тут доказывается неограниченность ЦЛП-ЛП зазора. Возможно, в будущем сделаю на это всё разбор.
Скажите, а вы после каждого прохода вниз по иерархии ведёте локальный поиск на следующем уровне? Просто об этом не говорится, но интересно - вы локальный поиск с этим радиусом гоняете только на последнем уровне ради экономии итераций или на всех уровнях (возможно, сэкономив на радиусе поиска далее, так как логично предположить, что он будет меньше).
А так же встаёт интересный вопрос - не лучше ли ради пользовательских целей принудительно заставить алгоритм около старта меньше раз вливаться, смещая всё потери к середине или концу пути?
Логика такая, что сейчас пользователь едет по первым 10 рёбрам из 1000 и большая неточность далеко от пользователя слабо влияет на то, куда он прямо сейчас будет ехать (руль крутить), однако сравнивая с кратчайшим путём мы получим, что та неточность под конец из-за иерархической ошибки при декомпозиции практически не повлияет на его траекторию сейчас, главное - чтобы вокруг пользователя пути строились с достаточно высокой точностью (чтобы руль крутил куда надо), а потом путь можно пересчитать, так как он станет меньше и так логарифм раз до финиша.
Можно, например, насильно ронять иерархию на уровни ниже около пользователя и тем самым те самые неприятные артефакты при переходе между уровнями (которые полируются локальным перестроением потом) будут дальше (что хорошо, так как ошибка "самортизируется" при превращении в следующие 10 минут действий пользователя (кручении руля).
Не не, я немного не про это, я про то, что когда волна извне приходит на границу и мы понимаем, что она уже потрогала ближайший из допустимых входов (например, если к самому ближайшему подошла), то мы по нему и пройдём внутри и в этот момент (когда мы можем с уверенностью сказать, что мы вошли во внутренний подграф по разрезу оптимально) дерево внешнее растить смысла больше нет, так как вход по неоптимальному входу недопустим (условие ПДД на argmin(...)), в таком случае можно внешнее дерево больше не растить, так как любой другой вход сделает решение недопустимым.
Вот и получается странно - когда мы уже знаем, что вход выбран оптимально (покрыл всё множество argmin(...)), то можно дерево заморозить, а у вас ставятся тормозащие штрафы на разрез, чтобы при этом раздувать внешнее дерево (а вершина посередине пути штраф вообще не видит ведь). Проблема в том, что target в A* штука не совсем умная и, например, может быть какой-то мощный поворот или объезд, где геометрию околопрямого пути пришлось существенно нарушить, вот от туда как раз и могут пойти отростки огромные, так как модификатор рёбер думает, что вы это сделали зря (ведь закрытая на ремонт или стоящая в мёртвой пробке дорога модификатору не видна) и что надо вас поправить и попытается найти какое-то решение пооптимальнее, при этом делая огроменный фронт поиске, ведь из-за поворотов расстояние уже большое и он будет рассматривать немало "потенциально лучших" путей.
Ой...да, не подумал, что выход тоже может быть из другого внутреннего графа. Но в таком случае ведь если запускать Дейкстру от Дейкстр (внутри стартового графа искать оптимальный и потом менее и менее оптимальный выход и с каждого такого менее оптимального выхода поочерёдно запускать A* во внешность, пока он не сломается (тупик) или не найдёт проезд), то граф плоский будет биться на компоненты связности (тупики) и одна из них всё-же дойдёт до второго графа внутреннего и для неё это будет корректный argmin, а значит решение будет допустимым. Если есть решение лучше, то только в выборе выезда из первой компоненты, а мы помним, что условие на argmin и там и там есть, так что оптимальность очевидна.
Единственная сложность такого подхода - временные окна, ведь у вас на самом деле решается обычная задача на графе трёхмерном с ориентированными рёбрами (рёбра в какие-то моменты времени есть, в какие-то нет, по времени движемся вверх с таким-то переходом на каждом ребре, пройдя вперёд-назад по одному ребру на самом деле проходим по двум рёбрам, каждое из которых отправляет немного в будущее на уровни выше) делится не факт что всегда на несвязные секции, которые друг друга не включают (один A* застрял в тупике и его компонента больше не трогается, другой A* дошёл до моста после того, как тот был заблокирован и теперь стоит в очереди на открытие, а вот третий приехал прямо перед открытием моста и они одновременно стартовали с тем который ждал, и получается, что их пути объединились (что глупо, так как мы дважды считаем одно и то же)).
Правило FIFO тут может подсказать кучу трюков, как этого избежать.
Тут для разделения (и, соответственно, экономии вычислений) можно, например, сделать запрещающие интервалы по времени по типу "тут до тебя с 8:40 стоял предыдущий A* и по итогу приехал к закрытому шлагбауму и поэтому ты появился, ты тут в 8:50 даже не думай ехать, зачем тебе считать путь до закрытого шлагбаума".
Например таким правилом со всего одной переменной на каждой вершине посещённой хоть кем-то, кого пришлось рестартнуть "кто проехал по ребру после 9:00 не доехал...кто поехал после 8:20 не доехал...кто поехал после 7:20 не доехал..." можно сделать так, чтобы трёхмерный граф разбился на независимые подграфы и, тем самым, не делал лишних вычислений.
А вот если делать штрафы на время, то вы как бы одновременно запускаете и того A*, который сможет дойти нормально (и на нём стоит остановиться, так как он выдаст min|argminANDargmin) и следующего и следующего и фронт растёт значительно, хотя какую-то его часть рассматривать смысла вообще нет. Более того, так как граф у вас трёхмерный (пусть и неявно), то эти деревья могут друг друга перекрыть (оба подъехали к мосту после закрытия и ждут, хотя логично что тот кто первый заехал успеет быстрее, либо оба не успеют).
Я так и не понял, как так получилось, что у вас существенное преимущество одного запуска большого. Это выглядит немного нелогично.
По-сути, весь граф разделён на (небольшую) внутренность, разрез и внешность (очень большую). Вы хотите найти путь min:s-p-t|p-t<p'-t, изначально вы запускали поиск от t до разреза, потом от s до входов на разрез (когда прошли все входы или лучший из доступных), дальше восстанавливали решение. Самое тормознутое - дерево от s до разреза (оно в ширь разрастись должно нормально так даже при использовании адекватных модификаторов весов как A*), так что как только он прошёл всё, что нужно, его тут же надо обрывать (так как ещё один шаг очень дорогой). Тут так и происходит, от границы внутрь решено всё уже, самое тяжёлое сейчас считается.
Во втором алгоритме вы вводите тормозящие штрафы, вот только пока алгоритм ждёт истечения штрафа на следующий вход, во внешности графа растёт огроменное дерево, которое его тормозит.
Если сравнить с первым алгоритмом, то вместо того, чтобы внешний поиск остановить, вы его продолжаете, при этом как бы запускаете внутренний поиск наоборот (от разреза в центр). Получается выигрыш на внутреннем графе (ведь вы не весь его считаете, а только кусочек, да и A* есть куда направить target. Но при этом проигрываете за счёт того, что огромное тяжеленное дерево всё это время растёт...и это при том, что если вы уже зашли с ближайшего входа, то внешнее дерево в принципе можно блокировать. Да, через границу из-за тормозящих штрафов ничего не пролезет, но при этом в остальной граф то оно всё полезет.
Но если внутренний граф такой уж плотный, может, стоит вместо перехода к этому огромному дереву объединить лучшее алгоритмов?
Например, дать дереву внешнему пройти до вершины номер 1 (или доказать, что пути нет и дойти до номера 2...и сказать, что лучше он найти не может и потом так же от этой вершины запустить поиск по внутреннему графу. По вычислениям получается в худшем случае так же (вам ведь нужно обосновать, что вход через разрез ближайший, иначе решение недопустимое), но скорее всего оно будет гораздо лучше, так как если он пройдёт 2 вход и 1 вход, внешнее дерево он как бы перестаёт постить (а оно огроменное).
Это оптимальное решение ищется за O(n!) или, если похитить, можно уложиться в
Но на практике ищут не точное, а просто хорошее решение, для этого придумывают эвристики, метаэвристики, приближённые алгоритмы и всё такое.
Из теоретических результатов на Кромивояжёра с метрикой есть 2opt алгоритм (есть модификация 3opt/2).
Здесь же ребята рассмотрели реализацию имитации отжига (довольно сильная эвристика, если применять её в правильных местах).
Пока нет, сейчас мы готовим новую работу к публикации, потом займёмся подготовкой старой (этой) но более расширенной. Как опубликуем (примерно через год, может чуть раньше), постараюсь ссылку в комментариях выложить не забыть.
Верно, это происходит автоматически, мы на "голове рыбки" увеличиваем веса и если рыбка часто формируется на одном месте, то добавляется достаточно большой добавок на рёбра чтобы подграф-ловушка перестал перетягивать на себя рыбку.
Варьируя этот добавок, можно поставить разную силу "успокаивания", чтобы подграф получал на рёбра довесок и становился непривлекательным.
Были и более аккуратные способы, позволяющие, например, получить результат не более r*opt (перебор немного упрощается в обмен на смещение оптимума, такой регуляризатор как бы) где r-гиперпараметр, но на практике смысла в них оказалось не много.
Можно записать задачу как ЦЛП булевую и если решать её как ЛП на [0,1], то решения будут выглядеть как разноцветные потоки суммарной мощности 1 (поток мощности 1 отправляется по s->t, поток мощности 1 из 1->2, мощности 1 из 2->t), но из-за того что у нас решается ЛП, то может поток разбиться, например, на два потока 0.5+0.5 и пойти по разным рёбрам и так соединиться с другими 0.5 потоками. Изначально пытались получить приближённый алгоритм перестройкой ЛП в допустимое решение и поняли, что за счёт того трюка можно получить неограниченную оценку на зазор целочисленности.
Согласен, слишком уж сократил.
Путь может пройти через одну и ту же вершину только один раз.
Без пересечений путь будет допустимым, допустимый+оптимальный -> np-h, мы же немного ослабляем допустимость, с этой постановкой ковыряется и получаем необычный ускоренный переборщик (который потом перестраиваем в метаэвристику по поиску просто хорошего решения).
1,2 - это порядок обхода обязательных вершин, путь получается как s->1->2->3->t с промежуточными вершинами без маркеров.
Разделения на подграфы и нет, я просто описываю как алгоритм ложится (он находит подграф-ловушку, зацикливается на него и начинает люто ветвиться по рёбрам, в таком случае мы настраиваем веса новые так, чтобы такой подграф-ловушка перестал его интересовать). В самом деле, напоминает немного A*, только у них оптимальность не ломается, а тут он как бы отказывается постепенно смотреть какие-то подграфы, где вообще-то могло спрятаться оптимальное решение. Например, если вы в хорошем разреженном графе воткнёте посредине клику с малыми весами и подгоните пути, то алгоритм застрянет на переборе рёбер клики, пытаясь выжать лучше и лучше, мы же его потихоньку успокаиваем и говорим, что в клике этой он и так хорошо поковырялся уже и надо начинать её избегать, это позволяет выводить ветвление из таких нехороших подграфов.
Если очевидную ЦЛП перевести в ЛП, то целочисленный зазор в худшем случае станет неограниченно большим, что показано на примере (если путь может разбиться на нецелочисленные, то он пойдёт дешёвым путём, а вот просто путь без этого допущения не пройдёт там и пойдёт в обход по дорогому пути).
С детекцией - да, надо было объяснить получше, но, в принципе, можно догадаться, что если я не акцентирую внимание на конкретной рыбке, то можно брать для ветвления любую (я брал первую встретившуюся). Но тут вы правы - я зря про это не рассказал.
Нашли ускоренный переборный (точный) алгоритм и потом переделали его в метаэвристику (с потерей оптимального решения в обмен на быстрое получение достаточно хорошего).
Релаксация это снятие или ослабление каких-то условий, тут мы условие на непересекаемость пути по вершинам заменили на "рыбковость" и крутили дальше.
NP трудность для 2 вершин доказывается очень непросто, когда число обязательных вершин является элементом входа, можно свести напрямую к 3cnf через хитрый и красивый трюк (о котором, возможно, я сделаю отдельный разбор в будущем). Более того, можно доказать (если число обязательных вершин - это элемент входа), что задача неаппроксиммируема с любым множителем (как Кромивояжёр без метрики), доказательство основано на NP трудности и конструкции похожей на то, чем тут доказывается неограниченность ЦЛП-ЛП зазора. Возможно, в будущем сделаю на это всё разбор.