Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
Таблица 1. Статистика по предварительной обработке. Представлены размер множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки | Таблица 1. Статистика по предварительной обработке. Представлены размер множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки | ||
Таблица 2. Эффективность алгоритма маршрутизации при помощи транзитных узлов на 10 000 000 случайных запросов. Столбец для уровня i показывает, на какую часть запросов был дан точный ответ с использованием только информации, доступной на уровнях < i. Каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно | |||
Рисунок 2. Распределение времени ответа на запросы как функция от ранга Дейкстры – количеству итераций, которое требуется алгоритму Дейкстры для решения данного экземпляра задачи. Распределения представлены в виде «ящика с усами»: каждый «ящик» простирается от нижнего до верхнего квартиля и содержит медианное значение, «усы» простираются до минимального и максимального значений, исключая выбросы, изображенные отдельно | |||
== Наборы данных == | == Наборы данных == | ||