4551
правка
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 13:44, 23 января 2014
, 23 января 2014→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Для заданного множества 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) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию. | |||
== Родственные работы == | == Родственные работы == | ||
