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

Маршрутизация при помощи транзитных узлов [2, 3] основывается на простом наблюдении, интуитивно используемом людьми: Если вы начинаете движение из исходного узла s и движетесь куда-то «далеко», вы покинете свое текущее местоположение через одну из нескольких «важных» точек пересечений дорог, называемых (прямыми) ''узлами доступа'' <math>\overrightarrow{A}(s)</math>. Аналогичное рассуждение применяется и к целевому узлу, в который можно попасть только из одного из нескольких обратных узлов доступа <math>\overleftarrow{A}(t)</math>. Более того, объединение всех прямых и обратных узлов доступа всех узлов, называемое ''множеством транзитных вершин'' <math>\mathcal{T}</math>, весьма невелико. Из этого следуют два наблюдения, заключающиеся в том, что для каждого узла можно хранить расстояния до и из его прямых и обратных узлов доступа, а для каждой пары транзитных узлов (u, v) – расстояние между u и v. Для заданных исходного и целевого узлов s и t длина кратчайшего путь, проходящего как минимум через один транзитный узел, задается соотношением <math>d_{\mathcal{T}} (s, t) = min \{ d(s, u) + d(u, v) + d(v, t) | u \in \overrightarrow{A}(s), v \in \overleftarrow{A}(t) \}</math>.

Пример приведен на рис. 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>, т. е. расстояния, которые не могут быть получены при помощи первичного уровня. Аналогичным образом можно добавить и более глубокие уровни.