Дата публикации: 2017

Дата публикации в реестре: 2020-03-03T19:06:33Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2017. № 10. С. 168-171