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

Маршрутизация при помощи транзитных узлов [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>.

Заметим, что все входящие в него расстояния d(s, u), d(u, v) и d(v, t) могут быть непосредственно получены из предварительно вычисленных структур данных. Наконец, необходим также ''фильтр локальности'' <math>L: V \times V \to \{ true, false \}</math>, определяющий, не находятся ли узлы s и t слишком близко друг к другу для того, чтобы перемещаться между ними через транзитный узел. Значение <math>L</math> должно удовлетворять свойству, заключающемуся в том, что из <math>\lnot{L}(s, t)</math> следует <math>d(s, t) = d_{\mathcal{T}}(s, t)</math>. Заметим, что в общем случае обратное не обязательно должно быть справедливо, поскольку это может стать препятствием для эффективной реализации фильтра локальности. Таким образом, могут встречаться ''ложноположительные'' значения, т. е. "<math>L(s, t) \and d(s, t) = d_{\mathcal{T}} (s, t)</math>".

Рисунок 1. Поиск оптимального времени поездки между двумя точками (''отмеченными флажками'') где-то между Саарбрюккеном и Карлсруэ сводится к получению 2x4 ''узлов доступа'' (''отмеченных ромбами''), выполнению 16 поисков по таблице между всеми парами узлов доступа и проверке, не перекрываются ли два диска, определяющие ''фильтр локальности''. ''Транзитные узлы'', не принадлежащие к множествам узлов доступа выбранных исходного и целевого узлов, изображены в виде маленьких квадратиков. Уровни иерархии дорог обозначены цветом: серым, красным, синим и зеленым для уровней 0-1, 2, 3 и 4, соответственно

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