Библиографическое описание:Приближённый алгоритм поиска оптимального маршрута в сети с ограничением : научное издание / А. А. Солдатенко. - Текст : непосредственный // Прикладная дискретная математика. Приложение. - 2019. - № 12. - С. 186-191. - ISSN 2226-308X. - ISSN 2411-2313. Перевод заглавия: Approximate algorithm for searching shortest path in multiservice network with constrained resource
Аннотация:Предлагается приближённый алгоритм RevTree решения NP-трудной задачи RCSP (Resource Constrained Shortest Path). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V,E), когда для каждой дуги e £ E кроме основной весовой функции w(e) дополнительно задаются функции Ti(e), i = 1,...,k, численно отражающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Задача RCSP возникает при проектировании и эксплуатации компьютерных и мультисервисных сетей. Показано, что алгоритм RevTree всегда находит допустимое решение задачи RCSP, если оно существует, за полиномиальное время, отклоняясь от оптимального решения на величину, зависящую от значений w(e) и ri(e), e £ E.
In the paper, we consider the Resource Constrained Shortest Path problem (RCSP). This problem is NP-hard extension of a well-known shortest path problem in the directed graph G = (V, E). In the RCSP problem each arc e from E has a cost w(e) and additional weight functions ri(e), i = 1,..., k, which specifying its requirements from a finite set of resource. The RCSP problem has various practical applications, including design and operation of multi-service network. Nowadays, multi-service networks grow at a rapid pace. Therefore, it is relevant to search for a new approximation algorithms that can solve the RCSP problem quickly. This paper reviews existing approximation algorithms for the RCSP problem. A polynomial time
Издательство:Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский Томский государственный университет, Томск
