TY  - SER
AU  - Солдатенко,Александр Александрович
TI  - Двухфазный алгоритм маршрутизации в нестационарных сетях
KW  - нестационарные сети
KW  - оптимальная маршрутизация
KW  - ALT, двухэтапный алгоритм
KW  - задача о кратчайшем пути
KW  - статьи в журналах
N1  - Библиогр.: 4 назв
N2  - Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа — функция от времени отправления из вершины х. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP
UR  - http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000582296
ER  -