4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:01, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
'''Теорема 2 (Тревизан [17]). Если <math>d \ge log \; n \; </math>, то существует константа <math>\epsilon > 0 \; </math>, такая, что евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> является NP-полной для аппроксимации с коэффициентом <math>1 + \epsilon \; </math>. | '''Теорема 2 (Тревизан [17]). Если <math>d \ge log \; n \; </math>, то существует константа <math>\epsilon > 0 \; </math>, такая, что евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> является NP-полной для аппроксимации с коэффициентом <math>1 + \epsilon \; </math>. | ||
В частности, из этого результата следует, что если <math>d \ge log \; n \; </math>, то евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> не имеет PTAS, за исключением случая, когда | В частности, из этого результата следует, что если <math>d \ge log \; n \; </math>, то евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> не имеет PTAS, за исключением случая, когда P = NP. | ||
Тот же результат имеет место для любой <math>\ell _p</math>-метрики. Кроме того, из теоремы 2 следует, что евклидова задача коммивояжера на | Тот же результат имеет место для любой <math>\ell _p</math>-метрики. Кроме того, из теоремы 2 следует, что евклидова задача коммивояжера на <math>\mathbb{R} ^{log \; n}</math> является APX PB-полной при ограничении по E и APX-полной при ограничении по AP. | ||
Считалось, что теорема 2 может выполняться для небольших значений d, в частности, для d = 2, однако это было независимым образом опровергнуто Аророй [1] и Митчеллом [13]. | |||
'''Теорема 3 (Arora [1], Mitchell [13]). Евклидова задача коммивояжера на плоскости имеет PTAS.''' | '''Теорема 3 (Arora [1], Mitchell [13]). Евклидова задача коммивояжера на плоскости имеет PTAS.''' | ||
Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую | Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon)</math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | ||
Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время исполнения в форме 0{nll€), что позволяло получить (1 + e)-аппроксимацию; впоследствии оно было улучшено. В частности, рандомизированный алгоритм Ароры [1] исполняется за время O(n(log и)1/е); он может быть дерандомизирован, в силу чего время увеличится на O(n). Результат теоремы 3 также может быть распространен на более высокие измерения. Арора демонстрирует следующий результат. | Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время исполнения в форме 0{nll€), что позволяло получить (1 + e)-аппроксимацию; впоследствии оно было улучшено. В частности, рандомизированный алгоритм Ароры [1] исполняется за время O(n(log и)1/е); он может быть дерандомизирован, в силу чего время увеличится на O(n). Результат теоремы 3 также может быть распространен на более высокие измерения. Арора демонстрирует следующий результат. | ||