Двухфазный алгоритм маршрутизации в нестационарных сетях А. А. Солдатенко
Material type: ArticleSubject(s): нестационарные сети | оптимальная маршрутизация | ALT, двухэтапный алгоритм | задача о кратчайшем путиGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика. Приложение № 10. С. 168-171Abstract: Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа — функция от времени отправления из вершины х. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP.Библиогр.: 4 назв.
Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа — функция от времени отправления из вершины х. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP.
There are no comments on this title.