Иерархии сокращений

В информатике метод иерархий сжатия — это метод ускорения поиска кратчайшего пути в графе . Наиболее интуитивно понятными приложениями являются системы автомобильной навигации: пользователь хочет проехать из в по максимально быстрому маршруту. Оптимизируемой здесь метрикой является время в пути. Пересечения представлены вершинами , а участки дороги, соединяющие их, — ребрами . Веса ребер представляют время, необходимое для проезда по этому участку дороги. Путь от в представляет собой последовательность ребер (участков дороги); кратчайший путь — это тот, у которого сумма весов ребер минимальна среди всех возможных путей. Кратчайший путь в графе можно вычислить с помощью алгоритма Дейкстры, но, учитывая, что дорожные сети состоят из десятков миллионов вершин, это непрактично. ^[1] Иерархии сжатия — это метод ускорения, оптимизированный для использования свойств графов, представляющих дорожные сети. ^[2] Ускорение достигается путем создания сокращений на этапе предварительной обработки, которые затем используются во время запроса кратчайшего пути для пропуска «неважных» вершин. ^[2] Это основано на наблюдении, что дорожные сети имеют высокую иерархичность. Некоторые перекрестки, например, развязки автомагистралей, «важнее» и находятся выше в иерархии, чем, например, развязка, ведущая в тупик. Сокращенные пути можно использовать для сохранения предварительно вычисленного расстояния между двумя важными развязками, так что алгоритму не нужно учитывать полный путь между этими развязками во время запроса. Иерархии сокращения не знают, какие дороги люди считают «важными» (например, автомагистрали), но им предоставляется граф в качестве входных данных, и они могут назначать важность вершинам с помощью эвристики. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Иерархии сокращения применяются не только для ускорения алгоритмов в системах автомобильной навигации , но и в веб- планировщиках маршрутов , моделировании дорожного движения и оптимизации логистики. ^{[3] [1] [4]} Реализации алгоритма общедоступны как программное обеспечение с открытым исходным кодом . ^{[5] [6] [7] [8] [9]}

Алгоритм

Алгоритм сокращения иерархий (CH) представляет собой двухфазный подход к задаче кратчайшего пути, состоящий из фазы предварительной обработки и фазы запроса . Поскольку дорожные сети меняются довольно редко, больше времени (секунды или часы) можно использовать для предварительного вычисления некоторых вычислений перед тем, как отвечать на запросы. Используя эти предварительно вычисленные данные, можно ответить на многие запросы, затратив очень мало времени (микросекунды) на каждый. ^{[1] [3]} CH полагаются на сокращения для достижения этого ускорения. Сокращение соединяет две вершины , не являющиеся смежными в исходном графе. Его вес ребра равен сумме весов ребер на кратчайшем пути . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$

Рассмотрим два больших города, соединенных шоссе. Между этими двумя городами есть множество перекрестков, ведущих к небольшим деревням и пригородам. Большинство водителей хотят добраться из одного города в другой — возможно, как часть более крупного маршрута — и не съезжать по пути. В графе, представляющем эту схему дороги, каждое пересечение представлено узлом, а ребра создаются между соседними перекрестками. Чтобы вычислить расстояние между этими двумя городами, алгоритм должен пройти все ребра по пути, суммируя их длину. Предварительное вычисление этого расстояния один раз и сохранение его в дополнительном ребре, созданном между двумя большими городами, сэкономит вычисления каждый раз, когда это шоссе должно оцениваться в запросе. Это дополнительное ребро называется «срезом» и не имеет аналога в реальном мире. Алгоритм иерархий сокращения не имеет знаний о типах дорог, но может определить, какие срезы должны быть созданы, используя только граф в качестве входных данных.

Чтобы найти путь от до, алгоритм может пропустить серые вершины и использовать вместо них пунктирный ярлык . Это уменьшает количество вершин, которые алгоритм должен просмотреть. Вес ребра ярлыка от до — это сумма весов ребер кратчайшего пути . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$

Фаза предварительной обработки

