Использование методов теории оптимального управления для решения некоторых задач дискретной оптимизации. III. Динамическая задача коммивояжера

Для одного из базовых вариантов динамической минисуммной задачи коммивояжера предлагается декомпозиционная схема решения, приводящая в общем случае к новому приближенному алгоритму решения. При задании определенных условий на матрицу расстояний алгоритм становится точным. Решение задачи основывается на использовании известных в теории оптимального управления достаточных условий оптимальности.