4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дан ориентированный граф G = (V, E) с неотрицательными весами ребер. Необходимо вычислить кратчайший путь по графу G из вершины-источника s в целевую вершину t для заданных s и t. Предполагая, что граф G остается | Пусть дан ориентированный граф G = (V, E) с неотрицательными весами ребер. Необходимо вычислить кратчайший путь по графу G из вершины-источника s в целевую вершину t для заданных s и t. Предполагая, что граф G остается неизменным и что будет много запросов с указанием источника и цели, имеет смысл потратить некоторое время на этап предварительной обработки, который позволит очень быстро отвечать на запросы. На выходе, в зависимости от приложения, ожидается либо полное описание кратчайшего пути, либо только его длина d(s, t). | ||
Строка 35: | Строка 35: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
До сих пор неизвестно, можно ли найти более эффективные множества транзитных узлов или лучший фильтр локальности для | До сих пор неизвестно, можно ли найти более эффективные множества транзитных узлов или лучший фильтр локальности для дальнейшего улучшения производительности. Неясно также, может ли маршрутизация при помощи транзитных узлов успешно применяться к другим типам графов, отличным от дорожных сетей. В этом контексте было бы желательно получить какие-либо теоретические гарантии, применимые к любому графу, обладающему определенными свойствами. Для некоторых практических областей применения пригодилась бы ''динамическая'' версия маршрутизации при помощи транзитных узлов для работы с сетями, зависящими от времени, или непредсказуемыми изменениями весов дуг, вызванными, к примеру, заторами на дорогах. Последний сценарий может обрабатываться с помощью родственного подхода из работы [8], однако он работает гораздо медленнее, чем маршрутизация при помощи транзитных узлов. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Эксперименты проводились на дорожных сетях Западной Европы и США с использованием целевой функции, учитывающей только ожидаемое время в пути. Результаты отражают различные компромиссы между средним временем выполнения запроса (от 5 до 63 микросекунд для США), продолжительностью предварительной обработки (от 59 до 1200 минут) и затратами на хранение (от 21 до 244 байт на узел). Для варианта, использующего три уровня и настроенного для минимального времени выполнения запроса, в таблицах 1 и 2 показана статистика для продолжительности предварительной обработки и эффективности запросов, соответственно. Среднее время выполнения запроса, около 5 микросекунд, на шесть порядков величины меньше, чем у алгоритма Дейкстры. На рис. 2 для каждого ранга r на оси x приведено распределение для 1000 запросов со случайной исходной точкой s и целевым узлом t, для нахождения ответа на которые алгоритму Дейкстры требуется r итераций. Можно различить три уровня маршрутизации при помощи транзитных узлов с небольшими | Эксперименты проводились на дорожных сетях Западной Европы и США с использованием целевой функции, учитывающей только ожидаемое время в пути. Результаты отражают различные компромиссы между средним временем выполнения запроса (от 5 до 63 микросекунд для США), продолжительностью предварительной обработки (от 59 до 1200 минут) и затратами на хранение (от 21 до 244 байт на узел). Для варианта, использующего три уровня и настроенного для минимального времени выполнения запроса, в таблицах 1 и 2 показана статистика для продолжительности предварительной обработки и эффективности запросов, соответственно. Среднее время выполнения запроса, около 5 микросекунд, на шесть порядков величины меньше, чем у алгоритма Дейкстры. На рис. 2 для каждого ранга r на оси x приведено распределение для 1000 запросов со случайной исходной точкой s и целевым узлом t, для нахождения ответа на которые алгоритму Дейкстры требуется r итераций. Можно различить три уровня маршрутизации при помощи транзитных узлов с небольшими зонами перехода между ними: для больших рангов достаточно обращения только к первичному уровню, что дает время выполнения запроса около 5 микросекунд, для меньших рангов требуются дополнительные уровни и медианное время выполнения запроса возрастает до 20 микросекунд. | ||
Строка 44: | Строка 44: | ||
|- | |- | ||
! | ! | ||
! colspan="2" | | ! colspan="2" | уровень 1 | ||
! colspan="3" | | ! colspan="3" | уровень 2 | ||
! colspan="2" | | ! colspan="2" | уровень 3 | ||
! | ! | ||
! | ! | ||
Строка 84: | Строка 84: | ||
|} | |} | ||
Таблица 1. Статистика по предварительной обработке. Представлены | Таблица 1. Статистика по предварительной обработке. Представлены мощность множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки | ||
Строка 92: | Строка 92: | ||
! к-во узлов | ! к-во узлов | ||
! к-во ребер | ! к-во ребер | ||
! | ! уровень 1 | ||
! | ! уровень 2 | ||
! | ! уровень 3 | ||
! запрос | ! запрос | ||
|- | |- | ||
Строка 114: | Строка 114: | ||
|} | |} | ||
Таблица 2. Эффективность алгоритма маршрутизации при помощи транзитных узлов на 10 000 000 случайных запросов. Столбец для уровня i показывает, на какую часть запросов был дан точный ответ с использованием только информации, доступной на уровнях | Таблица 2. Эффективность алгоритма маршрутизации при помощи транзитных узлов на 10 000 000 случайных запросов. Столбец для уровня i показывает, на какую часть запросов был дан точный ответ с использованием только информации, доступной на уровнях не выше i. Каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно | ||
[[Файл:RRNTN_2.png]] | [[Файл:RRNTN_2.png]] | ||
Рисунок 2. Распределение времени ответа на запросы как функция от ранга Дейкстры – | Рисунок 2. Распределение времени ответа на запросы как функция от ранга Дейкстры – количества итераций, которое требуется алгоритму Дейкстры для решения данного экземпляра задачи. Распределения представлены в виде «ящика с усами»: каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно | ||
== Наборы данных == | == Наборы данных == |
правок