Алгоритм CH полагается на сокращения, созданные на этапе предварительной обработки, для сокращения пространства поиска, то есть количества вершин, которые CH должен просмотреть во время запроса. Для достижения этого выполняются итеративные сокращения вершин. При сокращении вершины она временно удаляется из графа , и сокращение создается между каждой парой соседних вершин, если кратчайший путь от до содержит . ^[2] Процесс определения того, содержит ли кратчайший путь между и , называется поиском свидетелей. Его можно выполнить, например, вычислив путь от до с помощью прямого поиска, используя только еще не сокращенные узлы. ^[3] ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle \{u,w\}}$ ${\textstyle u}$ ${\textstyle w}$ ${\displaystyle v}$ ${\textstyle u}$ ${\textstyle w}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle w}$

Исходный график — это линия (сплошная). Пунктирные ребра представляют сокращения, серые стрелки показывают, какие два ребра объединены для формирования соответствующего сокращения. Вершины были нарисованы для представления порядка узлов, в котором вершины сжимаются, снизу вверх. Сжимающаяся вершина вводит сокращение между и с . Сокращения вершин и вводят одно сокращение соответственно. Сокращения , и не вводят никаких сокращений и поэтому не показаны. ${\displaystyle (a,b,c,d,e,f)}$ ${\displaystyle c}$ ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle \mathrm {dist} (b,d)=\mathrm {dist} (b,c)+\mathrm {dist} (c,d)}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle f}$

Порядок узлов

Вершины входного графа должны быть сжаты таким образом, чтобы минимизировать количество ребер, добавляемых к графу сжатием. Поскольку оптимальное упорядочение узлов является NP-полным , ^[10] используются эвристики . ^[2]

Существуют эвристики снизу вверх и сверху вниз . С одной стороны, эвристики снизу вверх, которые требуют меньше вычислений, определяют порядок, в котором следует сжимать вершины, в жадной манере; это означает, что порядок неизвестен заранее, а следующий узел выбирается для сжатия после того, как предыдущее сжатие было завершено. С другой стороны, эвристики сверху вниз предварительно вычисляют весь порядок узлов до того, как будет сжат первый узел. Это дает лучшие результаты, но требует больше времени на предварительную обработку. ^[2]

В эвристике снизу вверх для выбора следующей вершины для сжатия используется комбинация факторов. Поскольку количество сокращений является основным фактором, определяющим предварительную обработку и время выполнения запроса, мы хотим сохранить его как можно меньшим. Наиболее важным термином, с помощью которого можно выбрать следующий узел для сжатия, является чистое количество ребер, добавляемых при сжатии узла . Это определяется как , где — количество сокращений, которые были бы созданы, если бы были сокращены, а — количество ребер, инцидентных . Используя только этот критерий, линейный путь приведет к линейной иерархии (много уровней ) и отсутствию созданных сокращений. Рассматривая количество соседних вершин, которые уже сокращены, достигается равномерное сжатие и плоская иерархия (меньше уровней). Это можно сделать, например, поддерживая счетчик для каждого узла, который увеличивается каждый раз, когда сокращается соседняя вершина. Узлы с более низкими счетчиками затем предпочитаются узлам с более высокими счетчиками. ^[11] ${\displaystyle x}$ ${\displaystyle A(x)-|\{(u,x)\colon (u,x)\in E\}|}$ ${\displaystyle A(x)}$ ${\displaystyle x}$ ${\displaystyle |\{(u,x)\colon (u,x)\in E\}|}$ ${\displaystyle x}$

