4551
правка
Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в дорожных сетях с транзитными узлами (посмотреть исходный код)
Версия от 00:18, 10 июня 2019
, 10 июня 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Заметим, что все входящие в него расстояния d(s, u), d(u, v) и d(v, t) могут быть непосредственно получены из предварительно вычисленных структур данных. Наконец, необходим также фильтр локальности | Заметим, что все входящие в него расстояния 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>". | ||
Следующий алгоритм может использоваться для вычисления d(s,t): | Следующий алгоритм может использоваться для вычисления d(s, t): | ||
Если <math>\lnot{L}(s, t)</math>, то вычислить и вернуть <math>d_{\mathcal{T}} (s, t)</math>; | |||
в противном случае использовать любой другой алгоритм маршрутизации. | |||