4446
правок
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:16, 22 января 2014
, 22 января 2014→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
== Нотация == | == Нотация == | ||
Евклидова задача коммивояжера заключается в следующем: для заданного множества S из n точек в евклидовом пространстве | Евклидова задача коммивояжера заключается в следующем: для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}\ ^d</math> найти путь минимальной длины, проходящий через каждую точку ровно один раз. | ||
Стоимость | Стоимость <math>\delta\ (x, y)</math> дуги, соединяющей пару точек x;y2Rd, равна евклидовому расстоянию между точками x и y. Иначе говоря, S(x, y) = P di=1(xi ~~ i)2, где x = (x 1 ; :. , xd) и y = (y 1,.: ; y d). В более общем виде расстояние можно определить с использованием других норм – таких как lp-нормы для любого p > l,8(x,y) = Pid=1(xi ~ yi)p . | ||
Для заданного множества S точек в евклидовом пространстве Rd, для целого d > 2, евклидов граф (сеть) представляет собой граф G = (S; E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется полным евклидовым графом на S. Стоимость графа равна сумме стоимостей дуг графа: | Для заданного множества S точек в евклидовом пространстве Rd, для целого d > 2, евклидов граф (сеть) представляет собой граф G = (S; E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется полным евклидовым графом на S. Стоимость графа равна сумме стоимостей дуг графа: | ||
Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию. | Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию. | ||
== Родственные работы == | == Родственные работы == | ||
