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

Пример приведен на рис. 1. Зная длину кратчайшего пути, можно эффективно вывести его полное описание при помощи итеративных поисков по таблице и заранее вычисленных представлений путей между транзитными вершинами. При условии, что вышеупомянутые наблюдения справедливы, а процент ложноположительных срабатываний мал, данный алгоритм работает очень эффективно, поскольку значительная часть всех запросов может быть обработана в строке 1, <math>d_{\mathcal{T}} (s, t)</math> может быть вычислено при помощи нескольких поисков в таблице, а источник и цельоставшихся запросов в строке 2 оказываются достаточно близки. И в самом деле, поиск ответов на оставшиеся запросы может быть ускорен за счет введения вторичного уровня маршрутизации транзитных узлов, основанного на множестве ''вторичных транзитных узлов'' <math>{\mathcal{T}}_2 \supset {\mathcal{T}}</math>. В данном случае нет необходимости в вычислении и хранении полной таблицы расстояний <math>{\mathcal{T}}_2 \times {\mathcal{T}}_2</math>, достаточно хранить только расстояния <math>\{d(u, v) | u, v \in {\mathcal{T}}_2 \and d(u, v) \ne d_{{\mathcal{T}}}(s, t) \}</math>, т. е. расстояния, которые не могут быть получены при помощи первичного уровня. Аналогичным образом можно добавить и более глубокие уровни.

До сих пор неизвестно, можно ли найти более эффективные множества транзитных узлов или лучший фильтр локальности для дальнейшейго улучшения производительности. Неясно также, может ли маршрутизация с использованием транзитных узлов успешно применяться к другим типам графов, отличным от дорожных сетей. В этом контексте было бы желательно получить какие-либо теоретические гарантии, применимые к любому графу, обладающему определенными свойствами. Для некоторых практических областей применения пригодилась бы динамическая версия маршрутизации с использованием транзитных узлов для работы с сетями, зависящими от времени, или непредсказуемыми изменениями весов дуг, вызванными, к примеру, заторами на дорогах. Последний сценарий может обрабатываться с помощью родственного подхода из работы [8], однако он работает гораздо медленнее, чем маршрутизация с использованием транзитных узлов.

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