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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Решение)
(Решение)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
== Решение ==
 
== Решение ==
Обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Оченвидно, что если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max</m>
+
Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.
 +
 
 +
В TSP обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной (длина любого гамильтонова цикла возрастет ровно на <m>Cn</m>, где <m>n</m> - число городов). Под эквивалентостью имеется в виду совпадение маршрутов, а его длину в старой задаче  можно получить, вычитая из результата новой задачи величину <m>Cn</m>. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max_{i,j}{d_{ij}}</m>. В качестве константы <m>C</m> возьмем <m>D + 1</m>. Тогда для новых расстояний выполнено <m>D + 1 < d_{ij}^* \le 2D + 1</m>. При таких расстояниях справедливо неравенство треугольника. Что и требовалось.

Текущая версия на 05:48, 22 ноября 2011

Решение

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

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