Сибирский федеральный университет

Рассматривается NP-трудная задача поиска ресурсоограниченного кратчайшего пути, известная под названием Resource Constrained Shortest Path (RCSP). Задача RCSP является расширением задачи о кратчайшем пути в ориентированном графе G = (V;E), когда для каждой дуги e 2 E кроме основной весовой функции w(e) дополнительно задаются функции ri(e); i = 1; : : : ; k, числен- но отражающие потребности в ресурсах, которые необходимы для передвижения по этой дуге. Предлагается полиномиальный ϵ-приближенный алгоритм RevTree, использующий специальную маркировку вершин. Основное преимущество алгоритма RevTree по сравнению с существующими алгоритмами: он быстро находит допустимое решение задачи за O(jV j2) время, отклоняясь от оптимального решения на величину, не превышающую ϵ. В работе приведены доказательства оценок сложности и точности алгоритма RevTree