Комментарии — Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна

Решение

Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.

В TSP обозначим за расстояние между городами и . Если мы ко всем прибавим константу , то получим задачу, эквивалентную исходной (длина любого цикла возрастет ровно на , где - число городов). Под эквивалентостью имеется в виду совпадение маршрутов, а его длину в старой задаче можно получить, вычитая из результата новой задачи величину . Пусть - максимум расстояний между городами, то есть . В качестве константы возьмем . Тогда для новых расстояний выполнено . При таких расстояниях справедливо неравенство треугольника. Что и требовалось.