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

Маршрутизация в сетях с транзитными узлами [2, 3] основывается на простом наблюдении, интуитивно используемом людьми: Если вы начинаете движение из исходного узла s и движетесь куда-то «далеко», вы покинете свое текущее местоположение через одну из нескольких «важных» точек пересечений дорог, зазываемых (прямыми) узлами доступа A (s). Аналогичное рассуждение применяется и к целевому узлу, в который можно попасть только из одного из нескольких обратных узлов доступа A it). Более того, объединение всех прямых и обратных узлов доступа всех узлов, называемое множеством транзитных вершин T, весьма невелико. Из этого следуют два наблюдения, заключающиеся в том, что для каждого узла можно хранить расстояния до и из его прямых и обратных узлов доступа, а для каждой пары транзитных узлов (u, v) – расстояние между u и v. Для заданных исходного и целевого узлов s и t длина кратчайшего путь, проходящего как минимум через один транзитный узел, задается соотношением t) = minfd(s; u) + d(u; v) + d(v; t) j и € ~A(s),v 2 'Ait)}.

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