Просмотр кода страницы Евклидова задача коммивояжера

== Ключевые слова и синонимы ==
Геометрическая задача коммивояжера


== Постановка задачи ==

Рассматриваются NP-полные задачи геометрической оптимизации – такие как евклидова [[задача коммивояжера]] и евклидова задача нахождения [[дерево Штейнера|дерева Штейнера]]. Эти задачи являются геометрическими вариантами стандартных задач [[оптимизация графа|оптимизации графа]]; ограничение входных экземпляров геометрическим или евклидовым случаем встречается во множестве приложений ([1, 2]). Далее будет в основном рассматриваться евклидова задача коммивояжера.

== Нотация ==
Евклидова задача коммивояжера заключается в следующем: для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> найти путь минимальной длины, проходящий через каждую точку ровно один раз.

Стоимость <math>\delta (x, y) \; </math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R} ^d</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta (x, y) = \sqrt{\sum_{i=1}^d (x_i - y_i)^2} </math>, где <math>x = (x_1, ..., x_d) \; </math> и <math>y = (y_1, ..., y_d) \; </math>. В более общем виде расстояние можно определить с использованием других норм – таких как <math>\ell _p</math>-нормы для любого p > 1, <math>\delta (x, y) = (\sum_{i=1}^d (x_i - y_i)^p)^{1/p} </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>-аппроксимацию.

== Родственные работы ==

Классическая работа Лоулера и коллег [12] содержит полную информацию о подходах к решению евклидовой задачи коммивояжера. Обзор Берна и Эппстайна [7] представляет состояние дел в исследованиях геометрических евклидовых задач коммивояжера вплоть до 1995; Арора в своем обзоре [2] рассматривает работы, выполненные после 1995 года.

== Основные результаты ==
Известно, что в графах общего вида задача коммивояжера является NP-полной; то же верно для евклидовой задачи коммивояжера ([11], [14]).


'''Теорема 1. Евклидова задача коммивояжера является NP-полной.'''

Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз).

