На Хабре можно найти немало статей, посвящённых оптимизациям поиска кратчайшего пути на графе. Я расскажу ещё про один подход. Речь пойдёт о распараллеливании алгоритма 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.
