Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями

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

! colspan="2" | Слой 1

! colspan="3" | Слой 2

! colspan="2" | Слой 3

Таблица 1. Статистика по предварительной обработке. Представлены размер множеств транзитных узлов, число записей в таблицах расстояний и среднее число узлов доступа на соответствующем уровне, а также расход памяти и время предварительной обработки

! слой 1

! слой 2

! слой 3