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

Решение

Обозначим за расстояние между городами и . Оченвидно, что если мы ко всем прибавим константу , то получим задачу, эквивалентную исходной. Пусть - максимум расстояний между городами, то есть

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.