4430
правок
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:25, 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> | [[Аппроксимационная схема с полиномиальным временем выполнения]] (PTAS) представляет собой семейство алгоритмов <math> \big\{ A_{\varepsilon} \big\} </math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \; </math> алгоритм <math>A_{\varepsilon} \; </math> выполняется за время, полиномиальное относительно размера входного графа, и дает <math>(1 + \varepsilon) \; </math>-аппроксимацию. | ||
== Родственные работы == | == Родственные работы == | ||
| Строка 28: | Строка 28: | ||
Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз). | Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз). | ||
Аппроксимируемость евклидовой задачи коммивояжера в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют [[неравенство треугольника|неравенству треугольника]] (этот случай обозначается как [[метрическая задача коммивояжера]]), существует алгоритм 3/2-аппроксимации с полиномиальным временем | Аппроксимируемость евклидовой задачи коммивояжера в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют [[неравенство треугольника|неравенству треугольника]] (этот случай обозначается как [[метрическая задача коммивояжера]]), существует алгоритм 3/2-аппроксимации с полиномиальным временем выполнения, разработанный Кристофидесом [8]; также известно, что PTAS для этого случая не существует (если только не верно P = NP). Тревизан [17] усилил этот результат, включив евклидовы графы более высоких размерностей (тот же результат имеет место для любой <math>\ell _p</math>-метрики). | ||
| Строка 45: | Строка 45: | ||
Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | ||
Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время | Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время выполнения в форме <math>O(n^{1/ \epsilon})</math>, что позволяло получить <math>(1 + \epsilon ) \; </math>-аппроксимацию; впоследствии оно было улучшено. В частности, рандомизированный алгоритм Ароры [1] выполняется за время <math>O(n(log \; n)^{1/ \epsilon})</math>; он может быть дерандомизирован, в силу чего время увеличится на <math>O(n) \; </math>. Теорема 3 также может быть распространена на более высокие размерности. Арора демонстрирует следующий результат. | ||
'''Теорема 4 (Арора [1]). Для любого константного значения d евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | '''Теорема 4 (Арора [1]). Для любого константного значения d евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
'''Для любого фиксированного значения c > 1 и любых n вершин из <math>\mathbb{R} ^d</math> существует рандомизированный алгоритм, который находит (1 + 1/c)-аппроксимацию для оптимальной траектории движения коммивояжера за время <math>O(n (log \; n)^{(O(\sqrt{d} c))^{d-1} })</math>. В частности, для любых константных значений d и c время | '''Для любого фиксированного значения c > 1 и любых n вершин из <math>\mathbb{R} ^d</math> существует рандомизированный алгоритм, который находит (1 + 1/c)-аппроксимацию для оптимальной траектории движения коммивояжера за время <math>O(n (log \; n)^{(O(\sqrt{d} c))^{d-1} })</math>. В частности, для любых константных значений d и c время выполнения составляет <math>O(n (log \; n)^{O(1)})</math>. Алгоритм может быть дерандомизирован, что увеличит время выполнения на коэффициент <math>O(n^d) \; </math>. | ||
''' | ''' | ||