С другой стороны, эвристики сверху вниз дают лучшие результаты, но требуют больше времени на предварительную обработку. Они классифицируют вершины, которые являются частью многих кратчайших путей, как более важные, чем те, которые нужны только для нескольких кратчайших путей. Это можно аппроксимировать с помощью вложенных разрезов . ^[2] Чтобы вычислить вложенный разрез, рекурсивно разделяют граф на две части, которые затем сами разделяются на две части и так далее. То есть, находят подмножество узлов , которые при удалении из графа разделяются на две непересекающиеся части приблизительно одинакового размера, такие что . Размещают все узлы последними в порядке узлов, а затем рекурсивно вычисляют вложенный разрез для и , ^[12] интуиция заключается в том, что все запросы из одной половины графа в другую половину графа должны проходить через небольшой разделитель, и поэтому узлы в этом разделителе имеют большую важность. Вложенные разрезы можно эффективно вычислять на дорожных сетях из-за их небольших разделителей. ^[13] ${\displaystyle S\subseteq V}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G_{1},G_{2}}$ ${\displaystyle S\cup G_{1}\cup G_{2}=G}$ ${\displaystyle v\in S}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$

Фаза запроса

На этапе запроса выполняется двунаправленный поиск, начиная с начального узла и целевого узла на исходном графе, дополненный сокращениями, созданными на этапе предварительной обработки. ^[2] Самая важная вершина на кратчайшем пути между и будет либо сама по себе, либо важнее, чем и . Таким образом, минимизация вершин происходит на кратчайшем пути в исходном графе и выполняется. ^[2] Это, в сочетании с тем, как создаются сокращения, означает, что и прямой, и обратный поиск должны ослабить только ребра, ведущие к более важным узлам (вверх) в иерархии, что сохраняет небольшое пространство поиска. ^[3] Во всех путях вверх-(вниз-вверх)-вниз внутренний (вниз-вверх) может быть пропущен, поскольку сокращение было создано на этапе предварительной обработки. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)}$ ${\displaystyle s-t}$ ${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)=\mathrm {dist} (s,t)}$

При вычислении кратчайшего пути от до , прямой (оранжевый) и обратный (синий) поиски должны следовать только по ребрам, идущим вверх по иерархии. Найденный путь отмечен красным и использует один ярлык (пунктирный). ${\displaystyle s}$ ${\displaystyle t}$

Поиск пути

Запрос CH, как описано выше, возвращает время или расстояние от до , но не сам путь. Чтобы получить список ребер (дорог) на кратчайшем пути, необходимо распаковать выбранные сокращения. Каждое сокращение представляет собой объединение двух ребер: либо двух ребер исходного графа, либо двух сокращений, либо одного исходного ребра и одного сокращения. Сохранение средней вершины каждого сокращения во время сжатия позволяет производить рекурсивную распаковку кратчайшего маршрута за линейное время. ^{[2] [3]} ${\displaystyle s}$ ${\displaystyle t}$

Индивидуально разработанные иерархии сокращений

Если веса ребер меняются чаще, чем топология сети, CH можно расширить до трехфазного подхода, включив фазу настройки между фазой предварительной обработки и запросом. Это можно использовать, например, для переключения между кратчайшим расстоянием и кратчайшим временем или включить текущую информацию о дорожном движении, а также предпочтения пользователя, такие как избегание определенных типов дорог (паромы, шоссе, ...). На фазе предварительной обработки большая часть времени выполнения тратится на вычисление порядка, в котором узлы сжимаются. ^[3] Эту последовательность операций сжатия на фазе предварительной обработки можно сохранить для того, когда они позже понадобятся на фазе настройки. Каждый раз, когда метрика настраивается, сжатия затем можно эффективно применять в сохраненном порядке с использованием пользовательской метрики. ^[2] Кроме того, в зависимости от новых весов ребер может потребоваться пересчитать некоторые сокращения. ^[3] Чтобы это работало, порядок сжатия должен быть вычислен с использованием вложенных диссекции, независимых от метрики. ^[1]

Расширения и приложения

CH, как описано выше, ищут кратчайший путь от одного начального узла до одного целевого узла. Это называется кратчайшим путем один к одному и используется, например, в системах автомобильной навигации. Другие приложения включают сопоставление GPS- треков с дорожными сегментами и ускорение симуляторов дорожного движения , которые должны учитывать вероятные маршруты, пройденные всеми водителями в сети. При прогнозировании маршрута пытаются оценить, куда, скорее всего, направится транспортное средство, вычисляя, насколько хорошо его текущее и прошлое положение согласуется с кратчайшим путем от его начальной точки до любой возможной цели. Это можно эффективно сделать с помощью CH. ^[2]

