4551
правка
Разработка алгоритмов для применения в больших сетях: различия между версиями
Материал из WEGA
Разработка алгоритмов для применения в больших сетях (посмотреть исходный код)
Версия от 12:28, 15 января 2019
, 15 января 2019→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Для эффективного управления работой приложений в больших сетях об…») |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
== Основные результаты == | == Основные результаты == | ||
Все обсуждаемые результаты касаются ответов на запросы о нахождении оптимальных (либо точных, либо сохраняющих расстояния) кратчайших путей в упомянутом сценарии с большим числом запросов и основываются на следующем базовом подходе. Выполняется предварительная обработка входной сети G = (V, E), результатом которой становится структура данных размера O(|V| + |E|) (т.е. линейная относительно размера G). Эта структура данных содержит дополнительную информацию по поводу определенных кратчайших путей, которая впоследствии может быть использована в ходе ответов на запросы. | |||
В зависимости от заранее вычисленной дополнительной информации и от способа ответа на запросы о кратчайшем пути можно выделить два разных подхода. В рамках первого подхода, с аннотированием графа, дополнительная информация связывается с вершинами или ребрами графа. Затем к алгоритму Дейкстры применяются техники ускорения, которые на основе этой информации быстро определяют, в какой части графа не требуется производить поиск. В рамках второго подхода иерархически строится дополнительный граф. Запрос о кратчайшем пути выполняется только на небольшой части графа G0 при помощи алгоритма Дейкстры, дополненного эвристика для дальнейшего сокращения времени выполнения запроса. | |||
Основные результаты применения первого [3, 4, 9, 11] и второго [1, 2, 5, 7, 8, 10] подходов, а также вопросы моделирования будут обсуждены далее. | |||
'''Первый подход (аннотирование графа)''' | |||
Первая работа в рамках этого подхода посвящена исследованию крупных железнодорожный сетей [9]. В этой статье были введены две новые эвристики: ограничение угла (эта эвристика стремится сократить пространство поиска, пользуясь информацией о геометрическом расположении вершин) и выбор станций (выбирается подмножество вершин, для которого вычисляются кратчайшие пути между всеми вершинами). Эти две эвристики в сочетании с классическим целеориентированным поиском или A*-поиском оказались очень эффективными. Более того, они стимулировали создание двух важных обобщений [10, 11], позволивших ускорить выполнение запросов о кратчайшем пути. | |||
Полное исследование геометрических эвристик было проведено в работе [11], в которой рассматривались уличная и железнодорожная сети. В этой работе было показано, что пространство поиска у алгоритма Дейкстры можно значительно уменьшить (до 5-10% от исходного размера графа) в результате извлечения геометрической информации из заданного расположения графа и сохранения заранее вычисленной информации о кратчайших путях в геометрических объектах, называемых контейнерами. Исследовался также динамический вариант этой задачи, в котором стоимости ребер могли изменяться, а геометрические контейнеры нужно было обновлять. | |||
Мощная модификация классического алгоритма Дейкстры, получившая название маршрутизации на основе достижимости, была представлена в [4]. Каждой вершине присваивается так называемое значение достижимости, определяющее, следует ли рассматривать конкретную вершину в ходе работы алгоритма Дейкстры. Вершина исключается из рассмотрения, если ее значение достижимости невелико – иначе говоря, если она не входит в какой-либо путь, достаточно длинный, чтобы пригодиться при выполнении текущего запроса. | |||
Важное расширение классического алгоритма A*-поиска, использующее ориентиры (избранные вершины, как в работах [9, 10]) и неравенство треугольника применительно к расстояниям по кратчайшим путям, было предложено в [3]. Ориентиры и неравенство треугольника позволяют улучшить нижние границы и, в силу этого, ускорить A*-поиск. | |||
'''Второй подход (дополнительный граф)''' | |||
