E-catalog        

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

Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа — функция от времени отправления из вершины х. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP.