Приближенный алгоритм поиска оптимального маршрута в сети с ограничением А. А. Солдатенко
Material type:
ArticleContent type: Текст Media type: электронный Subject(s): ресурсоограниченный кратчайший путь | алгоритмы на графах | оптимальная маршрутизация | компьютерные сети | мультисервисные сетиGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика. Приложение № 12. С. 186-191Abstract: Предлагается приближённый алгоритм RevTree решения NP-трудной задачи RCSP (Resource Constrained Shortest Path). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V, E), когда для каждой дуги e G E кроме основной весовой функции w(e) дополнительно задаются функции ri(e), i = 1,. . . ,k, численно отражающие потребности в ресурсах, которые необходимы для = передвижения по этой дуге. Задача RCSP возникает при проектировании и эксплуатации компьютерных и мультисервисных сетей. Показано, что алгоритм RevTree всегда находит допустимое решение задачи RCSP, если оно существует, за полиномиальное время, отклоняясь от оптимального решения на величину, зависящую от значений w(e) и ri(e), e G E.
Библиогр.: 10 назв.
Предлагается приближённый алгоритм RevTree решения NP-трудной задачи RCSP (Resource Constrained Shortest Path). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V, E), когда для каждой дуги e G E кроме основной весовой функции w(e) дополнительно задаются функции ri(e), i = 1,. . . ,k, численно отражающие потребности в ресурсах, которые необходимы для = передвижения по этой дуге. Задача RCSP возникает при проектировании и эксплуатации компьютерных и мультисервисных сетей. Показано, что алгоритм RevTree всегда находит допустимое решение задачи RCSP, если оно существует, за полиномиальное время, отклоняясь от оптимального решения на величину, зависящую от значений w(e) и ri(e), e G E.
There are no comments on this title.