- PVSM.RU - https://www.pvsm.ru -
Если кто ещё не знает, то 2ГИС [1] — это бесплатный справочник организаций с картой города. И если про справочник уже написано много [2], то про карту и её возможности информации меньше. А рассказать есть чего. Например, про роутинг — почему мы не взяли существующие решения, а написали своё или зачем нужен единый алгоритм построения в разных продуктах.
В начале 2012 года мы впервые столкнулись с проблемой — движок, который до этого использовался в десктопной версии, оказался слишком требовательным к ресурсам и его невозможно использовать на мобильных устройствах. Нужно было что-то делать.
Почему не взять готовые решения?
Существует мнение, что движок роутинга — это неподъемная задача с кучей тонкостей реализации. Будто за то, что не лезет в boost::graph и браться не стоит (про что не снято кино, того и знать не положено, да) и проще найти уже готовое решение. Возможно, но не в нашем случае.
Надеюсь, что из статьи станет понятно — здравый смысл, немного авантюризма и готовое на всё руководство позволяют решить любую задачу.
Справедливости ради, следует отметить, что я уже имел опыт работы с поиском в графах (~50 млн вершин), поэтому некоторые представления о том, как надо решать подобные задачи, уже были.
Итак, вводная:
Обозначим основные (и, банальные, в общем-то) принципы:
Основные идеи
Вот так выглядит фрагмент графа, посаженный на решетку.
Пример ребер, попавших в один тайл на примере фрагмента дорожного графа Москвы.
Исходные данные
Предобработка
Хранение на диске
Собственно данные хранятся в В-деревьях, точнее в одной из их разновидностей.
От хранилища данных нам нужна способность хранить сортированный массив N-ок и быстро вычитывать их интервалы.
По большому счету, выбор хранилища не принципиален, мы выбрали В-деревья, т.к они:
Итак, есть несколько деревьев:
1. Дерево вершин. N-ка этого дерева состоит из 4 элементов:
2. Дерево ребер, Его ключ состоит из 7 элементов:
3. Дерево идентификаторов. Служит для связи с внешним миром. Ключ содержит 5 элементов:
4. Дерево ограничений с ключом длины 4:
Вдумчивый читатель скажет: «Ба! Чтобы прочитать всю информацию об одном тайле надо делать 3 строка по деревьям. Не лучше ли запаковать всё в BLOB и поднимать его одним махом?» Для read-only данных лучше, конечно, и в скорости и по качеству сжатия. Но это дополнительная работа, дополнительное тестирование. Кроме того, профилирование показало, что, собственно, вычитывание данных не является узким местом при поиске проезда.
Если же речь идет о данных, которые могут динамически меняться, здесь В-деревья вне конкуренции. Не обязательно даже иметь собственную реализацию деревьев, можно использовать SQL-хранилище, а вышеописанные сущности задавать как таблицы, состоящие из одного только primary key. Так, один из предшественников описываемого движка был построен на базе СУБД OpenLink Virtuoso [3], где сами таблицы устроены, как деревья и, в нашем случае, отсутствует дублирование данных как таковое (имеется ввиду дублирование данных из таблицы в индексе).
Представление графа в памяти
В этом разделе опишем, как выглядит распакованный граф в памяти.
1. Весь граф в памяти может и не существовать. Как уже говорилось, он подгружается потайлово по мере того, как кому-то потребовались части этого графа.
2. Следовательно, есть кэш тайлов и держатель этого кэша. Стратегия кэширования может быть любой. У нас это LRU (Least Recently Used).
3. Загруженный в память тайл — содержит всю информацию о данных, попавших в его область пространства. Как уже говорилось, вся память для этого выделяется из принадлежащего тайлу аллокатора и освобождается при его кончине. А именно:
// следующее ребро
};
struct restriction_t {uint64_t from_; uint64_t to_;}; Описатель ограничения движения. Их относительно немного и дешевле содержать отдельный набор ограничений, чем добавлять (скорее всего) пустой указатель на список ограничений в каждый описатель вершины. Впрочем, это дело вкуса.
4. Таким образом, тайл в памяти — это готовый к использованию кусок графа, который умеет:
Собственно поиск
1. Перед началом поиска нужно привязаться к графу. Т.е. снаружи мы получаем два набора точек — исходных и конечных. Описание каждой точки состоит из ее внешнего идентификатора ребра графа и стоимости. Стоимости достижения начала этого ребра для исходной точки и стоимости пути от конца ребра до финала для конечной точки. Итак:
2. С помощью дерева идентификаторов мы превращаем идентификаторы ребер в точки входа в граф (const vertex_t *). Для этого придется обратиться к держателю кэша тайлов и подгрузить нужные из них.
Нам нужен объект — держатель информации о финале, включая идентификаторы тайлов и номера вершин. Еще одна полезная информация, которой обладает этот объект, — геометрическое положение финиша. Ее можно задавать явно, а можно вычислять, например, как центроид финальных точек. Эта точка нам будет нужна для вычисления оценочной части стоимости достигнутой вершины для алгоритма А*
3. Теперь нам нужен держатель «волны». Он состоит из:
a. Аллокатора, ну куда ж без него.
b. Набора подгруженных тайлов. Для графов разумной величины достаточно битовой маски. Т.е., когда мы первый раз попали в какой-либо тайл, помечаем соответствующий бит в этой маске и наращиваем счетчик его ссылок. После завершения поиска, ориентируясь на эту маску, мы откатим счетчики ссылок обратно. При этом, те тайлы, чьи счетчики обнулились, получают в дальнейшем шанс вылететь из кэша.
c. Приоритетная очередь. Мы используем бинарную сортирующую кучу. В очередь попадают кандидаты на просмотр. Например, стартовые точки попадают прямиком сюда. Ключом при этом являются пройденное расстояние либо потраченное время. А значением — указатель на описатель пройденной точки
d. Набора пройденных точек. Каждая такая точка описывается структурой:
struct vertex_ptr_t {
int64_t fid_; // внешний идентификатор ребра, из которого мы сюда попали
// для стартовых точек это 0
const vertex_t *ptr_; // указатель на точку в графе
const vertex_ptr_t *prev_; // указатель на предыдущую пройденную точку
size_t cost_len_; // пройденное на данный момент расстояние
size_t cost_time_; // потраченное на данный момент время
};
Конечно, эти структуры выделяются аллокатором.
4. Итак, для каждой стартовой точки мы создаем ее описатель и помещаем его в кучу. Вот мы и готовы начинать поиск.
5. Пока в куче что-то есть (и пока это что-то потенциально лучше уже найденных кандидатов), выбираем из нее самый дешевый элемент и:
a. бежим по списку его исходящих ребер и для каждого из них:
I. проверяем возможность перехода на это ребро с предыдущего.
II. находим вершину графа, на которую указывает это ребро. Возможно, при этом будет подгружен новый тайл, и эта точка будет в нем.
III.Вычисляем стоимость достижения этой новой точки. Для этого:
IV. создаем и наполняем описатель пройденной вершины
V. проверяем, не является ли финальной эта точка
VI. если это финиш, то раскручиваем список предыдущих
( vertex_ptr_t::prev_ ), начиная с данной точки, пока на упремся в 0,
т.е. в старт. Вот и готовый кандидат на выдачу.
VII. заносим созданный описатель в кучу
Результаты
Попробуем оценить результаты содеянного на примере дорожного графа столицы нашей необъятной Родины.
Синим обозначен оптимальный маршрут, красным — “волна”.
Как и раньше, синим обозначен оптимальный маршрут, красным — “волна”.
Забавно наблюдать, как поиск выявил (фактическое, неявное) иерархическое устройство графа и стал его использовать
Итого
Как мы видим, столь простая структура данных и описанный алгоритм, позволяют работать с одноуровневым графом большого города на рядовом смартфоне. А если нам позволяет оперативная память, например, в серверном случае, увеличивая размер кэша тайлов мы просто загоняем весь граф в память и работаем с готовым его представлением. Что благотворно сказывается на производительности.
Мы намеренно не касались некоторых моментов, например, учета дорожной обстановки, предсказания оной, иерархических графов, ибо это совсем другая история.
That’s All Folks!
Автор: zzeng
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/karty/34325
Ссылки в тексте:
[1] 2ГИС: http://2gis.ru/?utm_source=news&utm_medium=habr&utm_campaign=post_routing
[2] про справочник уже написано много: http://habrahabr.ru/company/2gis/
[3] OpenLink Virtuoso: http://www.google.com/url?q=http%3A%2F%2Fvirtuoso.openlinksw.com%2Fdataspace%2Fdoc%2Fdav%2Fwiki%2FMain%2F&sa=D&sntz=1&usg=AFQjCNE6rH8ztAOZKC38o0yW3WyvbyE_lQ
[4] Источник: http://habrahabr.ru/post/179749/
Нажмите здесь для печати.