4551
правка
Евклидова задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 13:53, 23 января 2014
, 23 января 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
'''Теорема 1. Евклидова задача коммивояжера является NP-полной.''' | '''Теорема 1. Евклидова задача коммивояжера является NP-полной.''' | ||
Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства | Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз). | ||
Аппроксимируемость TSP в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача TSP неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют неравенству треугольника (этот случай обозначается как «метрическая задача коммивояжера»), существует алгоритм 3/2-аппроксимации с полиномиальным временем исполнения, разработанный Кристофидесом [8]; также известно, что PTAS для этого случая не существует (если только не верно P = NP). Тревизан [17] усилил этот результат, включив евклидовы графы более высоких измерений (тот же результат имеет место для любой lp-метрики). | Аппроксимируемость TSP в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача TSP неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют неравенству треугольника (этот случай обозначается как «метрическая задача коммивояжера»), существует алгоритм 3/2-аппроксимации с полиномиальным временем исполнения, разработанный Кристофидесом [8]; также известно, что PTAS для этого случая не существует (если только не верно P = NP). Тревизан [17] усилил этот результат, включив евклидовы графы более высоких измерений (тот же результат имеет место для любой lp-метрики). | ||
| Строка 32: | Строка 32: | ||
'''Теорема 2 (Тревизан [17]). Если d > log n, то существует константа e > 0, такая, что евклидова задача коммивояжера на R является NP-полной с аппроксимацией с коэффициентом 1 + e. | '''Теорема 2 (Тревизан [17]). Если d > log n, то существует константа e > 0, такая, что евклидова задача коммивояжера на R является NP-полной с аппроксимацией с коэффициентом 1 + e. | ||
В частности, из этого результата следует, что если d > log n, то евклидова задача коммивояжера на | В частности, из этого результата следует, что если d > log n, то евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> не имеет PTAS, за исключением случая, когда''' | ||
| Строка 45: | Строка 45: | ||
Исходные алгоритмы, представленные в первой версии [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 также может быть распространен на более высокие измерения. Арора демонстрирует следующий результат. | ||
'''Теорема 4 (Арора [1]). Для каждого константного значения d евклидова задача коммивояжера на | '''Теорема 4 (Арора [1]). Для каждого константного значения d евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
Для каждого фиксированного значения c > 1 и любых n вершин из | Для каждого фиксированного значения c > 1 и любых n вершин из <math>\mathbb{R} ^d</math> существует рандомизированный алгоритм, который находит (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за время O(n (log n)^°^dc^ ). В частности, для любых константных значений d и c время исполнения составляет O(n (log n)O(1)). Алгоритм может быть дерандомизирован, что увеличит время исполнения на коэффициент O(nd). | ||
Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую. | Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую. | ||