Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов

Исследуется задача обхода мегаполисов с фиксированным числом “входов” и специальным образом заданными отношениями предшествования, являющаяся естественным обобщением классической задачи коммивояжера (TSP). Для поиска оптимального решения задачи приводится схема динамического программирования, эквивалентная методу поиска кратчайшего пути в подходящем бесконтурном ориентированном взвешенном графе. Обосновываются условия, при которых трудоемкость алгоритма полиномиально, в частности, линейно зависит от числа мегаполисов.