4430
правок
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 13:32, 1 октября 2023
, 1 октября 2023нет описания правки
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) представляет собой семейство алгоритмов <math> \big\{ A_{\varepsilon} \big\} </math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \; </math> алгоритм <math>A_{\varepsilon} \; </math> исполняется за время, полиномиальное относительно размера входного графа, и дает <math>(1 + \varepsilon) \; </math>-аппроксимацию. | ||
== Родственные работы == | == Родственные работы == | ||
| Строка 69: | Строка 69: | ||
== Применение == | == Применение == | ||
Техники, разработанные Аророй [1] и Митчеллом [13], нашли множество вариантов применения в разработке схем | Техники, разработанные Аророй [1] и Митчеллом [13], нашли множество вариантов применения в разработке аппроксимационных схем с полиномиальным временем выполнения для задач геометрической оптимизации. | ||
| Строка 95: | Строка 95: | ||
Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем | Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных аппроксимационных схем – то есть алгоритмов с временем выполнения <math>n^{O(log \; n)}</math>. К примеру, Арора и Карокостас [4] создали аппроксимационную схему с квазиполиномиальным временем выполнения для решения евклидовой задачи нахождения минимального времени ожидания; Реми и Стегер [16] предложили аппроксимационную схему с полиномиальным временем выполнения для решения задачи триангуляции с минимальным весом. | ||
Более подробные обзоры можно найти в [2] и [10]. | Более подробные обзоры можно найти в [2] и [10]. | ||
| Строка 104: | Строка 104: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается неясным интересный вопрос: могут ли упомянутые выше квазиполиномиальные схемы | Остается неясным интересный вопрос: могут ли упомянутые выше квазиполиномиальные аппроксимационные схемы (для нахождения минимального времени ожидания и триангуляции с минимальным весом) быть расширены для получения аппроксимационных схем с полиномиальным временем выполнения. Другие открытые вопросы можно найти в [2]. | ||
== См. также == | == См. также == | ||
