В статье приводятся результаты исследований по обоснованию гарантированных и асимптотически точных оценок решения ряда трудных задач маршрутизации, для которых в общем случае не удается построить точные алгоритмы полиномиальной сложности (в предположении, что классы P и NP не совпадают). Основное внимание уделено задачам отысканиея в полном неориентированном взвешенном графе нескольких реберно непересекающихся маршрутов коммивояжера экстремального суммарного веса.
Файл с полным текстом: | Алгоритмы для задач маршрутизации.pdf |