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

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

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

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

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

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

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