4551
правка
Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в дорожных сетях с транзитными узлами (посмотреть исходный код)
Версия от 12:47, 17 июня 2019
, 17 июня 2019→Экспериментальные результаты
Irina (обсуждение | вклад) м (→Наборы данных) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Эксперименты проводились на дорожных сетях Западной Европы и США с использованием целевой функции, учитывающей только ожидаемое время в пути. Результаты отражают различные компромиссы между средним временем выполнения запроса (от 5 до 63 микросекунд для США), продолжительностью предварительной обработки (от 59 до 1200 минут) и затратами на хранение (от 21 до 244 байт на узел). Для варианта, использующего три уровня и настроенного для минимального времени выполнения запроса, в таблицах 1 и 2 показана статистика для продолжительности предварительной обработки и эффективности запросов, соответственно. Среднее время выполнения запроса, около 5 микросекунд, на шесть порядков величины меньше, чем у алгоритма Дейкстры. На рис. 2 для каждого ранга r на оси x приведено распределение для 1000 запросов со случайной исходной точкой s и целевым узлом t, для нахождения ответа на которые алгоритму Дейкстры требуется r итераций. Можно различить три уровня маршрутизации с использованием транзитных узлов с небольшими транзитными зонами между ними: для больших рангов достаточно обращения только к первичному уровню, что дает время выполнения запроса около 5 микросекунд, для меньших рангов требуются дополнительые уровни и медианное время выполнения запроса возрастает до 20 микросекунд. | |||
Таблица 1. Статистика по предварительной обработке. Представлены размер множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки | |||
== Наборы данных == | == Наборы данных == | ||