Иерархии сжатия

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

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

Алгоритм [ править ]

Алгоритм стягивающих иерархий (СНО) представляет собой двухэтапный подход к кратчайшему пути проблеме , состоящей из предварительной обработки фазы и фазы запроса . Поскольку дорожные сети меняются довольно редко, можно использовать больше времени (от секунд до часов), чтобы предварительно вычислить некоторые расчеты, прежде чем будет дан ответ на запросы. Используя эти предварительно вычисленные данные, можно ответить на многие запросы, занимая очень мало времени (микросекунды) каждый. ^{[1] [3]} Каналы полагаются на ярлыки для достижения этого ускорения. Ярлык соединяет две вершины, а не смежные в исходном графе. Его края вес сумма весов ребер на короткий - путь.${\ 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 \ {и, ш \}}$${\ textstyle u}$${\ textstyle w}$${\ displaystyle v}$${\ textstyle u}$${\ textstyle w}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle w}$

Исходный график - это линия (сплошная). Пунктирные края представляют собой ярлыки, серые стрелки показывают, какие два края объединены, чтобы сформировать соответствующий ярлык. Вершины нарисованы для представления порядка узлов, в котором вершины сужаются, снизу вверх. Сужение вершины вводит ярлык между и with . Сжимаем вершины и вводим одно сокращение соответственно. Стягивания , и не вводить какие - либо ярлыков и поэтому не показаны.${\ Displaystyle (а, б, в, г, д, е)}$${\ 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]

В восходящей эвристике для выбора следующей вершины для сжатия используется комбинация факторов. Поскольку количество ярлыков является основным фактором, определяющим время предварительной обработки и выполнения запросов, мы хотим, чтобы оно было как можно меньше. Таким образом, наиболее важным условием для выбора следующего узла для сжатия является чистое количество ребер, добавленных при сжатии узла . Это определяется как где - количество ярлыков, которые были бы созданы, если бы они были сокращены, и - это количество ребер, относящихся к${\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}$. Используя только этот критерий, линейный путь приведет к линейной иерархии (много уровней) без создания ярлыков. Рассматривая количество соседних вершин, которые уже сжаты, достигается равномерное сжатие и плоская иерархия (меньше уровней). Это может быть сделано, например, путем поддержания счетчика для каждого узла, который увеличивается каждый раз, когда соседняя вершина сжимается. Тогда узлы с более низкими счетчиками предпочтительнее, чем узлы с более высокими счетчиками шириной. ^[11]

С другой стороны, нисходящая эвристика дает лучшие результаты, но требует больше времени на предварительную обработку. Они классифицируют вершины, которые являются частью многих кратчайших путей, как более важные, чем те, которые необходимы только для нескольких кратчайших путей. Это можно приблизительно оценить с помощью вложенных разрезов . ^[2] Чтобы вычислить вложенное рассечение, нужно рекурсивно разделять граф на две части; которые затем разделяются на две части и так далее. То есть найдите подмножество узлов, которые при удалении из графа разделяются на две непересекающиеся части примерно равного размера, так что . Поместите все узлы в последнюю очередь${\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}$ в порядке узлов, а затем рекурсивно вычислить вложенное рассечение для и . ^[12] Интуиция заключается в том, что все запросы от одной половины графа к другой половине графа должны проходить через небольшой разделитель, и поэтому узлы в этом разделителе имеют большое значение. Вложенные разрезы могут быть эффективно рассчитаны на дорожных сетях из-за их небольших разделителей. ^[13]${\displaystyle G_{1}}$${\displaystyle G_{2}}$

Фаза запроса [ править ]

На этапе запроса выполняется двунаправленный поиск, начиная с начального узла и целевого узла на исходном графе, дополненном ярлыками, созданными на этапе предварительной обработки. ^[2] Наиболее важная вершина по кратчайшему пути между и будет либо или сами по себе или более важным , чем как и . Следовательно, минимизация вершин находится на кратчайшем пути в исходном графе и выполняется. ^[2] Это, в сочетании с тем, как создаются ярлыки, означает, что как при прямом, так и обратном поиске нужно только ослабить ребра, ведущие к более важным узлам (вверх) в иерархии, что сохраняет пространство поиска небольшим.${\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)}$^[3] Во всех путях вверх (вниз-вверх)-вниз внутренний (вниз-вверх) можно пропустить, потому что на этапе предварительной обработки был создан ярлык.

При вычислении кратчайшего пути от до , при прямом (оранжевый) и обратном (синий) поиске необходимо следовать только по ребрам, идущим вверх по иерархии. Найденный путь отмечен красным и использует один ярлык (пунктир).${\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]${\displaystyle s}$${\displaystyle s}$Обратите внимание, что это возможно, потому что порядок, в котором узлы обрабатываются на втором этапе, не зависит от исходного узла . ^[2]${\displaystyle s}$

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

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

Ссылки [ править ]

Внешние ссылки [ править ]

Реализации с открытым исходным кодом [ править ]

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