А. Н. Жуланов

Решение задачи коммивояжера методом динамического моделирования

Предложена динамическая модель для решения симметричной задачи коммивояжера. В основе модели лежит принцип первоначальной генерации сигналов всеми вершинами графа, синхронного и симметричного распространения сигналов и их одновременного возвращения во все исходные вершины. Посещения вершин регистрируются. В каждом сигнале может фиксироваться координата одной пройденной вершины – время и порядок ее посещения относительно исходной вершины. Описаны свойства симметрии простого пути, включая обратную симметрию посещений каждой вершины противоположно направленными сигналами. Асимметричные координаты указывают на повторные посещения вершин. Доказано, что в любом непростом цикле координата посещения по крайней мере одной вершины асимметрична. Такие координаты можно итерационно удалять. Для исключения из графа с n вершинами всех непростых циклов заданной протяженности требуется менее n итераций моделирования. Вычислительная сложность предложенного алгоритма составляет O(n⁸) и с ростом n стремится к Ω(n⁷).

КЛЮЧЕВЫЕ СЛОВА: задача коммивояжера, проблема равенства классов P и NP, динамическая модель.