4446
правок
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 13:43, 23 января 2014
, 23 января 2014→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Стоимость <math>\delta (x, y)</math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R} ^d</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta (x, y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} </math>, где <math>x = (x_1, ..., x_d) \; </math> и <math>y = (y_1, ..., y_d) \; </math>. В более общем виде расстояние можно определить с использованием других норм – таких как <math>\ell _p</math>-нормы для любого p > 1, <math>\delta (x, y) = (\sum_{i=1}^d (x_i - y_i)^p)^{1/p} </math>. | Стоимость <math>\delta (x, y)</math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R} ^d</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta (x, y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} </math>, где <math>x = (x_1, ..., x_d) \; </math> и <math>y = (y_1, ..., y_d) \; </math>. В более общем виде расстояние можно определить с использованием других норм – таких как <math>\ell _p</math>-нормы для любого p > 1, <math>\delta (x, y) = (\sum_{i=1}^d (x_i - y_i)^p)^{1/p} </math>. | ||
Для заданного множества S точек в евклидовом пространстве <math>\mathbb{R} | Для заданного множества S точек в евклидовом пространстве <math>\mathbb{R} ^d</math>, для целого <math>d \ge 2 \; </math>, [[евклидов граф]] ([[евклидова сеть|сеть]]) представляет собой граф G = (S, E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется [[полным евклидовым графом|полный евклидов граф]] на S. Стоимость графа равна сумме стоимостей дуг графа: <math>cost(G) = \sum{(x, y) \in E} \delta (x, y)</math> | ||
Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию. | <math>Схема аппроксимации с полиномиальным временем исполнения|схема аппроксимации с полиномиальным временем исполнения</math> (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию. | ||
== Родственные работы == | == Родственные работы == | ||
