4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:48, 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} ^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> | Для заданного множества 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) представляет собой семейство алгоритмов <math> \big\{ A_{\varepsilon} \big\} </math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \; </math> алгоритм <math>A_{\varepsilon} \; </math> исполняется за время, полиномиальное относительно размера входного графа, и дает <math>(1 + \varepsilon) \; </math>-аппроксимацию. | [[схема аппроксимации с полиномиальным временем исполнения|Схема аппроксимации с полиномиальным временем исполнения]] (PTAS) представляет собой семейство алгоритмов <math> \big\{ A_{\varepsilon} \big\} </math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \; </math> алгоритм <math>A_{\varepsilon} \; </math> исполняется за время, полиномиальное относительно размера входного графа, и дает <math>(1 + \varepsilon) \; </math>-аппроксимацию. | ||