Обсуждение:Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна — различия между версиями
Материал из DISCOPAL
(Created page with "== Решение ==") |
(→Решение) |
||
| Строка 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> | ||
Версия 20:29, 21 ноября 2011
Решение
Обозначим за расстояние между городами и . Оченвидно, что если мы ко всем прибавим константу , то получим задачу, эквивалентную исходной. Пусть - максимум расстояний между городами, то есть