Аппроксимируемость евклидовой задачи коммивояжера в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют неравенству треугольника (этот случай обозначается как [[метрическая задача коммивояжера]]), существует алгоритм 3/2-аппроксимации с полиномиальным временем исполнения, разработанный Кристофидесом [8]; также известно, что PTAS для этого случая не существует (если только не верно P = NP). Тревизан [17] усилил этот результат, включив евклидовы графы более высоких измерений (тот же результат имеет место для любой <math>\ell _p</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, за исключением случая, когда P = NP.


Тот же результат имеет место для любой <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.'''

Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <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>; он может быть дерандомизирован, в силу чего время увеличится на <math>O(n) \; </math>. Результат теоремы 3 также может быть распространен на более высокие измерения. Арора демонстрирует следующий результат.


'''Теорема 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 время исполнения составляет <math>O(n (log \; n)^{O(1)})</math>. Алгоритм может быть дерандомизирован, что увеличит время исполнения на коэффициент <math>O(n^d) \; </math>.

Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую.


'''Теорема 5 (Рао и Смит [15]). Существует детерминированный алгоритм, вычисляющий (1 + 1/c)-аппроксимацию оптимальной траектории движения коммивояжера за время <math>O(2^{(cd)^{O(d)}} n + (cd)^{O(d)} n log \; n)</math>.'''

'''Также существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время <math>(c \sqrt{d})^{O(d(c \sqrt{d})^{d-1})} n + O(d \; n \; log \; n)</math>.'''


Для отдельного, наиболее интересного случая, при d = 2, Рао и Смит продемонстрировали следующий результат.


'''Теорема 6 (Рао и Смит [15]). Существует рандомизированный алгоритм, который вычисляет (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за время <math>O(n 2^{c^{O(1)}} + c^{O(1)} n \; log \; n)</math>.'''

'''Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время <math>O(n 2^{c^{O(1)}} + n \; log \; n)</math>.'''

== Применение ==
Техники, разработанные Аророй [1] и Митчеллом [13], нашли множество вариантов применения в разработке схем аппроксимации с полиномиальным временем исполнения для задач геометрической оптимизации.

''Евклидова задача нахождения минимального дерева Штейнера''

Для заданного множества S из n точек в евклидовом пространстве Rd найти путь минимальной стоимости, соединающий все точки S (стоимость сети равна сумме длин дуг, ее определяющих).

'''Теорема 7 ([1, 15]). Для каждого константного значения d евклидова задача нахождения минимального дерева Штейнера на Rd имеет PTAS.'''

''Евклидова задача нахождения k медиан''

Для заданного множества S из n точек в евклидовом пространстве Rd и целого числа k найти k медиан между точками S, таких, что сумма расстояний от каждой точки S до ближайшей к ней медианы минимальна.

'''Теорема 8 ([5]). Для каждого константного значения d евклидова задача нахождения k медиан на Rd имеет PTAS.'''

''Евклидова задача коммивояжера с k точками''

Для заданного множества S из n точек в евклидовом пространстве Rd и целого числа k найти путь минимальной длины, проходящий не менее k точек множества S.

''Евклидова задача нахождения минимального дерева Штейнера с k точками''

Для заданного множества S из n точек в евклидовом пространстве Rd и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S.

'''Теорема 9 ([1]). Для каждого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на Rd имеют PTAS.'''

''Евклидова задача нахождения k-связного подграфа минимальной стоимости''

Для заданного множества S из n точек в евклидовом пространстве Rd и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным.

'''Теорема 10 ([9]). Для каждого константного значения d и константного k, евклидова задача нахождения k-связного подграфа минимальной стоимости на Rd имеет PTAS.'''

Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем аппроксимации – то есть алгоритмов с временем исполнения n°^°&n\. К примеру, Арора и Карокостас [4] создали схему аппроксимации с квазиполиномиальным временем исполнения для решения евклидовой задачи нахождения минимального времени ожидания; Реми и Стегер [16] предложили схему аппроксимации с полиномиальным временем исполнения для решения задачи триангуляции с минимальным весом.
Более подробные обзоры можно найти в [2] и [10].


== Расширение на планарные графы ==

Подход динамического программирования, используемый Арором и Митчеллом, также имеет отношение к недавним достижениям в области нескольких проблем оптимизации для планарных графов. В частности, Аврор и коллеги [3] разработали PTAS для задачи коммивояжера на взвешенных планарных графах; существует также PTAS для задачи нахождения двусвязного остовного подграфа планарного графа, имеющего минимальную стоимость [6].


== Открытые вопросы ==

Остается неясным интересный вопрос: могут ли упомятуные выше квазиполиномиальные схемы аппроксимации (для нахождения минимального времени ожидания и триангуляции с минимальным весом) быть расширены для получения схем аппроксимации с полиномиальным временем исполнения. Другие открытые вопросы можно найти в [2].


== См. также ==
* ''[[Метрическая задача коммивояжера]]
* ''[[Минимальные k-связные геометрические сети]]
* ''[[Триангуляция с минимальным весом]]


== Литература ==

1.	Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782 (1998)

2.	Arora, S.: Approximation schemes for NP-hard geometric optimization problems: A survey. Math. Program. Ser. B 97,43-69 (2003)

3.	Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A..: A polynomial time approximation scheme for weighted planar graph TSP. In: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 33-41

4.	Arora, S., Karakostas, G.: Approximation schemes for minimum latency problems. In: Proc. 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 688-693

5.	Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proc. 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 106-113

6.	Berger, A., Czumaj, A., Grigni, M., Zhao, H.: Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. In: Proc. 13th Annual European Symposium on Algorithms, 2005, pp. 472-483

7.	Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard problems. PWS Publishing, Boston (1996)

8.	 Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Technical report, Graduate School of Industrial Administration. Carnegie-Mellon University, Pittsburgh (1976)

9.	Czumaj, A., Lingas, A.: On approximability of the minimum-cost k-connected spanning subgraph problem. In: Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 281-290

10.	Czumaj, A., Lingas, A.: Approximation schemes for minimum-cost k-connectivity problems in geometric graphs. In: Gonzalez, T.F. (eds.) Handbook of Approximation Algorithms and Metaheuristics. CRC Press, Boca Raton (2007)

11.	Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. 8th Annual ACM Symposium on Theory of Computing, 1976, pp. 10-22

12.	Lawler, E.L., Lenstra,J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.:The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)

13.	Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal  subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298-1309 (1999)

14.	Papadimitriou, C.H.: Euclidean TSP is NP-complete. Theor. Comput. Sci. 4, 237-244 (1977)

15.	Rao, S.B., Smith, W.D.: Approximating geometrical graphs via "spanners" and "banyans". In: Proc. 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 540-550

16.	Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. In: Proc. 38th Annual ACM Symposium on Theory of Computing, 2006

17.	Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and SteinerTree. SIAM J. Comput. 30(2), 475-485 (2000)