4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:12, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | ||
Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время исполнения в форме <math>O(n^{1/ \epsilon})</math>, что позволяло получить <math>(1 + \epsilon ) \; </math>-аппроксимацию; впоследствии оно было улучшено. В частности, рандомизированный алгоритм Ароры [1] исполняется за время <math>O(n(log \; n)^{1/ \epsilon})</math>; он может быть дерандомизирован, в силу чего время увеличится на O(n). Результат теоремы 3 также может быть распространен на более высокие измерения. Арора демонстрирует следующий результат. | Исходные алгоритмы, представленные в первой версии [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)-аппроксимацию для оптимального пути коммивояжера за время O(n (log n)^ | Для каждого фиксированного значения 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 время исполнения составляет O(n (log n)O(1)). Алгоритм может быть дерандомизирован, что увеличит время исполнения на коэффициент O(nd). | ||
Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую. | Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую. | ||