В сценариях «один ко многим» задаются начальный узел и набор целевых узлов , и расстояние для всех должно быть вычислено. Наиболее известным применением запросов «один ко многим» является поиск точек интереса. Типичные примеры включают поиск ближайшей заправочной станции, ресторана или почтового отделения с использованием фактического времени в пути вместо географического расстояния в качестве метрики. ^[2] ${\displaystyle s}$ ${\displaystyle T}$ ${\displaystyle \mathrm {dist} (s,t)}$ ${\displaystyle t\in T}$

В сценарии кратчайшего пути «многие ко многим» заданы набор начальных узлов и набор целевых узлов , и расстояние для всех должно быть вычислено. Это используется, например, в логистических приложениях. ^[2] CHs могут быть расширены до запросов «многие ко многим» следующим образом. Сначала выполните обратный поиск вверх из каждого . Для каждой вершины, сканируемой во время этого поиска, сохраняется в контейнере . Затем выполняется прямой поиск вверх из каждого , проверяя для каждого непустого контейнера, улучшает ли маршрут через соответствующую вершину любое наилучшее расстояние. То есть, если для любого . ^{[2] [3]} ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle \mathrm {dist} (s_{i},t_{i})}$ ${\displaystyle (s_{i},t_{j})\in S\times T}$ ${\displaystyle t_{j}\in T}$ ${\displaystyle u}$ ${\displaystyle \mathrm {dist} (t_{j},u)}$ ${\displaystyle \beta (u)}$ ${\displaystyle s_{i}\in S}$ ${\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})}$ ${\displaystyle (s_{i},t_{j})\in S\times T}$

Некоторые приложения даже требуют вычислений «один ко всем» , т. е. нахождения расстояний от исходной вершины до всех других вершин в графе. Поскольку алгоритм Дейкстры посещает каждое ребро ровно один раз и, следовательно, выполняется за линейное время, он теоретически оптимален. Однако алгоритм Дейкстры трудно распараллелить , и он не является оптимальным для кэша из- за своей плохой локальности. CH можно использовать для более оптимальной для кэша реализации. Для этого выполняется прямой поиск вверх с последующим сканированием вниз по всем узлам в графе, обогащенном ярлыком. Последняя операция сканирует память линейно, поскольку узлы обрабатываются в порядке убывания важности и, следовательно, могут быть размещены в памяти соответствующим образом. ^[14] Обратите внимание, что это возможно, поскольку порядок, в котором узлы обрабатываются на втором этапе, не зависит от исходного узла . ^[2] ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$

В производстве автомобильные навигационные системы должны уметь вычислять самые быстрые маршруты движения, используя прогнозируемую информацию о дорожном движении, и отображать альтернативные маршруты. Оба варианта можно реализовать с помощью CH. ^[2] Первый вариант называется маршрутизацией с сетями, зависящими от времени, где время прохождения заданного края больше не является постоянным, а скорее функцией времени суток при въезде на край. Альтернативные маршруты должны выглядеть плавно, значительно отличаться от кратчайшего пути, но не значительно длиннее. ^[2]

CHs можно расширить для оптимизации нескольких метрик одновременно; это называется многокритериальным планированием маршрута. Например, можно минимизировать как стоимость поездки, так и время. Другим примером являются электромобили , для которых доступный заряд батареи ограничивает допустимые маршруты, поскольку батарея может не разрядиться. ^[2]

Теория

Было установлено несколько границ для производительности предварительной обработки и запросов иерархий сжатия. В дальнейшем пусть будет числом вершин в графе, числом ребер, размерностью шоссе , диаметром графа, является глубиной дерева и является шириной дерева . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle h}$ ${\displaystyle D}$ ${\displaystyle td}$ ${\displaystyle tw}$

