На Хабре можно найти немало статей, посвящённых оптимизациям поиска кратчайшего пути на графе. Я расскажу ещё про один подход. Речь пойдёт о распараллеливании алгоритма A* и исполнении его на двух потоках, а также о сложностях, с которыми я столкнулся при реализации, и их преодолении.
Причины выбора A*
При поиске маршрута в навигационных приложениях используются алгоритмы поиска кратчайшего пути на графе дорог. Таких алгоритмов немало, и они отличаются по характеристикам. Рассмотрим те из них, которые ищут кратчайший путь между двумя вершинами или дугами графа дорог.
С одной стороны, есть алгоритмы, которые работают только с графом дорог и не требуют предварительно готовить индекс на основе этого графа. Это алгоритм Дейкстры, A* и им подобные. С другой стороны, есть алгоритмы, которые требуют генерации большого индекса на основе графа перед началом расчёта маршрутов. Наиболее радикальный вариант: посчитать и запомнить кратчайшие пути, соединяющие все дуги графа со всеми дугами. Такой подход потребует огромного индекса, но зато маршруты в среднем будут вычисляться за константное время. Точнее, за время поиска по ключу, состоящему из старта и финиша в хеш-таблице.
Очень многие современные алгоритмы реализуют нечто среднее между этими двумя подходами, то есть индекс вычисляется на основе графа. Он много меньше, чем все кратчайшие пути вместе взятые, но всё же существенного размера. Затем вычисляются маршруты с использованием графа дорог и индекса. У Contraction Hierarchies относительно небольшой индекс и быстрая скорость вычисления. Именно этот алгоритм использовался в Maps.me до того, как нам понадобилось поддерживать прокладку маршрута с учётом пробок и прокладку маршрута в объезд, паромов, магистралей, грунтовых дорог и т. п. по выбору пользователя. Пока не требовалось поддерживать эти функции, мы адаптировали для работы на мобильной платформе реализацию Contraction Hierarchies из библиотеки OSRM. Индекс занимал 15-25 % от объёма всех данных, хранящихся в карте. В сумме, для всех карт мира индекс занимал дополнительно несколько гигабайтов.
Если использовать какой-нибудь из алгоритмов поиска кратчайшего пути с индексом и поддерживать возможность для пользователя исключать из прокладывания маршрута некоторые типы дорог, например, магистрали или грунтовки, то возникает серьёзная проблема: количество индексов будет удваиваться при добавлении каждого нового типа дорог. Maps.me — это оффлайн-карта, работает без интернета. Мы всё считали на смартфоне и не могли себе позволить держать на нём несколько индексов. Кроме того, не кажется правильной реализация, когда в ней потребление ресурсов начинает расти как 2^n, даже если n пока не очень большое число.
С поддержкой пробок у алгоритмов с индексом тоже возникают сложности. Учёт пробок означает необходимость динамически менять вес дуг графа дорог, каждые несколько минут. А это означает, что если используется алгоритм поиска кратчайшего пути с индексом, то этот индекс должен быть пересчитан после каждого обновления пробок. Пересчитывать его на сервере и скачивать на устройство для прокладки маршрута не выйдет. Во-первых, он долго вычисляется даже на сервере, во-вторых, он большого размера. Прокладывать маршрут на сервере и закачивать его в Maps.me — возможный вариант. Но, как я отмечал ранее, Maps.me вычиляет маршрут на устройстве. То есть, скачав пробки программа может использовать их позже, даже если нет связи с сервером.
Именно поэтому мы были вынуждены посмотреть в сторону алгоритмов поиска кратчайшего пути без использования индекса. И когда стало необходимо поддерживать пробки и потребовалась возможность прокладки маршрута в объезд паромов, грунтовых дорог и т.п., мы перешли на A* и разные оптимизации этого алгоритма.
Про граф дорог
Я много работал с прокладкой маршрутов в Maps.me, поэтому буду писать не про абстрактный математический граф, а про граф дорог мира. Точнее даже про граф дорог OpenStreetMap, именно эти карты используется в Maps.me.
A* в классическом варианте
A* — это один из алгоритмов поиска кратчайшего маршрута на ориентированном графе. По сути, это расширение известного алгоритма Дейкстры. Главное отличие в том, что алгоритм Дейкстры рассматривает только ближайшие вершины вокруг старта, пока волна раскрытых вершин не дойдёт до финиша. A* же учитывает, где находится финиш и рассматривает вершины графа преимущественно в его сторону. Это позволяет раскрыть в среднем меньше вершин для нахождения кратчайшего пути. Разница хорошо видна на иллюстрации ниже, это маршрут длиной 53 км проложенный во Франции:
Двусторонний A*
При работе A* волна раскрываемых вершин идёт от старта к финишу. Можно запустить аналогичную волну от финиша к старту, при этом две волны будут двигаться навстречу друг другу. Тут есть несколько тонких моментов.
Во-первых, в случае прямой волны (запущенной от старта к финишу) мы ищем исходящие дуги для раскрытия вершин. А в случае обратной волны (от финиша к старту) мы должны искать входящие в вершины дуги для раскрытия вершин, это нужно для сохранения симметричности алгоритма.
Во-вторых, желательно написать тесты для функций, которые для графа возвращают исходящие из вершины и входящие в вершину дуги. Это важная проверка на корректность. Остановлюсь на этом чуть подробнее. Рассмотрим простой ориентированный граф с тремя вершинами и четырьмя дугами:
Теперь проверим:
Получаем исходящие дуги для вершины A: AC и AB.
Далее получаем дуги, входящие в вершины C и B.
Для вершины C входящие AC и BC. Убеждаемся, что среди входящих в C есть дуга, исходящая из A — AC.
Для вершины B входящая дуга AB. В общем случае нужно убедиться, что среди входящих в B есть дуга, исходящая из A. Но в данном случае в В входит только AB, это и есть искомая дуга.
Такую проверку желательно сделать для существенной части вершин графа. Это даст уверенность, что методы получения исходящих и входящих дуг работают корректно.
Такие тесты особенно важны, когда на получение исходящих и входящих дуг влияет множество факторов, как это бывает в случае реального графа дорог.
В-третих, сейчас мы рассматриваем двухстороннюю версию A*, запущенную в один поток. Это значит, что в этом потоке поочередно должны раскрываться вершины в прямой волне (от старта) и в обратной (к финишу). Имеет смысл раскрывать не по одной вершине каждой из волн, а по несколько десятков или сотен, и только затем переключаться на вершины другой волны. Переключение с одной волны на другую требует времени (вычислительных ресурсов). Расскажу об этом немного подробнее, поскольку когда разговор пойдёт о двухпоточной версии двустороннего A* мы как раз будем бороться с этими потребителями ресурсов.
Итак, на что уходит время при переключении с волны на волну? Главный потребитель времени при движении волны это обращение к графу дорог. Он большой и хранится на диске, к которому нужно обращаться за вершинами. Кроме графа в ряде случаев нужно обращаться к другим структурам данных, например, к информации о высоте дуги над уровнем моря. Всё это тоже хранится на диске. В случае Maps.me есть и другие явные и неявные чтения с диска. При работе A* есть большая вероятность, что мы обратимся к данным каждой вершины не один раз. А если так, то имеет смысл их кешировать. К тому же данные эти разной природы, поэтому и кешей может быть несколько. Крайне желательно сделать хотя бы основные кеши отдельно для каждой волны. Особенно, если вычислять маршрут нужно на мобильном устройстве и нет возможности сильно увеличивать размер кешей. Если же кеш один и не очень большой, то одна волна будет очищать его от элементов, нужных другой волне, и наоборот. Если он общий для двух волн, то при каждом переключении волны будет обновляться. С другой стороны, в случае реализации двустороннего A* в один поток реализация всех кешей для каждой волны может оказаться неоправданно ресурсозатратной. Однако, в случае двухпоточной реализации двустороннего A* для каждой волны должны быть свои кеши, иначе ещё и придётся синхронизировать доступ к ним, а это тоже весьма накладно.
В-четвёртых, критерий остановки алгоритма несколько сложнее, чем в случае одностороннего A*. Первая точка соприкосновения прямой и обратной волны может не являться точкой, соединяющей два участка оптимального маршрута, и для подбора наилучшего маршрута требуется продолжить вычисления. Подробнее об этом я расскажу ниже. Однако, если волны уже пересеклись, то останется немного работы, чтоб найти маршрут. Так что в среднем количество раскрытых вершин у двустороннего А* окажется существенно меньше, чем у простого A*. Вот уже знакомый нам маршрут, проложенный A* и двухсторонним A*:
A*: раскрыто 90 803 дуг графа.
Двухсторонний A*: раскрыто 32 589 дуг графа.
Двусторонний A* в два потока
А вот теперь после небольшой разминки мы подошли к самому интересному. Прямая и обратная волны могут делать вычисления почти независимо, пока не сойдутся. То есть при наличии процессора с двумя или более ядрами можно ускорить прокладку маршрута.
Прежде всего несколько замечаний по реализации такого подхода.
Если граф небольшой, то его можно загрузить в память. Тогда данные, необходимые для прокладки маршрута (входящие в вершины дуги, исходящие из вершин и прочее), будут читаться без модификации вспомогательных структур для работы с графом. То есть граф можно загрузить в память, а затем запустить две волны A* на двух потоках и обращаться к графу за данными без средств синхронизации, просто на чтение. К сожалению, при расчёте маршрута по графу дорог мира на мобильных устройствах так сделать не получится, потому что он не поместится в память целиком. А это значит, что нужно подгружать граф во время прокладки, при достижении волнами A* не загруженных частей графа. Для такой подгрузки нужна синхронизация. Однако несложно реализовать алгоритм прокладки маршрута таким образом, что синхронизация потребует не очень много ресурсов.
Как отмечалось ранее, при однопоточной реализации двустороннего A* желательно иметь отдельные кеши для прямой и обратной волн. При двухпоточной реализации это становится обязательным. В кешах хранятся данные, к которым приходится обращаться часто, и их синхронизация сильно замедлит работу. Кроме того, элементы одной волны, будут вытеснять из кеша элементы другой волны, увеличивая риск непопадания в кеш. Так что для прямой и обратной волны нужно всё кешировать отдельно. Подробнее про кеширование я писал выше в главе про однопоточную реализацию двустороннего A*.
Когда волны A* распространяются навстречу друг другу есть место, где никак не обойтись без объекта синхронизации. Это проверка, не пересеклись ли волны. Эту проверку нужно делать при каждом раскрытии вершины, каждой из волн. Ее суть очень проста. Надо посмотреть, есть ли раскрываемая вершина, среди раскрытых вершин противоположной волны. Тут основная сложность в том, что нам нужно взять мьютекс и под ним поискать раскрываемую вершину одной волны среди раскрытых вершин другой волны. Кажется, что это может очень заметно сказаться на эффективности поиска кратчайшего пути. Поскольку количество раскрытых вершин может быть существенным. Тесты показали, что данный объект синхронизации сказывается на эффективности, однако не критическим образом.
Замечание о корректности работы двухстороннего A* на двух потоках
Предложенная оптимизация существенным образом меняет классический алгоритм A*. Она также несколько отличается от двухстороннего A* в варианте, когда вершины раскрываются по одной из каждой волны. В подобных ситуациях важно доказать, что корректность работы сохранена, или понять, что у нас получился не точный алгоритм, а эвристика. Доказательство корректности должно учитывать весь спектр вариантов возможной работы алгоритма. Например, вся работа будет выполнена прямой или обратной волной. Или волны могут сойтись где-то посередине, что наиболее вероятно. Как пойдёт выполнение двухстороннего A* на двух потоках зависит от выделения им процессорного времени.
Можно показать, что после предложенных изменений алгоритм сохранит свою корректность. Хорошее доказательство корректности двухстороннего A* через потенциалы есть в рамках курса “Algorithms on Graphs” на Coursera. Достаточно немного его модифицировать и мы получим доказательство двухпоточной версии алгоритма.
Критерий остановки работы алгоритма
Я старался не описывать подробности работы алгоритмов, но на одном важном моменте в работе двухстороннего A* всё же остановлюсь. Как я отмечал выше, точка, в которой сошлись прямая и обратная волна двухстороннего A*, может не являться точкой кратчайшего маршрута. То есть, исходя из алгоритма, от старта до точки, где волны сошлись, рассчитан кратчайший путь, и от этой точки до финиша — тоже кратчайший. Тем не менее, кратчайший путь от старта до финиша может обходить точку, в которой волны сошлись. Покажу на простом примере. Рассмотрим ориентированный граф:
Будем искать маршрут при помощи двухстороннего A* из точки S в точку F. Цифрами обозначены веса дуг, буквами — вершины графа. После первого шага прямой волны (от старта) и обратной волны (от финиша) граф выглядит так:
Тёмным цветом обозначены раскрытые вершины, то есть такие, до которых уже найден кратчайший путь. Под вершинами подписано, какой суммарный вес дуг надо пройти, чтоб добраться по кратчайшему пути от старта до вершины, и аналогично для обратной волны. После того, как прямая и обратная волны сделают ещё один шаг, граф будет выглядеть вот так:
После третьего шага:
В этот момент прямая и обратная волны сходятся в вершине B, то есть она раскрыта и прямой, и обратной волной. Это момент, когда нужно останавливать движение волн навстречу друг другу. Но кратчайший путь из S в F нельзя составить из кратчайших путей из S-В и B-F, то есть путь S-A-B-C-F не кратчайший, его вес 8. Как видно из примера, кратчайшим будет S-A-C-F весом 7, в обход B:
Пример демонстрирует, что критерий остановки двухстороннего A* несколько сложнее, чем у одностороннего A*. В общем случае можно показать, что критерий остановки и получения кратчайшего пути следующей:
Прямая волна движется от старта, а обратная от финиша до момента, пока прямая волна не раскроет первую раскрытую вершину обратной, или наоборот. Выражаясь иначе, волны движутся навстречу друг другу, пока не пересекутся.
После первой общей раскрытой вершины волны останавливаются.
Найдём самый короткий (самый лёгкий) из маршрутов, который начинается в одной из раскрытых прямой волной вершин, далее одной дугой соединяем его с раскрытыми от финиша вершинами обратной волны.
Замечу, что если следовать алгоритму описанному выше, то маршрут, проходящий через вершину B, будет рассмотрен пункте 3 наравне с другими. А именно, после того как прямая и обратная волны алгоритма сойдутся мы должны рассмотреть следующие маршруты:
После чего будет выбран самый короткий (легкий) маршрут — SACF.
Результаты тестов
Для тестов эффективности я использовал исходный код Maps.me и версию, в которой распараллелил двухстороний A*. Использовалось два смартфона: iPhone SE 2016 (двухъядерный процессор) и Samsung Galaxy S10e (восьмиядерный процессор). Ниже результаты, которые получились для пешеходного протяжённого маршрута Москва (Тушино) — Таруса. Время прокладки в таблице — это среднее время четырёх прокладок маршрута в миллисекундах.
Использование двух потоков для прокладки маршрута на Samsung Galaxy S10e дало большее ускорение, чем на iPhone SE. Думаю, это связано с тем, что на S10e восемь ядер, и два из них могли быть выделены под прокладку маршрута полностью, в то время как у iPhone SE ядер всего два и во время прокладки маршрута они могли выполнять какую-то другую работу.
В каких случаях есть смысл в расчёте двухстороннего A* на двух потоках?
Есть ситуации, когда такая оптимизация неоправдана. Как видно из тестов и из логики реализации, синхронизация расчёта кратчайшего пути на двух потоках отнимает ресурсы. Если требуется повысить количество ответов в секунду (RPS), а максимально быстрым временем ответа можно пожертвовать, то имеет смысл использовать двухсторонний A* в один поток, чтоб не тратить ресурсы на синхронизацию при работе алгоритма.
Если же важно максимально ускорить прокладку маршрута, то имеет смысл распараллеливать на два потока двухсторонний A*. Тесты показывают, что при разумном подходе к синхронизации это позволяет выиграть десятки процентов, загрузив два ядра во время расчёта маршрута.
Ссылки:
Исходные код Maps.me: https://github.com/mapsme/omim/
Курс Algorithms on Graphs на Coursera: https://www.coursera.org/learn/algorithms-on-graphs
Хочу поблагодарить за ценные комментарии и редактирование этой статьи Ольгу Хлопкову (@Serine), Татьяну Ян (@tatiana_k), Анастасию Гутор (@AnastasiaGutor) и Павла Бабакова.
Статью посвящаю замечательной команде, с которой работал над проектом Maps.me в Mail.ru Group с 2014 по 2020.
Комментарии (34)
wslc
15.05.2023 10:31+11. Для двунаправленного поиска есть довольно тонкий момент, что неизвестно время прихода на финиш, что важно для оценки пробок. Соответственно, обычно для финиша берется какое-то предсказание, которое может не совпасть с реальным и две волны встретятся в разное время. Для решения проблемы, наверное, нужно продолжать гнать прямую волну, а результаты обратной использовать как эвристику
2. В OSRM есть второй алгоритм - multi-level dijkstra (MLD). Он позволяет обновлять индекс на лету, но тут тоже сильно будет зависеть от скорости устройства и объема данных
BykoIanko Автор
15.05.2023 10:31+11. Для двунаправленного поиска есть довольно тонкий момент, что неизвестно время прихода на финиш, что важно для оценки пробок...
Это правда очень тонкий момент и интересное наблюдение. Кажется этот момент важен при условии, что у нас есть какая-то эвристика позволяющая оценить пробки в будущем. Тогда односторонний A* (только прямая волна) позволит нам их учесть. А для двухстороннего придется придумывать предсказание для финиша. Да еще такое предсказание, чтоб эвристика A* не дала переоценки. У нас были пробки только в текущий момент времени, так что я не столкнулся с указанной проблемой.
2. В OSRM есть второй алгоритм - multi-level dijkstra (MLD). Он позволяет обновлять индекс на лету, но тут тоже сильно будет зависеть от скорости устройства и объема данных
Да. Это правда. Но MLD в OSRM появился в 2017, а мы реализовывали поддержку пробок в Maps.me в 2016.
Спасибо за комментарии!
Orient
15.05.2023 10:31Можно ли придумать какой-то частичный индекс?
Добавление второй волны как улучшает оценку сложности в среднем случае?
wataru
15.05.2023 10:31+1На ассимптотическую сложность оно не влияет. Но, как A* в среднем работает быстрее Дейкстры на реальных графах, так и двунаправленный A* работает на них быстрее простого A*. Это эвристическая оптимизация.
Надеюсь, автор приведет примеры с конкретными числами.
BykoIanko Автор
15.05.2023 10:31+1Добавление второй волны как улучшает оценку сложности в среднем случае?
Кажется, что просто на константу. Но на большую. Приведу довольно грубые рассуждения для Дейкстра, которые наводят на такую оценку.
Допустим у нас есть граф, вершины которого распределены равномерно на плоскости. Допустим от старта до финиша R метров.
Рассмотрим односторонний Дейкстра на этом графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины на круге с центром в старте. Площадь круга будет Pi*R^2.
Представим двусторонний Дейкстра на этом же графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины в кругах вокруг старта и финиша. Площадь каждого R/2. Суммарная площадь, на которой раскрыты вершины будет: 2*Pi*(R/2)^2 = (Pi*R^2)/2.
Т.е. в этом частном случае, кол-во раскрытых вершин уменьшиться в двое.
Это не ответ на вопрос. Кол-во раскрытых вершин удобно использовать для оценки сложности алгоритма роутинга, но это не сложность в среднем. И эти рассуждения актуальны для Дейкстра, но не для A*. Я подумаю, над более точным ответом.
Можно ли придумать какой-то частичный индекс?
Уточните п-та вопрос. Индекс, который мог бы обновляться при обновлении весов дуг графа?
Sergey_Kovalenko
15.05.2023 10:31Здравствуйте, уважаемый автор.
Хотите ли вы получить алгоритм, который будет асимптотически в
бесконечность раз быстрее описанного вами в статье для графов на плоских картах
и требовать только где-то в ln (числа ребер) раз больше памяти?
Это не фантастика: граф дорог не произвольный, а специальной
структуры (вершины лежат на плоскости, ребра не сильно отличаются
от геодезических, скорости сопоставимы). Наверно, такие алгоритмы даже где-то
даже описаны. Но если нет, и у вас есть желание, возможность и уверенность
в вашей способности вести математические исследования,
я бы мог вам в них помочь.
С уважением.wataru
15.05.2023 10:31асимптотически в
бесконечность раз быстрее описанного вами в статьеЭто как? Какая же ассимптотика вашего алгоритма? Как она в бесконечность раз быстрее O(E log V)?
Наверно, такие алгоритмы даже где-то
даже описаны.Полно алгоритмов для планарных графов описано. Я бы не надеялся что ваш алгоритм что-то уникальное и новое.
вершины лежат на плоскости, ребра не сильно отличаются
от геодезических, скорости сопоставимыА вот тут неправда. Шоссе, эстакады, тоннели, изогнутые дороги, серпантины и еще куча всяких исключений. А еще ПДД все портят: Какой-нибудь перекресток где с одной дороги можно поворачивать только налево, а с другой во все стороны — планарным графом особо не задашь.
Sergey_Kovalenko
15.05.2023 10:31+11 да быстрее, правдопобно получить вплоть до O(ln(E)*ln(v)), все зависит от класса графов
.
2. В задаче граф не планарный, однако он почти метрически отображен на плоскость.
.
3.См 2wataru
15.05.2023 10:31+1Это очень крутой алгоритм! Есть какие-нибудь ссылки почитать про него?
Подозреваю, правда, что нужен очень специфичный класс гарфов. Планарный граф — линия — будет иметь |V| вершин в пути между двумя концами, так что его за ln(E)*ln(V) ну никак не найти.
BykoIanko Автор
15.05.2023 10:31Сергей, спасибо за комментарий и за предложение!
Вы говорите про алгоритм с индексом или без?
Вы пишите про вершины, лежащие на плоскости ребра. П-та уточните, что имеется ввиду. Существенная доля вершин лежит в плоскости ребра? Верно?
Вы пишите, скорости сопоставимы. Если говорить про дорожную сеть, то формально есть дороги без ограничений. Правда их не много. Но в реальности скорости на дугах часто отличаются раз 20.
Состояние дел с прокладкой маршрутов по графам дорог не плохо было описано в этой обзорной статье: https://arxiv.org/pdf/1504.05140.pdf . Вероятно, там есть что-то похожее и вашу задумку. Если да, то скажите п-та какой это алгоритм. Если нет, но напишите п-та поконкретнее в чем идея.
Коллеги, обзорная статья 2015 года. Если у кто-то знает более новую подобную статью - пришлите ссылку п-та.
Sergey_Kovalenko
15.05.2023 10:311.Пожалуйста :)
.
2. Структура данных не главное в потенциальном решении.
.
3. Да не "в плоскости ребра" а сами вершины и ребра лежат на плоскости. Реальные дорожные графы имеют еще кучу особых признаков, особенно в отношении "локальности".
.
4. Думаю, эту проблему можно решить за счет масштаба.
.
5. В плане научного поиска уже существующих решений ваши навыки на голову превосходят мои. Наверное, то, что я имею ввиду должно быть похоже на Geometric Containers, Precomputed Cluster Distances и из вашей ссылки. Всю статью и ссылки не смотрел, но там явно что-то побыстрее (асимптотически в бесконечность раз) A* алгоритма есть.
.
6 Идея в многоуровневом масштабном представлении графа и последовательного вычисления возможных путей с более масштабных и грубых представлений в сторону более мелких и точных. Предположительно после завершения каждого этапа вы будете иметь некоторую узкую полосу для возможного пролегания вашего кратчайшего пути на графе следующего по мелкости уровня представления.wataru
15.05.2023 10:31+1асимптотически в бесконечность раз
Вы используете термины слишком небрежно. Эта фараза не имеет смысла. Если оценка O(lnE lnV) истина, то не в бесконечность, а всего-то в E/lnE раз быстрее.
BykoIanko Автор
15.05.2023 10:31+1Сергей.
Действительно граф дорог имеет ряд интересных особенностей. Он почти планарный (мостов и туннелей не так много.) И еще длинные маршруты почти всегда строятся через очень ограниченное число быстрых дуг (через магистрали). Наличие таких быстрых дуг эксплуатируется в алгоритмах, указанных вами, а так же в 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/
Sergey_Kovalenko
15.05.2023 10:31+1Спасибо за развернутый ответ.
Я изначально писал, что скорее всего уже есть, уж слишком очевидная идея.
Да, я подразумевал, что требуется подготовка и задача поиска будет решаться затем много раз. Видите, вы с этой областью работаете, если решение есть и оно
для ваших целей не подходит, то значит так оно и есть. Если бы вдруг не было, можно было бы поискать. Хотя стоит подумать над какой-то модификацией: бывает "в лоб" - нельзя, а "в обход" - можно.
Желаю вам свежих идей и вдохновения их реализовывать!BykoIanko Автор
15.05.2023 10:31Спасибо на добром слове, Сергей! Это правда очень хорошая идея. И она подходит для многих случаев. Но ввиду описанных причин, нам пришлось сделать иначе.
Желаю вам удачи в ваших начинаниях!
domix32
15.05.2023 10:31Не понял куда смотреть в код чтобы посмотреть эвристики. Не пробовали эвристики менять, чтобы ещё сильнее оптимизировать это дело? Выглядит будто эвристика плохо справляется с сортированием нод, раз там такое количество разбега во все стороны.
BykoIanko Автор
15.05.2023 10:31+1Посмотреть в код стоит вот сюда:
А так же можно и вот сюда:
Не пробовали эвристики менять, чтобы ещё сильнее оптимизировать это дело?
Пробовали. Там иначе переоценка получается. Так же пробовали ALT.
Выглядит будто эвристика плохо справляется с сортированием нод, раз там такое количество разбега во все стороны.
Поясните п-та.
domix32
15.05.2023 10:31На первом скриншоте количество точек примерно равномерно распределено вокруг точки назначения, что подсказывает, что либо точки складывают в обычную очередь и алгоритм из A* сваливается в какой-то DFS, либо эвристика крайне плохо работает и приоритет обработки вершин не смотрит на абсолютную дистанцию между вершинами и точкой назначения. В обычной ситуации A* должен был явно сделать "наклон" в сторону пункта назначения, что не слишком заметно на исходном скриншоте.
С другой стороны без каких-нибудь heatmap доказать я этого не могу т.к. картинка точно не рисует все 90к точек. Возможно на геоданных ещё какие-то нюансы всплывают и отображение вцелом некорректно из-за искажений карты.
А такой вопрос - консистентность эвристики в данном случае в чём заключается? Делает один и тот же путь если поменять местами назначение и отправление?
wataru
15.05.2023 10:31+2алгоритм из A* сваливается в какой-то DFS
Но A* никогда не сваливается в DFS. Он сваливается в Дейкстру, если эвристики нет. Что выраждается в BFS, если все ребра одинаковой длины. Но DFS тут никак не получить.
консистентность эвристики в данном случае в чём заключается?
Эвристика A* консистентна, если она никогда не переоценивает длину оставшегося пути.
BykoIanko Автор
15.05.2023 10:31На первом скриншоте количество точек примерно равномерно распределено вокруг точки назначения
Уточните п-та на каком скриншоте. Картинка с раскрытыми 90К вершинами есть на 1-й и на 3-й иллюстрациях. Вершины вокруг точки назначения - это вторая картинка на 3-й иллюстрации. И на ней не 90К, а 30К вершин раскрыто.
Комментарий про DFS и переоценку A* уже написал @wataru Спасибо!
domix32
15.05.2023 10:31Тот что рядом с Дийкстрой на 340к и одним направлением.
BykoIanko Автор
15.05.2023 10:31На этой картинке одна волна от старта к финишу. Классический A*. В нем используется стандартная эвристика: берется расстояние по прямой (на поверхности земли, без учета рельефа) и делится на максимальную скорость.
На примере видно, что есть преимущество перед алгоритмом Дейкстры. Так же видно, что волна ушла к финишу в двое дальше, чем в противоположенном направлении.
Так же на распространение волны очень влияет, есть ли быстрые дороги в регионе прокладки. Если присмотреться, то можно заметить, что именно по магистралям были раскрыты вершины в низу и в направлении от старта.
v0stok86
15.05.2023 10:31+2Можете пояснить про мьютекс - зачем там нужна блокировка? Нельзя ли для целей отслеживания/проверки завершения снарядить еще 1 поток, который бы получал обновления из потоков поиска и останавливал их, если обнаруживал критерий завершения? Да, это потребовало бы памяти, но избавило бы от блокировок.
BykoIanko Автор
15.05.2023 10:31Спасибо @v0stok86!
Да. Я не думал, о таком варианте. И это вариант, вполне можно протестировать. Отказаться от мьютекса это серьезный плюс. Так же хочу отметить, что используя третий поток, мы слегка изменим момент остановки алгоритма. Он может наступить, чуть позже, чем пересекутся волны. Но это, кажется, не должно повлиять на корректность алгоритма, насколько я помню доказательство.
С другой стороны, добавив 3й поток мы получим следующие минусы:
Нам нужно будет копировать приличный объем данных между потоками. Раскрытые вершин много на больших графах.
Нам нужно будет как-то наладить передачу данных о раскрытых вершинах в третий поток из двух рабочих потоков. Как вариант - очередь. Это тоже накладные расходы.
Хорошо бы, чтоб под 3й поток, было отдельное ядро. (Его может не быть на мобильных устройствах.)
Усложнится система.
Но тут, нужно реализовывать и мерить. Может и лучше окажется.
Мой добрый приятель и бывший коллега (@kshalnev) уже после публикации статьи, придумал очень интересную штуку, как уменьшить проверки под мьютексом. Идея применима к любому графу, но опишу ее в терминах графа дорог. Идея в следующем.
Перед запуском алгоритма считаем расстояние между стартом и финишем.
У нас есть консистентная эвристика для A*. А это значит, мы можем понять, сколько времени минимально может потребоваться, чтоб добраться из старта в финиш. По сути, в терминах карты, это время, чтоб доехать из старта до финиша по прямой дороге, на максимально скорости.
Пока в раскрытых вершинах от старта и от финиша у нас меньше половины этого времени - не проверяем, что волны пересеклись. И следовательно не выполняем долгой проверки под мьютексом. Действительно, чтоб волны пересеклись, в одной из волны мы должны рассматривать вершины, в которых будет сохранено время большее, чем половина самого быстрого.
Кажется это может ускорить работу алгоритма. Более того, кажется, что не проверять, что волны пересеклись можно и дольше. И это тоже не должно повлиять на корректность алгоритма.
za90
15.05.2023 10:31Вот бы посмотреть на статистику, собранную мапсми - сколько ядер было на устройствах, где запускалось приложение.
wataru
Просто интересно, а сколько там всего суммарно вершин и дуг в графе всех дорог мира?
И есть вопрос про двусторонний A*. А можно поподробнее остановиться на доказательстве корректности критерия остановки? Почему после первого касания, достаточно рассмотреть только все дуги между двумя "волнами"?
Ясно, что в случае, если все вершины графа поделены между двумя волнами, то такой алгоритм найдет кротчайший путь, ведь кратчайший путь можно разбить на 2 куска — в первой доле и во второй, плюс ребро между долями, и настоящий кратчайший путь в рассмотренные попадет.
Но, что, если в графе есть еще нераскрытые вершины? Почему кратчайший путь не может проходить через них?
BykoIanko Автор
Примерно сотни миллионов дорожных фичей в OpenStreetMap (https://taginfo.openstreetmap.org/keys/highway#overview). Далее, в среднем 5-7 сегментов на фичу. Т.е. грубо получается 1-2 миллиарда вершин графа дорог. Можно, уменьшить кратно их кол-во рассматривая в качестве вершин только перекрестки. Такой подход не позволит по-простому реализовать разворот в произвольном месте, где он возможен, но он вполне оправдан. Развороты при таком подходе будут возможны только на перекрестках.
Отличный вопрос! Я изначально думал это написать в статье, но она оказалась и без того достаточно объемной. Предлагаю так. Я или напишу ответ на Ваш комментарий, где покажу, корректность алгоритма. Или напишу отдельную статью на эту тему. Как продолжение к этой статье.
wataru
Если вы собираетесь формально это доказывать, да еще добавите более детальное описание алгоритма (скажем, псевдокод), то это определенно потянет на целую статью.
BykoIanko Автор
Кажется без описания алгоритма не обойтись, если писать статью и доказательство. Я наверно, так сделаю. Завтра или после завтра напишу не большой набросок, в какую сторону смотреть, прямо в этой ветке. А статью уже позже и отдельно. Спасибо, за замечание!
wataru
А, погодите. Я что-то затупил. Оно же элементарно доказывается в одно предложение:
Кратчайший путь не может проходить через нераскрытую обеими волнами вершину, потому что этот путь будет не короче пути через вершину-пересечение волн (потому что каждая половинка этого пути не короче соответствующей половинки пути через точку пересечения внутри волны, а это так по свойству "волны" А*).
Но все-равно, формальное доказательство от начала и до конца, да техническое описание алгоритма будут не лишними.
BykoIanko Автор
Да. Это основная идея! Но все же формальное доказательство существенно длиннее. Но и к нему, желательно описание алгоритма, чтоб договориться, что мы доказываем. Мне нравится вариант доказательства корректности - через потенциалы вершин. Думаю, это было бы не плохим дополнением к статье.