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

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показано 55 промежуточных версий 1 участника)
Строка 8: Строка 8:


== Нотация ==
== Нотация ==
Евклидова задача коммивояжера заключается в следующем: для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}\ ^d</math> найти путь минимальной длины, проходящий через каждую точку ровно один раз.
Евклидова задача коммивояжера заключается в следующем: для заданного множества 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>.
Стоимость <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 точек в евклидовом пространстве Rd, для целого d > 2, евклидов граф (сеть) представляет собой граф G = (S; E), где E – множество прямолинейных сегментов, соединяющих пары точек из S. Если все пары точек в S соединены дугами из E, то G называется полным евклидовым графом на S. Стоимость графа равна сумме стоимостей дуг графа:
Для заданного множества 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) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию.
[[Аппроксимационная схема с полиномиальным временем выполнения]] (PTAS) представляет собой семейство алгоритмов <math> \big\{  A_{\varepsilon} \big\} </math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \; </math> алгоритм <math>A_{\varepsilon} \; </math> выполняется за время, полиномиальное относительно размера входного графа, и дает <math>(1 + \varepsilon) \; </math>-аппроксимацию.


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


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


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




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


Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства Rd и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз).
Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз).
 
Аппроксимируемость евклидовой задачи коммивояжера в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют [[неравенство треугольника|неравенству треугольника]] (этот случай обозначается как [[метрическая задача коммивояжера]]), существует алгоритм 3/2-аппроксимации с полиномиальным временем выполнения, разработанный Кристофидесом [8]; также известно, что PTAS для этого случая не существует (если только не верно P = NP). Тревизан [17] усилил этот результат, включив евклидовы графы более высоких размерностей (тот же результат имеет место для любой <math>\ell _p</math>-метрики).
 


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


'''Теорема 2 (Тревизан [17]). Если d > log n, то существует константа e > 0, такая, что евклидова задача коммивояжера на R является NP-полной с аппроксимацией с коэффициентом 1 + e.
В частности, из этого результата следует, что если d > log n, то евклидова задача коммивояжера на Rd не имеет PTAS, за исключением случая, когда'''


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


Тот же результат имеет место для любой lp-метрики. Кроме того, из теоремы 2 следует, что евклидова задача коммивояжера на Rlog n является APX PB-полной при ограничении по E и APX-полной при ограничении по AP.
Считалось, что теорема 2 может выполняться для небольших значений d, в частности, для d = 2, однако это было независимым образом опровергнуто Аророй [1] и Митчеллом [13].


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


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


Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую «структурную теорему». Она демонстрирует, что существует (1 + e)-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства припомощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме.
Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <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 также может быть распространена на более высокие размерности. Арора демонстрирует следующий результат.


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


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


Для каждого фиксированного значения c > 1 и любых n вершин из Rd существует рандомизированный алгоритм, который находит (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за время O(n (log n)^°^dc^ ). В частности, для любых константных значений d и c время исполнения составляет O(n (log n)O(1)). Алгоритм может быть дерандомизирован, что увеличит время исполнения на коэффициент O(nd).
'''Для любого фиксированного значения 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] впоследствии расширили эту теорему, предложив следующую.
Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую.
Теорема 5 (Рао и Смит [15]). Существует детерминированный алгоритм, вычисляющий (1 + 1/c)-аппроксимацию
^
п +
оптимальной траектории движения коммивояжера за время n log n).


Существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время {c\fd)°^c^d:) ) n + O(d n log n).
 
'''Теорема 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, Рао и Смит продемонстрировали следующий результат.
Для отдельного, наиболее интересного случая, при d = 2, Рао и Смит продемонстрировали следующий результат.


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


Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для оптимального пути коммивояжера за ожидаемое время O(n 2cO(1)     + n log n).
'''Теорема 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], нашли множество вариантов применения в разработке схем аппроксимации с полиномиальным временем исполнения для задач геометрической оптимизации.
Техники, разработанные Аророй [1] и Митчеллом [13], нашли множество вариантов применения в разработке аппроксимационных схем с полиномиальным временем выполнения для задач геометрической оптимизации.


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


== См. также ==
== См. также ==
Строка 151: Строка 147:


17. Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and SteinerTree. SIAM J. Comput. 30(2), 475-485 (2000)
17. Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and SteinerTree. SIAM J. Comput. 30(2), 475-485 (2000)
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 10:46, 7 декабря 2024

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

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


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

Рассматриваются 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].

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

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

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

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

См. также


Литература

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)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Евклидова_задача_коммивояжера&oldid=15712