Разработка алгоритмов для применения в больших сетях: различия между версиями

Поиск наилучшего пути (или оптимального маршрута) подразумевает решение задачи о поиске пути с минимальной стоимостью (или кратчайшего пути) на подходящим образом определенном ориентированном графе с неотрицательными стоимостями ребер. Это, в свою очередь, сводится к базовой алгоритмической задаче, которой в данной ситуации является задача нахождения кратчайших путей с единственным источником и единственной целью.

Прямолинейный подход с предварительным вычислением и хранением кратчайших путей между всеми парами вершин позволяет отвечать на запросы о кратчайших путях с оптимальной скоростью, однако он требует квадратичного объема памяти, что для орграфов с числом вершин более 105 делает его крайне непрактичным для использования в больших и очень больших сетях. По этой причине основная цель почти всех известных подходов заключается в максимально возможном сокращении требований к памяти. Это, в свою очередь, подразумевает возможность применения масштабной (по времени) предварительной обработки, не требующей увеличения объема памяти, для ускорения выполнения запросов.

Наиболее распространенный подход к нахождению ответов на запросы о кратчайшем пути основан на алгоритме Дейкстры и его вариациях. Таким образом, главная задача заключается в уменьшении пространства поиска алгоритма (количества посещенных вершин), поскольку это автоматически способствует сокращению времени выполнения запросов.

Все обсуждаемые результаты касаются ответов на запросы о нахождении оптимальных (либо точных, либо сохраняющих расстояния) кратчайших путей в упомянутом сценарии с большим числом запросов и основываются на следующем базовом подходе. Выполняется предварительная обработка входной сети G = (V, E), результатом которой становится структура данных размера O(|V| + |E|) (т.е. линейная относительно размера G). Эта структура данных содержит дополнительную информацию по поводу определенных кратчайших путей, которая впоследствии может быть использована в ходе ответов на запросы.

В зависимости от заранее вычисленной дополнительной информации и от способа ответа на запросы о кратчайшем пути можно выделить два разных подхода. В рамках первого подхода, с аннотированием графа, дополнительная информация связывается с вершинами или ребрами графа. Затем к алгоритму Дейкстры применяются техники ускорения, которые на основе этой информации быстро определяют, в какой части графа не требуется производить поиск. В рамках второго подхода иерархически строится дополнительный граф. Запрос о кратчайшем пути выполняется только на небольшой части графа G0 при помощи алгоритма Дейкстры, дополненного эвристика для дальнейшего сокращения времени выполнения запроса.

Первая работа в рамках этого подхода посвящена исследованию крупных железнодорожный сетей [9]. В этой статье были введены две новые эвристики: ограничение угла (эта эвристика стремится сократить пространство поиска, пользуясь информацией о геометрическом расположении вершин) и выбор станций (выбирается подмножество вершин, для которого вычисляются кратчайшие пути между всеми вершинами). Эти две эвристики в сочетании с классическим целеориентированным поиском или A*-поиском оказались очень эффективными. Более того, они стимулировали создание двух важных обобщений [10, 11], позволивших ускорить выполнение запросов о кратчайшем пути.

Полное исследование геометрических эвристик было проведено в работе [11], в которой рассматривались уличная и железнодорожная сети. В этой работе было показано, что пространство поиска у алгоритма Дейкстры можно значительно уменьшить (до 5-10% от исходного размера графа) в результате извлечения геометрической информации из заданного расположения графа и сохранения заранее вычисленной информации о кратчайших путях в геометрических объектах, называемых контейнерами. Исследовался также динамический вариант этой задачи, в котором стоимости ребер могли изменяться, а геометрические контейнеры нужно было обновлять.

Мощная модификация классического алгоритма Дейкстры, получившая название маршрутизации на основе достижимости, была представлена в [4]. Каждой вершине присваивается так называемое значение достижимости, определяющее, следует ли рассматривать конкретную вершину в ходе работы алгоритма Дейкстры. Вершина исключается из рассмотрения, если ее значение достижимости невелико – иначе говоря, если она не входит в какой-либо путь, достаточно длинный, чтобы пригодиться при выполнении текущего запроса.

Первая работа в рамках этого подхода [10] представляет новую технику иерархической декомпозиции, получившую название многоуровневого графа. Многоуровневый граф M представляет собой орграф, определяемый последовательностью подмножеств V, множество E которого расширено посредством дополнения несколькими уровнями ребер. Это позволяет в ходе ответа на запрос эффективно строить подграф M, значительно меньшего размера по сравнению с G, в котором расстояние по кратчайшему пути между любыми двумя вершинами равно расстоянию по кратчайшему пути между теми же вершинами в графе G. Дальнейшие улучшения этого подхода были недавно предложены в работе [1]. Дальнейшим развитием первоначальной идеи стало введение многоуровневых графов с наложениями [5]. В таком графе иерархия декомпозиции не определяется информацией, относящейся к конкретной области применения, как это было в случае [9, 10].