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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

Этап запроса

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

Поиск пути

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

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

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

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

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

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

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

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

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

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

Теория

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

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

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

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

Предварительная обработка временной сложности иерархий сокращения
Алгоритм	Год	Временная сложность
Рандомизированная обработка ^{[ 21 ]}	2015	$O(n^{2}\log n+nm)$

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

Сложность времени запроса сокращающихся иерархий
Алгоритм/метод анализа	Год	Временная сложность	Примечания
Графы ограниченного роста ^{[ 22 ]}	2018	$O({\sqrt {n}}\log n)$
Настраиваемые иерархии сокращений ^{[ 19 ]}^{[ 20 ]}	2013-2018	$O(td^{2})$ или $O((tw*\log n)^{2})$ .	$td$ это глубина дерева и $tw$ это ширина дерева
Рандомизированная обработка ^{[ 21 ]}	2015	${\sqrt {n}}(6\ln(1/p)\log {\sqrt {n}}+2)$	Точно, без О-нотации; сработает с большой вероятностью
Модифицированный ШАРК ^{[ 18 ]}	2010	$O((h\log n\log D)^{2})$	Полиномиальная предварительная обработка
Модифицированный ШАРК ^{[ 18 ]}	2010	$O((h\log D)^{2})$	Суперполиномиальная предварительная обработка

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (5 апреля 2016 г.). «Настраиваемые иерархии сокращений». Журнал экспериментальной алгоритмики . 21 (1): 1–49. arXiv : 1402.0402 . дои : 10.1145/2886843 . S2CID 5247950 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р Баст, Ханна; Деллинг, Дэниел; Гольдберг, Эндрю В.; Мюллер-Ханнеманн, Матиас; Пайор, Томас; Сандерс, Питер; Вагнер, Доротея; Вернек, Ренато Ф. (2016). «Планирование маршрутов в транспортных сетях». Алгоритмическая инженерия . Конспекты лекций по информатике. Том. 9220. стр. 19–80. arXiv : 1504.05140 . дои : 10.1007/978-3-319-49487-6_2 . ISBN 978-3-319-49486-9 . S2CID 14384915 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Гейсбергер, Роберт; Сандерс, Питер; Шультес, Доминик; Веттер, Кристиан (2012). «Точная прокладка маршрутов в крупных дорожных сетях с использованием иерархий сжатия» . Транспортная наука . 46 (3): 388–404. дои : 10.1287/trsc.1110.0401 .
^ Деллинг, Дэниел; Сандерс, Питер; Шультес, Доминик; Вагнер, Доротея (2009). «Алгоритмы планирования инженерных маршрутов». Алгоритмы больших и сложных сетей . Конспекты лекций по информатике. Том. 5515. стр. 117–139. дои : 10.1007/978-3-642-02094-0_7 . ISBN 978-3-642-02093-3 .
^ «OSRM – Маршрутизатор с открытым исходным кодом» .
^ «Вики – OpenTripPlanner» .
^ «Веб – ГрафХоппер» .
^ «GitHub – Темпус» . Гитхаб . 9 сентября 2021 г.
^ «GitHub — RoutingKit» . Гитхаб . 24 января 2022 г.
^ Бауэр, Рейнхард; Деллинг, Дэниел; Сандерс, Питер; Шифердекер, Деннис; Шультес, Доминик; Вагнер, Доротея (01 марта 2010 г.). «Сочетание иерархических и целенаправленных методов ускорения алгоритма Дейкстры» . Журнал экспериментальной алгоритмики . 15 : 2.1. дои : 10.1145/1671970.1671976 . ISSN 1084-6654 . S2CID 1661292 .
^ Гейсбергер, Роберт; Сандерс, Питер; Шультес, Доминик; Деллинг, Дэниел (2008). «Иерархии сжатия: более быстрая и простая иерархическая маршрутизация в дорожных сетях». В МакГеоче, Кэтрин С. (ред.). Экспериментальные алгоритмы . Конспекты лекций по информатике. Том. 5038. Шпрингер Берлин Гейдельберг. стр. 319–333. дои : 10.1007/978-3-540-68552-4_24 . ISBN 9783540685524 . S2CID 777101 .
^ Бауэр, Рейнхард; Колумб, Тобиас; Раттер, Игнац; Вагнер, Доротея (13 сентября 2016 г.). «Размер пространства поиска в сокращающихся иерархиях» . Теоретическая информатика . 645 : 112–127. дои : 10.1016/j.tcs.2016.07.003 . ISSN 0304-3975 .
^ Деллинг, Дэниел; Гольдберг, Эндрю В.; Разенштейн, Илья; Вернек, Ренато Ф. (май 2011 г.). «Разбиение графа с естественными разрезами». 2011 Международный симпозиум IEEE по параллельной и распределенной обработке . стр. 1135–1146. CiteSeerX 10.1.1.385.1580 . дои : 10.1109/ipdps.2011.108 . ISBN 978-1-61284-372-8 . S2CID 6884123 .
^ Деллинг, Дэниел; Гольдберг, Эндрю В.; Новачик, Андреас; Вернек, Ренато Ф. (2011). «PHAST: деревья кратчайших путей с аппаратным ускорением». 2011 Международный симпозиум IEEE по параллельной и распределенной обработке . стр. 921–931. дои : 10.1109/ipdps.2011.89 . ISBN 978-1-61284-372-8 . S2CID 1419921 .
^ Фельдманн, Андреас Эмиль; Фунг, Вай Шинг; Кенеманн, Йохен; Пост, Ян (01 января 2018 г.). «$(1+\varepsilon)$-вложение графов малой размерности шоссе в графы ограниченной древовидной ширины» . SIAM Journal по вычислительной технике . 47 (4): 1667–1704. arXiv : 1502.04588 . дои : 10.1137/16M1067196 . ISSN 0097-5397 . S2CID 11339698 .
^ Блюм, Йоханнес (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 .
^ Блюм, Джон; Диссер, Янн; Фельдманн, Андреас Эмиль; Гупта, Сиддхартх; Зых-Павлевич, Анна (2022). «О разреженных наборах ударов: от справедливого покрытия вершин до измерения шоссе». В Делле, Хольгер; Недерлоф, Йеспер (ред.). 17-й Международный симпозиум по параметризованным и точным вычислениям (IPEC 2022) . Лейбниц Международные труды по информатике. Том 249. Дагштуль, Германия: Замок Дагштуль – Центр информатики Лейбница. стр. 5:1–5:23. doi : 10.4230/LIPIcs.IPEC.2022.5 . ISBN 978-3-95977-260-0 .
^ Перейти обратно: ^а ^б ^с Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю (2010). Размерность шоссе, кратчайшие пути и доказуемо эффективные алгоритмы (PDF) . Материалы ежегодного симпозиума ACM-SIAM 2010 г. по дискретным алгоритмам. дои : 10.1137/1.9781611973075.64 .
^ Перейти обратно: ^а ^б Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (2016). «Настраиваемые иерархии сокращений». Журнал экспериментальной алгоритмики ACM . 21 : 1–49. arXiv : 1402.0402 . дои : 10.1145/2886843 . S2CID 5247950 .
^ Перейти обратно: ^а ^б Хаманн, Майкл; Штрассер, Бен (2018). «Деление графа пополам с оптимизацией по Парето». Журнал экспериментальной алгоритмики ACM . 23 : 1–34. arXiv : 1504.03812 . дои : 10.1145/3173045 . S2CID 3395784 .
^ Перейти обратно: ^а ^б Функе, Стефан; Сторандт, Сабина (2015). «Доказуемая эффективность сократительных иерархий с рандомизированной предварительной обработкой». Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 9472. стр. 479–490. дои : 10.1007/978-3-662-48971-0_41 . ISBN 978-3-662-48971-0 .
^ Блюм, Йоханнес; Функе, Стефан; Сторандт, Сабина (2018). Сублинейные пространства поиска для планирования кратчайшего пути в энергосистемах и дорожных сетях (PDF) . АААИ.

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

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

[dibbelt2015-1] Перейти обратно: ^а ^б ^с ^д Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (5 апреля 2016 г.). «Настраиваемые иерархии сокращений». Журнал экспериментальной алгоритмики . 21 (1): 1–49. arXiv : 1402.0402 . дои : 10.1145/2886843 . S2CID 5247950 .

[bast2016-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р Баст, Ханна; Деллинг, Дэниел; Гольдберг, Эндрю В.; Мюллер-Ханнеманн, Матиас; Пайор, Томас; Сандерс, Питер; Вагнер, Доротея; Вернек, Ренато Ф. (2016). «Планирование маршрутов в транспортных сетях». Алгоритмическая инженерия . Конспекты лекций по информатике. Том. 9220. стр. 19–80. arXiv : 1504.05140 . дои : 10.1007/978-3-319-49487-6_2 . ISBN 978-3-319-49486-9 . S2CID 14384915 .

[geisberger12-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Гейсбергер, Роберт; Сандерс, Питер; Шультес, Доминик; Веттер, Кристиан (2012). «Точная прокладка маршрутов в крупных дорожных сетях с использованием иерархий сжатия» . Транспортная наука . 46 (3): 388–404. дои : 10.1287/trsc.1110.0401 .

[delling09-4] Деллинг, Дэниел; Сандерс, Питер; Шультес, Доминик; Вагнер, Доротея (2009). «Алгоритмы планирования инженерных маршрутов». Алгоритмы больших и сложных сетей . Конспекты лекций по информатике. Том. 5515. стр. 117–139. дои : 10.1007/978-3-642-02094-0_7 . ISBN 978-3-642-02093-3 .

[5] «OSRM – Маршрутизатор с открытым исходным кодом» .

[6] «Вики – OpenTripPlanner» .

[7] «Веб – ГрафХоппер» .

[8] «GitHub – Темпус» . Гитхаб . 9 сентября 2021 г.

[RoutingKit-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. Дагштуль, Германия: Замок Дагштуль – Центр информатики Лейбница. стр. 5:1–5:23. doi : 10.4230/LIPIcs.IPEC.2022.5 . ISBN 978-3-95977-260-0 .

[Abraham2010-18] Перейти обратно: ^а ^б ^с Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю (2010). Размерность шоссе, кратчайшие пути и доказуемо эффективные алгоритмы (PDF) . Материалы ежегодного симпозиума ACM-SIAM 2010 г. по дискретным алгоритмам. дои : 10.1137/1.9781611973075.64 .

[ReferenceA-19] Перейти обратно: ^а ^б Диббелт, Джулиан; Штрассер, Бен; Вагнер, Доротея (2016). «Настраиваемые иерархии сокращений». Журнал экспериментальной алгоритмики ACM . 21 : 1–49. arXiv : 1402.0402 . дои : 10.1145/2886843 . S2CID 5247950 .

[ReferenceB-20] Перейти обратно: ^а ^б Хаманн, Майкл; Штрассер, Бен (2018). «Деление графа пополам с оптимизацией по Парето». Журнал экспериментальной алгоритмики ACM . 23 : 1–34. arXiv : 1504.03812 . дои : 10.1145/3173045 . S2CID 3395784 .

[Funke2015-21] Перейти обратно: ^а ^б Функе, Стефан; Сторандт, Сабина (2015). «Доказуемая эффективность сократительных иерархий с рандомизированной предварительной обработкой». Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 9472. стр. 479–490. дои : 10.1007/978-3-662-48971-0_41 . ISBN 978-3-662-48971-0 .

[22] Блюм, Йоханнес; Функе, Стефан; Сторандт, Сабина (2018). Сублинейные пространства поиска для планирования кратчайшего пути в энергосистемах и дорожных сетях (PDF) . АААИ.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]