E-catalog        

Библиогр.: 14 назв.

Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Сеть представляется ориентированным графом G = (V, E), в котором для каждой дуги (x, у) £ E определены две функции: wxy (t) — время, необходимое для передвижения по дуге (x, у), и Fxy (t) — время прибытия в вершину у при условии, что старт из вершины x осуществлён в момент времени t. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут или кратчайший путь между этими вершинами. В работе задача TDSP исследована для полиномиально разрешимого случая, когда функции прибытия являются монотонными. Двухфазный алгоритм ALT (A* with Landmarks & Triangle) —один из современных алгоритмов, способных быстро решать задачу TDSP на графах большой размерности. В работе определено и доказано достаточное условие корректности алгоритма ALT для задачи TDSP: сеть должна отвечать неравенству треугольника, заданного для промежутков времени передвижения по узлам сети. Особенность предложенного неравенства треугольника — его определение через «оптимистичные» веса дуг, когда возможно беспрепятственное движение по дугам. Показано, что это неравенство треугольника верно всегда, если веса дуг заданы отношениями длин дуг к скорости передвижения по ним и справедливо неравенство треугольника для расстояний между узлами сети.