Евклидова задача коммивояжера

Ключевые слова и синонимы

Геометрическая задача коммивояжера

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

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

Нотация

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

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

Для заданного множества S точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R} ^d }[/math], для целого числа [math]\displaystyle{ d \ge 2 \; }[/math], евклидов граф (сеть) представляет собой граф G = (S, E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется полным евклидовым графом на S. Стоимость графа равна сумме стоимостей дуг графа: [math]\displaystyle{ cost(G) = \sum_{(x, y) \in E} \delta (x, y) }[/math]

Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов [math]\displaystyle{ \big\{ A_{\varepsilon} \big\} }[/math], такое, что для каждого фиксированного [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] алгоритм [math]\displaystyle{ A_{\varepsilon} \; }[/math] исполняется за время, полиномиальное относительно размера входного графа, и дает [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию.

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

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

Основные результаты

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

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

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

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

Теорема 2 (Тревизан [17]). Если [math]\displaystyle{ d \ge log \; n \; }[/math], то существует константа [math]\displaystyle{ \epsilon \gt 0 \; }[/math], такая, что евклидова задача коммивояжера на [math]\displaystyle{ \mathbb{R} ^d }[/math] является NP-полной для аппроксимации с коэффициентом [math]\displaystyle{ 1 + \epsilon \; }[/math].

В частности, из этого результата следует, что если [math]\displaystyle{ d \ge log \; n \; }[/math], то евклидова задача коммивояжера на [math]\displaystyle{ \mathbb{R} ^d }[/math] не имеет PTAS, за исключением случая, когда P = NP.

Тот же результат верен для любой [math]\displaystyle{ \ell _p }[/math]-метрики. Кроме того, из теоремы 2 следует, что евклидова задача коммивояжера на [math]\displaystyle{ \mathbb{R} ^{log \; n} }[/math] является APX PB-полной при ограничении по E и APX-полной при ограничении по AP.

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

Теорема 3 (Arora [1], Mitchell [13]). Евклидова задача коммивояжера на плоскости имеет PTAS.

Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую структурную теорему. Она демонстрирует, что существует [math]\displaystyle{ (1 + \epsilon) \; }[/math]-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме.

Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время исполнения в форме [math]\displaystyle{ O(n^{1/ \epsilon}) }[/math], что позволяло получить [math]\displaystyle{ (1 + \epsilon ) \; }[/math]-аппроксимацию; впоследствии оно было улучшено. В частности, рандомизированный алгоритм Ароры [1] исполняется за время [math]\displaystyle{ O(n(log \; n)^{1/ \epsilon}) }[/math]; он может быть дерандомизирован, в силу чего время увеличится на [math]\displaystyle{ O(n) \; }[/math]. Теорема 3 также может быть распространена на более высокие размерности. Арора демонстрирует следующий результат.

Теорема 4 (Арора [1]). Для любого константного значения d евклидова задача коммивояжера на [math]\displaystyle{ \mathbb{R} ^d }[/math] имеет PTAS.

Для любого фиксированного значения c > 1 и любых n вершин из [math]\displaystyle{ \mathbb{R} ^d }[/math] существует рандомизированный алгоритм, который находит (1 + 1/c)-аппроксимацию для оптимальной траектории движения коммивояжера за время [math]\displaystyle{ O(n (log \; n)^{(O(\sqrt{d} c))^{d-1} }) }[/math]. В частности, для любых константных значений d и c время исполнения составляет [math]\displaystyle{ O(n (log \; n)^{O(1)}) }[/math]. Алгоритм может быть дерандомизирован, что увеличит время исполнения на коэффициент [math]\displaystyle{ O(n^d) \; }[/math].

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

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

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

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

Применение

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

Евклидова задача нахождения минимального дерева Штейнера. Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R} ^d }[/math] найти путь минимальной стоимости, соединяющий все точки S (стоимость сети равна сумме длин дуг, ее определяющих).

Теорема 7 ([1, 15]). Для каждого константного значения d евклидова задача нахождения минимального дерева Штейнера на [math]\displaystyle{ \mathbb{R} ^d }[/math] имеет PTAS.

Евклидова задача нахождения k медиан. Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R} ^d }[/math] и целого числа k найти k медиан между точками S, таких, что сумма расстояний от каждой точки S до ближайшей к ней медианы минимальна.

Теорема 8 ([5]). Для каждого константного значения d евклидова задача нахождения k медиан на [math]\displaystyle{ \mathbb{R} ^d }[/math] имеет PTAS.

Евклидова задача коммивояжера с k точками. Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R} ^d }[/math] и целого числа k найти путь минимальной длины, проходящий не менее k точек множества S.

Евклидова задача нахождения минимального дерева Штейнера с k точками. Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R} ^d }[/math] и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S.

Теорема 9 ([1]). Для каждого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на [math]\displaystyle{ \mathbb{R} ^d }[/math] имеют PTAS.

Евклидова задача нахождения k-связного подграфа минимальной стоимости. Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R} ^d }[/math] и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным.

Теорема 10 ([9]). Для каждого константного значения d и константного k, евклидова задача нахождения k-связного подграфа минимальной стоимости на [math]\displaystyle{ \mathbb{R} ^d }[/math] имеет PTAS.

Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем аппроксимации – то есть алгоритмов с временем исполнения [math]\displaystyle{ n^{O(log \; n)} }[/math]. К примеру, Арора и Карокостас [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)