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

В информатике метод сокращения иерархий — это метод ускорения поиска кратчайшего пути в графе . Наиболее интуитивными приложениями являются автомобильные навигационные системы: пользователь хочет проехать из пункта в пункт максимально быстрым маршрутом. Оптимизированная здесь метрика — это время в пути. Перекрестки изображаются вершинами , соединяющие их участки дорог — ребрами . Веса ребер представляют собой время, необходимое для проезда по этому участку дороги. Путь от до представляет собой последовательность ребер (участков дороги); кратчайший путь — это путь с минимальной суммой весов ребер среди всех возможных путей. Кратчайший путь в графе можно вычислить с помощью алгоритма Дейкстры, но, учитывая, что дорожные сети состоят из десятков миллионов вершин, это непрактично. ^[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] CH можно расширить до запросов «многие ко многим» следующим образом. Сначала выполните обратный поиск вверх от каждого файла . Каждая вершина, просканированная во время этого поиска, сохраняется в корзине . Затем выполняется прямой поиск вверх от каждого , проверяя для каждого непустого сегмента, улучшает ли маршрут через соответствующую вершину какое-либо наилучшее расстояние. То есть, если для любого . ^{[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]

CH можно расширить для одновременной оптимизации нескольких показателей; это называется многокритериальным планированием маршрута. Например, можно минимизировать как стоимость, так и время поездки. Другим примером являются электромобили , у которых доступный заряд аккумулятора ограничивает допустимые маршруты, поскольку аккумулятор может не разряжаться. ^[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}})}$

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

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

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

Рекомендации

1. Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (5 апреля 2016 г.). «Настраиваемые иерархии сокращений». Журнал экспериментальной алгоритмики . 21 (1): 1–49. arXiv : 1402.0402 . дои : 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). «Точная прокладка маршрутов в крупных дорожных сетях с использованием иерархий сжатия». Транспортная наука . 46 (3): 388–404. дои : 10.1287/trsc.1110.0401.
4. Деллинг, Дэниел; Сандерс, Питер; Шультес, Доминик; Вагнер, Доротея (2009). «Алгоритмы планирования инженерных маршрутов». Алгоритмы больших и сложных сетей . Конспекты лекций по информатике. Том. 5515. стр. 117–139. дои : 10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
5. «OSRM - Маршрутизирующая машина с открытым исходным кодом» .
6. "Вики - OpenTripPlanner" .
7. "Интернет - GraphHopper" .
8. "GitHub - Темпус" . Гитхаб . 9 сентября 2021 г.
9. "GitHub - RoutingKit" . Гитхаб . 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. Бауэр, Рейнхард; Колумб, Тобиас; Раттер, Игнац; Вагнер, Доротея (13 сентября 2016 г.). «Размер пространства поиска в сокращающихся иерархиях». Теоретическая информатика . 645 : 112–127. дои : 10.1016/j.tcs.2016.07.003 . ISSN  0304-3975.
13. Деллинг, Дэниел; Гольдберг, Эндрю В.; Разенштейн, Илья; Вернек, Ренато Ф. (май 2011 г.). «Разбиение графа с естественными разрезами». 2011 Международный симпозиум IEEE по параллельной и распределенной обработке . стр. 1135–1146. CiteSeerX 10.1.1.385.1580 . дои : 10.1109/ipdps.2011.108. ISBN  978-1-61284-372-8. S2CID  6884123.
14. Деллинг, Дэниел; Гольдберг, Эндрю В.; Новачик, Андреас; Вернек, Ренато Ф. (2011). «PHAST: деревья кратчайших путей с аппаратным ускорением». 2011 Международный симпозиум IEEE по параллельной и распределенной обработке . стр. 921–931. дои : 10.1109/ipdps.2011.89. ISBN 978-1-61284-372-8. S2CID  1419921.
15. Фельдманн, Андреас Эмиль; Фунг, Вай Шинг; Кенеманн, Йохен; Пост, Ян (01 января 2018 г.). «$(1+\varepsilon)$-вложение графов малой размерности шоссе в графы ограниченной древовидной ширины». SIAM Journal по вычислительной технике . 47 (4): 1667–1704. arXiv : 1502.04588 . дои : 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 г. по дискретным алгоритмам. дои : 10.1137/1.9781611973075.64 .
19. Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (2016). «Настраиваемые иерархии сокращений». Журнал экспериментальной алгоритмики ACM . 21 : 1–49. arXiv : 1402.0402 . дои : 10.1145/2886843. S2CID  5247950.
20. Хаманн, Майкл; Штрассер, Бен (2018). «Деление графа пополам с оптимизацией по Парето». Журнал экспериментальной алгоритмики ACM . 23 : 1–34. arXiv : 1504.03812 . дои : 10.1145/3173045. S2CID  3395784.
21. Функе, Стефан; Сторандт, Сабина (2015). «Доказуемая эффективность сократительных иерархий с рандомизированной предварительной обработкой». Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 9472. стр. 479–490. дои : 10.1007/978-3-662-48971-0_41. ISBN 978-3-662-48971-0.
22. Блюм, Йоханнес; Функе, Стефан; Сторандт, Сабина (2018). Сублинейные пространства поиска для планирования кратчайшего пути в энергосистемах и дорожных сетях (PDF) . АААИ.

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

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

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