4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
Строка 6: | Строка 6: | ||
Поиск наилучшего пути (или оптимального маршрута) подразумевает решение задачи о поиске пути с минимальной стоимостью (или кратчайшего пути) на подходящим образом определенном ориентированном графе с неотрицательными стоимостями ребер. Это, в свою очередь, сводится к базовой алгоритмической задаче, которой в данной ситуации является задача нахождения кратчайших путей с единственным источником и единственной целью. | Поиск наилучшего пути (или оптимального маршрута) подразумевает решение задачи о поиске пути с минимальной стоимостью (или кратчайшего пути) на подходящим образом определенном ориентированном графе ([[орграф|орграфе]]) с неотрицательными стоимостями ребер. Это, в свою очередь, сводится к базовой алгоритмической задаче, которой в данной ситуации является задача нахождения кратчайших путей с единственным источником и единственной целью. | ||
Прямолинейный подход с предварительным вычислением и хранением кратчайших путей между всеми парами вершин позволяет отвечать на запросы о кратчайших путях с оптимальной скоростью, однако он требует квадратичного объема памяти, что для орграфов с числом вершин более | Прямолинейный подход с предварительным вычислением и хранением кратчайших путей между всеми парами вершин позволяет отвечать на запросы о кратчайших путях с оптимальной скоростью, однако он требует квадратичного объема памяти, что для орграфов с числом вершин более <math>10^5</math> делает его крайне непрактичным для использования в больших и очень больших сетях. По этой причине основная цель почти всех известных подходов заключается в максимально возможном сокращении требований к памяти. Это, в свою очередь, подразумевает возможность применения масштабной (по времени) предварительной обработки, не требующей увеличения объема памяти, для ускорения выполнения запросов. | ||
Наиболее распространенный подход к нахождению ответов на запросы о кратчайшем пути основан на алгоритме Дейкстры и его вариациях. Таким образом, главная задача заключается в уменьшении пространства поиска алгоритма (количества посещенных вершин), поскольку это автоматически способствует сокращению времени выполнения запросов. | Наиболее распространенный подход к нахождению ответов на запросы о кратчайшем пути основан на алгоритме Дейкстры и его вариациях. Таким образом, главная задача заключается в уменьшении ''пространства поиска'' алгоритма (количества посещенных вершин), поскольку это автоматически способствует сокращению времени выполнения запросов. | ||
== Основные результаты == | == Основные результаты == | ||
Все обсуждаемые результаты касаются ответов на запросы о нахождении оптимальных ( | Все обсуждаемые результаты касаются ответов на запросы о нахождении ''оптимальных'' (или ''точных'' либо ''сохраняющих расстояния'') кратчайших путей в упомянутом сценарии с большим числом запросов и основываются на следующем базовом подходе. Выполняется предварительная обработка входной сети G = (V, E), результатом которой становится структура данных размера O(|V| + |E|) (т. е. линейная относительно размера G). Эта структура данных содержит дополнительную информацию по поводу определенных кратчайших путей, которая впоследствии может быть использована в ходе ответов на запросы. | ||
В зависимости от заранее вычисленной дополнительной информации и от способа ответа на запросы о кратчайшем пути можно выделить два разных подхода. В рамках первого подхода, с аннотированием графа, дополнительная информация связывается с вершинами или ребрами графа. Затем к алгоритму Дейкстры применяются техники ускорения, которые на основе этой информации быстро определяют, в какой части графа не требуется производить поиск. В рамках второго подхода иерархически строится дополнительный граф. Запрос о кратчайшем пути выполняется только на небольшой части графа | В зависимости от заранее вычисленной дополнительной информации и от способа ответа на запросы о кратчайшем пути можно выделить два разных подхода. В рамках первого подхода, с ''аннотированием графа'', дополнительная информация связывается с вершинами или ребрами графа. Затем к алгоритму Дейкстры применяются техники ускорения, которые на основе этой информации быстро определяют, в какой части графа не требуется производить поиск. В рамках второго подхода иерархически строится ''дополнительный граф'' G'. Запрос о кратчайшем пути выполняется только на небольшой части графа G' при помощи алгоритма Дейкстры, дополненного эвристиками для дальнейшего сокращения времени выполнения запроса. | ||
Строка 26: | Строка 26: | ||
'''Первый подход (аннотирование графа)''' | '''Первый подход (аннотирование графа)''' | ||
Первая работа в рамках этого подхода посвящена исследованию крупных железнодорожный сетей [9]. В этой статье были введены две новые эвристики: ограничение угла (эта эвристика стремится сократить пространство поиска, пользуясь информацией о геометрическом расположении вершин) и выбор станций (выбирается подмножество вершин, для которого вычисляются кратчайшие пути между всеми вершинами). Эти две эвристики в сочетании с классическим целеориентированным поиском или A*-поиском оказались очень эффективными. Более того, они стимулировали создание двух важных обобщений [10, 11], позволивших ускорить выполнение запросов о кратчайшем пути. | Первая работа в рамках этого подхода посвящена исследованию крупных железнодорожный сетей [9]. В этой статье были введены две новые эвристики: ''ограничение угла'' (эта эвристика стремится сократить пространство поиска, пользуясь информацией о геометрическом расположении вершин) и ''выбор станций'' (выбирается подмножество вершин, для которого предварительно вычисляются кратчайшие пути между всеми вершинами). Эти две эвристики в сочетании с классическим ''целеориентированным поиском'' или ''A*-поиском'' оказались очень эффективными. Более того, они стимулировали создание двух важных обобщений [10, 11], позволивших ускорить выполнение запросов о кратчайшем пути. | ||
Полное исследование геометрических эвристик было проведено в работе [11], в которой рассматривались уличная и железнодорожная сети. В этой работе было показано, что пространство поиска у алгоритма Дейкстры можно значительно уменьшить (до 5-10% от исходного размера графа) в результате извлечения геометрической информации из заданного расположения графа и сохранения заранее вычисленной информации о кратчайших путях в геометрических объектах, называемых контейнерами. Исследовался также динамический вариант этой задачи, в котором стоимости ребер могли изменяться, а геометрические контейнеры нужно было обновлять. | Полное исследование геометрических эвристик было проведено в работе [11], в которой рассматривались уличная и железнодорожная сети. В этой работе было показано, что пространство поиска у алгоритма Дейкстры можно значительно уменьшить (до 5-10% от исходного размера графа) в результате извлечения геометрической информации из заданного расположения графа и сохранения заранее вычисленной информации о кратчайших путях в геометрических объектах, называемых ''контейнерами''. Исследовался также динамический вариант этой задачи, в котором стоимости ребер могли изменяться, а геометрические контейнеры нужно было обновлять. | ||
Мощная модификация классического алгоритма Дейкстры, получившая название маршрутизации на основе достижимости, была представлена в [4]. Каждой вершине присваивается так называемое значение достижимости, определяющее, следует ли рассматривать конкретную вершину в ходе работы алгоритма Дейкстры. Вершина исключается из рассмотрения, если ее значение достижимости невелико – иначе говоря, если она не входит в какой-либо путь, достаточно длинный, чтобы пригодиться при выполнении текущего запроса. | Мощная модификация классического алгоритма Дейкстры, получившая название ''маршрутизации на основе достижимости'', была представлена в [4]. Каждой вершине присваивается так называемое ''значение достижимости'', определяющее, следует ли рассматривать конкретную вершину в ходе работы алгоритма Дейкстры. Вершина исключается из рассмотрения, если ее значение достижимости невелико – иначе говоря, если она не входит в какой-либо путь, достаточно длинный, чтобы пригодиться при выполнении текущего запроса. | ||
Строка 40: | Строка 40: | ||
'''Второй подход (дополнительный граф)''' | '''Второй подход (дополнительный граф)''' | ||
Первая работа в рамках этого подхода [10] представляет новую технику иерархической декомпозиции, получившую название многоуровневого графа. Многоуровневый граф M представляет собой орграф, определяемый последовательностью подмножеств V, множество E которого расширено посредством дополнения несколькими уровнями ребер. Это позволяет в ходе ответа на запрос эффективно строить подграф M, значительно меньшего размера по сравнению с G, в котором расстояние по кратчайшему пути между любыми двумя вершинами равно расстоянию по кратчайшему пути между теми же вершинами в графе G. Дальнейшие улучшения этого подхода были недавно предложены в работе [1]. Дальнейшим развитием первоначальной идеи стало введение многоуровневых графов с наложениями [5]. В таком графе иерархия декомпозиции не определяется информацией, относящейся к конкретной области применения, как это было в случае [9, 10]. | Первая работа в рамках этого подхода [10] представляет новую технику иерархической декомпозиции, получившую название ''многоуровневого графа''. Многоуровневый граф M представляет собой орграф, определяемый последовательностью подмножеств V, множество E которого расширено посредством дополнения несколькими уровнями ребер. Это позволяет в ходе ответа на запрос эффективно строить подграф M, значительно меньшего размера по сравнению с G, в котором расстояние по кратчайшему пути между любыми двумя вершинами равно расстоянию по кратчайшему пути между теми же вершинами в графе G. Дальнейшие улучшения этого подхода были недавно предложены в работе [1]. Дальнейшим развитием первоначальной идеи стало введение многоуровневых графов с наложениями [5]. В таком графе иерархия декомпозиции не определяется информацией, относящейся к конкретной области применения, как это было в случае [9, 10]. | ||
правка