Эта публикация цитируется в
5 статьях
Вычислительные методы в дискретной математике
Оптимальная маршрутизация по ориентирам в нестационарных сетях
В. В. Быкова,
А. А. Солдатенко Сибирский федеральный университет, г. Красноярск, Россия
Аннотация:
Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Сеть представляется ориентированным графом
$G=(V,E)$, в котором для каждой дуги
$(x,y)\in E$ определены две функции:
$w_{xy}(t)$ – время, необходимое для передвижения по дуге
$(x,y)$, и
$F_{xy}(t)$ – время прибытия в вершину
$y$ при условии, что старт из вершины
$x$ осуществлён в момент времени
$t$. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут или кратчайший путь между этими вершинами. В работе задача TDSP исследована для полиномиально разрешимого случая, когда функции прибытия являются монотонными. Двухфазный алгоритм ALT (A
$^*$ with Landmarks & Triangle) – один из современных алгоритмов, способных быстро решать задачу TDSP на графах большой размерности. В работе определено и доказано достаточное условие корректности алгоритма ALT для задачи TDSP: сеть должна отвечать неравенству треугольника, заданного для промежутков времени передвижения по узлам сети. Особенность предложенного неравенства треугольника – его определение через “оптимистичные” веса дуг, когда возможно беспрепятственное движение по дугам. Показано, что это неравенство треугольника верно всегда, если веса дуг заданы отношениями длин дуг к скорости передвижения по ним и справедливо неравенство треугольника для расстояний между узлами сети.
Ключевые слова:
нестационарные сети, оптимальная маршрутизация, корректность алгоритма ALT.
УДК:
519.7
DOI:
10.17223/20710410/37/10