Первый анализ производительности иерархии сжатия частично опирается на величину, известную как размерность шоссе . Хотя определение этой величины является техническим, интуитивно граф имеет небольшую размерность шоссе, если для каждого существует разреженный набор вершин, такой что каждый кратчайший путь длины, большей, чем включает вершину из . Вычисление точного значения размерности шоссе является NP-трудным ^{[15] [16]} и, скорее всего, W[1]-трудным , ^[17] но для сеток известно, что размерность шоссе составляет . ^[18] ${\displaystyle r>0}$ ${\displaystyle S_{r}}$ ${\displaystyle r}$ ${\displaystyle S_{r}}$ ${\displaystyle h\in \Theta ({\sqrt {n}})}$

Альтернативный анализ был представлен в работе Customizable Contraction Hierarchy. Время выполнения запроса может быть ограничено . Поскольку глубина дерева может быть ограничена в терминах ширины дерева, также является допустимой верхней границей. Основной источник — ^[19], но последствия для времени выполнения в худшем случае лучше детализированы в ^{[20] .} ${\displaystyle O(td^{2})}$ ${\displaystyle O((tw\log n)^{2})}$

Производительность предварительной обработки

Производительность запроса

Ссылки

1. Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (5 апреля 2016 г.). «Настраиваемые иерархии сокращения». Журнал экспериментальной алгоритмики . 21 (1): 1–49. arXiv : 1402.0402 . doi : 10.1145/2886843. S2CID  5247950.
2. Баст, Ханна; Деллинг, Дэниел; Гольдберг, Эндрю В.; Мюллер-Ханнеманн, Маттиас; Пайор, Томас; Сандерс, Питер; Вагнер, Доротея; Вернек, Ренато Ф. (2016). «Планирование маршрутов в транспортных сетях». Алгоритмическая инженерия . Конспекты лекций по информатике. Том. 9220. стр. 19–80. arXiv : 1504.05140 . дои : 10.1007/978-3-319-49487-6_2. ISBN 978-3-319-49486-9. S2CID  14384915.
3. Гейсбергер, Роберт; Сандерс, Питер; Шультес, Доминик; Веттер, Кристиан (2012). «Точная маршрутизация в крупных дорожных сетях с использованием иерархий сжатия». Transportation Science . 46 (3): 388–404. doi :10.1287/trsc.1110.0401.
4. Деллинг, Дэниел; Сандерс, Питер; Шультес, Доминик; Вагнер, Доротея (2009). «Алгоритмы проектирования маршрутов». Алгоритмика больших и сложных сетей . Конспект лекций по информатике. Том 5515. С. 117–139. doi :10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
5. «OSRM – Маршрутная машина с открытым исходным кодом».
6. «Вики – OpenTripPlanner».
7. «Веб – GraphHopper».
8. "GitHub – Tempus". GitHub . 9 сентября 2021 г.
9. "GitHub – RoutingKit". GitHub . 24 января 2022 г.
10. Бауэр, Рейнхард; Деллинг, Дэниел; Сандерс, Питер; Шифердекер, Деннис; Шультес, Доминик; Вагнер, Доротея (01 марта 2010 г.). «Сочетание иерархических и целенаправленных методов ускорения алгоритма Дейкстры». Журнал экспериментальной алгоритмики . 15 : 2.1. дои : 10.1145/1671970.1671976. ISSN  1084-6654. S2CID  1661292.
11. Гейсбергер, Роберт; Сандерс, Питер; Шультес, Доминик; Деллинг, Дэниел (2008). «Иерархии сокращения: более быстрая и простая иерархическая маршрутизация в дорожных сетях». В МакГеоче, Кэтрин С. (ред.). Экспериментальные алгоритмы . Конспекты лекций по информатике. Том. 5038. Шпрингер Берлин Гейдельберг. стр. 319–333. дои : 10.1007/978-3-540-68552-4_24. ISBN 9783540685524. S2CID  777101.
12. Бауэр, Рейнхард; Колумбус, Тобиас; Раттер, Игнац; Вагнер, Доротея (2016-09-13). «Размер пространства поиска в иерархиях сжатия». Теоретическая информатика . 645 : 112–127. doi : 10.1016/j.tcs.2016.07.003 . ISSN  0304-3975.
13. Деллинг, Дэниел; Голдберг, Эндрю В.; Разенштейн, Илья; Вернек, Ренато Ф. (май 2011 г.). «Разбиение графа с естественными разрезами». 2011 IEEE International Parallel & Distributed Processing Symposium . стр. 1135–1146. CiteSeerX 10.1.1.385.1580 . doi :10.1109/ipdps.2011.108. ISBN  978-1-61284-372-8. S2CID  6884123.
14. Деллинг, Дэниел; Голдберг, Эндрю В.; Новатзик, Андреас; Вернек, Ренато Ф. (2011). «PHAST: Аппаратно-ускоренные деревья кратчайших путей». IEEE International Parallel & Distributed Processing Symposium 2011. стр. 921–931. doi :10.1109/ipdps.2011.89. ISBN 978-1-61284-372-8. S2CID  1419921.
15. Фельдманн, Андреас Эмиль; Фунг, Вай Шинг; Кёнеманн, Йохен; Пост, Ян (01.01.2018). «Вложение графов с малой размерностью магистралей в графы с ограниченной древовидной шириной $(1+\varepsilon)$». Журнал SIAM по вычислениям . 47 (4): 1667–1704. arXiv : 1502.04588 . doi : 10.1137/16M1067196. ISSN  0097-5397. S2CID  11339698.
16. Блюм, Йоханнес (2019). «Иерархия параметров транспортной сети и результатов твердости». Ин Янсен, член парламента Барта; Телле, Ян Арне (ред.). 14-й Международный симпозиум по параметризованным и точным вычислениям (IPEC 2019). Лейбниц Международные труды по информатике. Том. 148. Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. стр. 4:1–4:15. doi : 10.4230/LIPIcs.IPEC.2019.4 . ISBN 978-3-95977-129-0. S2CID  166228480.
17. Блюм, Йоханнес; Диссер, Янн; Фельдманн, Андреас Эмиль; Гупта, Сиддхартх; Зых-Павлевич, Анна (2022). «О разреженных наборах ударов: от справедливого покрытия вершин до измерения шоссе». В Делле, Хольгер; Недерлоф, Йеспер (ред.). 17-й Международный симпозиум по параметризованным и точным вычислениям (IPEC 2022) . Лейбниц Международные труды по информатике. Том. 249. Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. стр. 5:1–5:23. doi : 10.4230/LIPIcs.IPEC.2022.5 . ISBN 978-3-95977-260-0.
18. Авраам, Иттай; Фиат, Амос; Голдберг, Эндрю (2010). Измерение шоссе, кратчайшие пути и доказуемо эффективные алгоритмы (PDF) . Труды ежегодного симпозиума ACM-SIAM 2010 года по дискретным алгоритмам. doi : 10.1137/1.9781611973075.64 .
19. Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (2016). «Настраиваемые иерархии сокращения». ACM Journal of Experimental Algorithmics . 21 : 1–49. arXiv : 1402.0402 . doi : 10.1145/2886843. S2CID  5247950.
20. Хаманн, Майкл; Штрассер, Бен (2018). «Деление графа пополам с оптимизацией по Парето». ACM Journal of Experimental Algorithmics . 23 : 1–34. arXiv : 1504.03812 . doi : 10.1145/3173045. S2CID  3395784.
21. Funke, Stefan; Storandt, Sabine (2015). "Доказуемая эффективность иерархий сжатия с рандомизированной предварительной обработкой". Алгоритмы и вычисления . Конспект лекций по информатике. Том 9472. С. 479–490. doi :10.1007/978-3-662-48971-0_41. ISBN 978-3-662-48971-0.
22. Блюм, Йоханнес; Функе, Стефан; Сторандт, Сабина (2018). Пространства сублинейного поиска для планирования кратчайшего пути в сетях сеток и дорог (PDF) . AAAI.

Внешние ссылки

Реализации с открытым исходным кодом

• https://www.graphhopper.com/
• https://github.com/ifsttar/Tempus
• https://github.com/RoutingKit/RoutingKit
• http://project-osrm.org/
• http://www.opentripplanner.org/