Comments 35
Просто интересно, а сколько там всего суммарно вершин и дуг в графе всех дорог мира?
И есть вопрос про двусторонний A*. А можно поподробнее остановиться на доказательстве корректности критерия остановки? Почему после первого касания, достаточно рассмотреть только все дуги между двумя "волнами"?
Ясно, что в случае, если все вершины графа поделены между двумя волнами, то такой алгоритм найдет кротчайший путь, ведь кратчайший путь можно разбить на 2 куска — в первой доле и во второй, плюс ребро между долями, и настоящий кратчайший путь в рассмотренные попадет.
Но, что, если в графе есть еще нераскрытые вершины? Почему кратчайший путь не может проходить через них?
Просто интересно, а сколько там всего суммарно вершин и дуг в графе всех дорог мира?
Примерно сотни миллионов дорожных фичей в OpenStreetMap (https://taginfo.openstreetmap.org/keys/highway#overview). Далее, в среднем 5-7 сегментов на фичу. Т.е. грубо получается 1-2 миллиарда вершин графа дорог. Можно, уменьшить кратно их кол-во рассматривая в качестве вершин только перекрестки. Такой подход не позволит по-простому реализовать разворот в произвольном месте, где он возможен, но он вполне оправдан. Развороты при таком подходе будут возможны только на перекрестках.
И есть вопрос про двусторонний A*. А можно поподробнее остановиться на доказательстве корректности критерия остановки?
Отличный вопрос! Я изначально думал это написать в статье, но она оказалась и без того достаточно объемной. Предлагаю так. Я или напишу ответ на Ваш комментарий, где покажу, корректность алгоритма. Или напишу отдельную статью на эту тему. Как продолжение к этой статье.
Если вы собираетесь формально это доказывать, да еще добавите более детальное описание алгоритма (скажем, псевдокод), то это определенно потянет на целую статью.
Кажется без описания алгоритма не обойтись, если писать статью и доказательство. Я наверно, так сделаю. Завтра или после завтра напишу не большой набросок, в какую сторону смотреть, прямо в этой ветке. А статью уже позже и отдельно. Спасибо, за замечание!
А, погодите. Я что-то затупил. Оно же элементарно доказывается в одно предложение:
Кратчайший путь не может проходить через нераскрытую обеими волнами вершину, потому что этот путь будет не короче пути через вершину-пересечение волн (потому что каждая половинка этого пути не короче соответствующей половинки пути через точку пересечения внутри волны, а это так по свойству "волны" А*).
Но все-равно, формальное доказательство от начала и до конца, да техническое описание алгоритма будут не лишними.
1. Для двунаправленного поиска есть довольно тонкий момент, что неизвестно время прихода на финиш, что важно для оценки пробок. Соответственно, обычно для финиша берется какое-то предсказание, которое может не совпасть с реальным и две волны встретятся в разное время. Для решения проблемы, наверное, нужно продолжать гнать прямую волну, а результаты обратной использовать как эвристику
2. В OSRM есть второй алгоритм - multi-level dijkstra (MLD). Он позволяет обновлять индекс на лету, но тут тоже сильно будет зависеть от скорости устройства и объема данных
1. Для двунаправленного поиска есть довольно тонкий момент, что неизвестно время прихода на финиш, что важно для оценки пробок...
Это правда очень тонкий момент и интересное наблюдение. Кажется этот момент важен при условии, что у нас есть какая-то эвристика позволяющая оценить пробки в будущем. Тогда односторонний A* (только прямая волна) позволит нам их учесть. А для двухстороннего придется придумывать предсказание для финиша. Да еще такое предсказание, чтоб эвристика A* не дала переоценки. У нас были пробки только в текущий момент времени, так что я не столкнулся с указанной проблемой.
2. В OSRM есть второй алгоритм - multi-level dijkstra (MLD). Он позволяет обновлять индекс на лету, но тут тоже сильно будет зависеть от скорости устройства и объема данных
Да. Это правда. Но MLD в OSRM появился в 2017, а мы реализовывали поддержку пробок в Maps.me в 2016.
Спасибо за комментарии!
Можно ли придумать какой-то частичный индекс?
Добавление второй волны как улучшает оценку сложности в среднем случае?
На ассимптотическую сложность оно не влияет. Но, как A* в среднем работает быстрее Дейкстры на реальных графах, так и двунаправленный A* работает на них быстрее простого A*. Это эвристическая оптимизация.
Надеюсь, автор приведет примеры с конкретными числами.
Добавление второй волны как улучшает оценку сложности в среднем случае?
Кажется, что просто на константу. Но на большую. Приведу довольно грубые рассуждения для Дейкстра, которые наводят на такую оценку.
Допустим у нас есть граф, вершины которого распределены равномерно на плоскости. Допустим от старта до финиша R метров.
Рассмотрим односторонний Дейкстра на этом графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины на круге с центром в старте. Площадь круга будет Pi*R^2.
Представим двусторонний Дейкстра на этом же графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины в кругах вокруг старта и финиша. Площадь каждого R/2. Суммарная площадь, на которой раскрыты вершины будет: 2*Pi*(R/2)^2 = (Pi*R^2)/2.
Т.е. в этом частном случае, кол-во раскрытых вершин уменьшиться в двое.
Это не ответ на вопрос. Кол-во раскрытых вершин удобно использовать для оценки сложности алгоритма роутинга, но это не сложность в среднем. И эти рассуждения актуальны для Дейкстра, но не для A*. Я подумаю, над более точным ответом.
Можно ли придумать какой-то частичный индекс?
Уточните п-та вопрос. Индекс, который мог бы обновляться при обновлении весов дуг графа?
Здравствуйте, уважаемый автор.
Хотите ли вы получить алгоритм, который будет асимптотически в
бесконечность раз быстрее описанного вами в статье для графов на плоских картах
и требовать только где-то в ln (числа ребер) раз больше памяти?
Это не фантастика: граф дорог не произвольный, а специальной
структуры (вершины лежат на плоскости, ребра не сильно отличаются
от геодезических, скорости сопоставимы). Наверно, такие алгоритмы даже где-то
даже описаны. Но если нет, и у вас есть желание, возможность и уверенность
в вашей способности вести математические исследования,
я бы мог вам в них помочь.
С уважением.
асимптотически в
бесконечность раз быстрее описанного вами в статье
Это как? Какая же ассимптотика вашего алгоритма? Как она в бесконечность раз быстрее O(E log V)?
Наверно, такие алгоритмы даже где-то
даже описаны.
Полно алгоритмов для планарных графов описано. Я бы не надеялся что ваш алгоритм что-то уникальное и новое.
вершины лежат на плоскости, ребра не сильно отличаются
от геодезических, скорости сопоставимы
А вот тут неправда. Шоссе, эстакады, тоннели, изогнутые дороги, серпантины и еще куча всяких исключений. А еще ПДД все портят: Какой-нибудь перекресток где с одной дороги можно поворачивать только налево, а с другой во все стороны — планарным графом особо не задашь.
1 да быстрее, правдопобно получить вплоть до O(ln(E)*ln(v)), все зависит от класса графов
.
2. В задаче граф не планарный, однако он почти метрически отображен на плоскость.
.
3.См 2
Сергей, спасибо за комментарий и за предложение!
Вы говорите про алгоритм с индексом или без?
Вы пишите про вершины, лежащие на плоскости ребра. П-та уточните, что имеется ввиду. Существенная доля вершин лежит в плоскости ребра? Верно?
Вы пишите, скорости сопоставимы. Если говорить про дорожную сеть, то формально есть дороги без ограничений. Правда их не много. Но в реальности скорости на дугах часто отличаются раз 20.
Состояние дел с прокладкой маршрутов по графам дорог не плохо было описано в этой обзорной статье: https://arxiv.org/pdf/1504.05140.pdf . Вероятно, там есть что-то похожее и вашу задумку. Если да, то скажите п-та какой это алгоритм. Если нет, но напишите п-та поконкретнее в чем идея.
Коллеги, обзорная статья 2015 года. Если у кто-то знает более новую подобную статью - пришлите ссылку п-та.
1.Пожалуйста :)
.
2. Структура данных не главное в потенциальном решении.
.
3. Да не "в плоскости ребра" а сами вершины и ребра лежат на плоскости. Реальные дорожные графы имеют еще кучу особых признаков, особенно в отношении "локальности".
.
4. Думаю, эту проблему можно решить за счет масштаба.
.
5. В плане научного поиска уже существующих решений ваши навыки на голову превосходят мои. Наверное, то, что я имею ввиду должно быть похоже на Geometric Containers, Precomputed Cluster Distances и из вашей ссылки. Всю статью и ссылки не смотрел, но там явно что-то побыстрее (асимптотически в бесконечность раз) A* алгоритма есть.
.
6 Идея в многоуровневом масштабном представлении графа и последовательного вычисления возможных путей с более масштабных и грубых представлений в сторону более мелких и точных. Предположительно после завершения каждого этапа вы будете иметь некоторую узкую полосу для возможного пролегания вашего кратчайшего пути на графе следующего по мелкости уровня представления.
асимптотически в бесконечность раз
Вы используете термины слишком небрежно. Эта фараза не имеет смысла. Если оценка O(lnE lnV) истина, то не в бесконечность, а всего-то в E/lnE раз быстрее.
Сергей.
Действительно граф дорог имеет ряд интересных особенностей. Он почти планарный (мостов и туннелей не так много.) И еще длинные маршруты почти всегда строятся через очень ограниченное число быстрых дуг (через магистрали). Наличие таких быстрых дуг эксплуатируется в алгоритмах, указанных вами, а так же в Contraction hierarchies, Reach и ATL. Это очень быстрые алгоритмы прокладки маршрута с очень асимптотической сложностью.
Например, Contraction hierarchies - O(sqrt(n) * log(n)), где n кол-во вершин (https://en.wikipedia.org/wiki/Contraction_hierarchies)
Reach - тут сложность зависит от обучающей выборки, но на практике, говорят что результаты хорошие. Я сам Reach не реализовывал и не работал с ним.
К сожалению все эти алгоритмы требуют подготовки индекса перед началом работы. Например, подготовка индекса для Contraction hierarchies требует O(n^2 * log (n) + n*m, где n это кол-во вершин, а m - это кол-во ребер. Индекс имеет существенный размер и считается не быстро. Для карты мира, на хорошем сервере порядка суток занимало.
Сергей, мне кажется, что ваша задумка близка к одному из указанных алгоритмов. Вероятно, к Reach, если я правильно понял. Это очень хорошая и перспективная идея. Если посмотреть, на Reach, то к сожалению, чтоб понять, насколько сильно нужно стремиться к быстрым дорогам, нужно знать, насколько близко вершина лежит от быстрых дорог. А это предрасчет и индекс.
Сложность в среднем O(ln(m)*ln(n)) - выглядит очень круто. Хотя, как я отмечал ранее, в случае поиска кратчайшего пути на графе, желательно оговаривать, о каких дугах и вершинах мы говорим. Поскольку старт и финиш могут быть близко на огромном графе. И для расчета требуется затронуть маленькое число дуг относительно всего графа.
На всякий случай, вот статья с кратким описание сути Reach и ряда других алгоритмов: https://habr.com/ru/companies/2gis/articles/326638/
Спасибо за развернутый ответ.
Я изначально писал, что скорее всего уже есть, уж слишком очевидная идея.
Да, я подразумевал, что требуется подготовка и задача поиска будет решаться затем много раз. Видите, вы с этой областью работаете, если решение есть и оно
для ваших целей не подходит, то значит так оно и есть. Если бы вдруг не было, можно было бы поискать. Хотя стоит подумать над какой-то модификацией: бывает "в лоб" - нельзя, а "в обход" - можно.
Желаю вам свежих идей и вдохновения их реализовывать!
Не понял куда смотреть в код чтобы посмотреть эвристики. Не пробовали эвристики менять, чтобы ещё сильнее оптимизировать это дело? Выглядит будто эвристика плохо справляется с сортированием нод, раз там такое количество разбега во все стороны.
Посмотреть в код стоит вот сюда:
А так же можно и вот сюда:
Не пробовали эвристики менять, чтобы ещё сильнее оптимизировать это дело?
Пробовали. Там иначе переоценка получается. Так же пробовали ALT.
Выглядит будто эвристика плохо справляется с сортированием нод, раз там такое количество разбега во все стороны.
Поясните п-та.
На первом скриншоте количество точек примерно равномерно распределено вокруг точки назначения, что подсказывает, что либо точки складывают в обычную очередь и алгоритм из A* сваливается в какой-то DFS, либо эвристика крайне плохо работает и приоритет обработки вершин не смотрит на абсолютную дистанцию между вершинами и точкой назначения. В обычной ситуации A* должен был явно сделать "наклон" в сторону пункта назначения, что не слишком заметно на исходном скриншоте.
С другой стороны без каких-нибудь heatmap доказать я этого не могу т.к. картинка точно не рисует все 90к точек. Возможно на геоданных ещё какие-то нюансы всплывают и отображение вцелом некорректно из-за искажений карты.
А такой вопрос - консистентность эвристики в данном случае в чём заключается? Делает один и тот же путь если поменять местами назначение и отправление?
алгоритм из A* сваливается в какой-то DFS
Но A* никогда не сваливается в DFS. Он сваливается в Дейкстру, если эвристики нет. Что выраждается в BFS, если все ребра одинаковой длины. Но DFS тут никак не получить.
консистентность эвристики в данном случае в чём заключается?
Эвристика A* консистентна, если она никогда не переоценивает длину оставшегося пути.
На первом скриншоте количество точек примерно равномерно распределено вокруг точки назначения
Уточните п-та на каком скриншоте. Картинка с раскрытыми 90К вершинами есть на 1-й и на 3-й иллюстрациях. Вершины вокруг точки назначения - это вторая картинка на 3-й иллюстрации. И на ней не 90К, а 30К вершин раскрыто.
Комментарий про DFS и переоценку A* уже написал @wataru Спасибо!
Тот что рядом с Дийкстрой на 340к и одним направлением.
На этой картинке одна волна от старта к финишу. Классический A*. В нем используется стандартная эвристика: берется расстояние по прямой (на поверхности земли, без учета рельефа) и делится на максимальную скорость.
На примере видно, что есть преимущество перед алгоритмом Дейкстры. Так же видно, что волна ушла к финишу в двое дальше, чем в противоположенном направлении.
Так же на распространение волны очень влияет, есть ли быстрые дороги в регионе прокладки. Если присмотреться, то можно заметить, что именно по магистралям были раскрыты вершины в низу и в направлении от старта.
Можете пояснить про мьютекс - зачем там нужна блокировка? Нельзя ли для целей отслеживания/проверки завершения снарядить еще 1 поток, который бы получал обновления из потоков поиска и останавливал их, если обнаруживал критерий завершения? Да, это потребовало бы памяти, но избавило бы от блокировок.
Спасибо @v0stok86!
Да. Я не думал, о таком варианте. И это вариант, вполне можно протестировать. Отказаться от мьютекса это серьезный плюс. Так же хочу отметить, что используя третий поток, мы слегка изменим момент остановки алгоритма. Он может наступить, чуть позже, чем пересекутся волны. Но это, кажется, не должно повлиять на корректность алгоритма, насколько я помню доказательство.
С другой стороны, добавив 3й поток мы получим следующие минусы:
Нам нужно будет копировать приличный объем данных между потоками. Раскрытые вершин много на больших графах.
Нам нужно будет как-то наладить передачу данных о раскрытых вершинах в третий поток из двух рабочих потоков. Как вариант - очередь. Это тоже накладные расходы.
Хорошо бы, чтоб под 3й поток, было отдельное ядро. (Его может не быть на мобильных устройствах.)
Усложнится система.
Но тут, нужно реализовывать и мерить. Может и лучше окажется.
Мой добрый приятель и бывший коллега (@kshalnev) уже после публикации статьи, придумал очень интересную штуку, как уменьшить проверки под мьютексом. Идея применима к любому графу, но опишу ее в терминах графа дорог. Идея в следующем.
Перед запуском алгоритма считаем расстояние между стартом и финишем.
У нас есть консистентная эвристика для A*. А это значит, мы можем понять, сколько времени минимально может потребоваться, чтоб добраться из старта в финиш. По сути, в терминах карты, это время, чтоб доехать из старта до финиша по прямой дороге, на максимально скорости.
Пока в раскрытых вершинах от старта и от финиша у нас меньше половины этого времени - не проверяем, что волны пересеклись. И следовательно не выполняем долгой проверки под мьютексом. Действительно, чтоб волны пересеклись, в одной из волны мы должны рассматривать вершины, в которых будет сохранено время большее, чем половина самого быстрого.
Кажется это может ускорить работу алгоритма. Более того, кажется, что не проверять, что волны пересеклись можно и дольше. И это тоже не должно повлиять на корректность алгоритма.
Вот бы посмотреть на статистику, собранную мапсми - сколько ядер было на устройствах, где запускалось приложение.
Да. Это правда интересно. Такую статистику я не помню, да и помнил бы, написать не смог. Но по опыту могу сказать, что ядер очень часто больше двух. Например, один из девайсов, на котором я делал тесты выше iPhone SE (2016 год), на момент выпуска был не особенно мощным. Но в нем уже два ядра. Насколько я помню, даже на low-end девайсах последние годы обычно 2-4 ядра, если не больше.
Реализация двустороннего A* на двух потоках