4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 22:52, 29 августа 2016
, 29 августа 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Если существует алгоритм с полиномиальным временем выполнения для решения задачи TSP, коэффициент аппроксимации которого зависит от n, то P = NP. Таким образом, следует рассматривать ограниченные экземпляры. Наиболее естественным ограничением является [[неравенство треугольника]], которое выглядит следующим образом: | Если существует алгоритм с полиномиальным временем выполнения для решения задачи TSP, коэффициент аппроксимации которого зависит от n, то P = NP [6]. Таким образом, следует рассматривать ограниченные экземпляры. Наиболее естественным ограничением является [[неравенство треугольника]], которое выглядит следующим образом: | ||
<math>w(u, v) \le w(u, x) + w(x, v) \;</math> для всех <math>u, v, x \in V \;</math>. | <math>w(u, v) \le w(u, x) + w(x, v) \;</math> для всех <math>u, v, x \in V \;</math>. | ||