Евклидова задача коммивояжера: различия между версиями
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 53 промежуточные версии 1 участника) | |||
| Строка 10: | Строка 10: | ||
Евклидова задача коммивояжера заключается в следующем: для заданного множества 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) \; </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>\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] содержит полную информацию о | Классическая работа Лоулера и коллег [12] содержит полную информацию о подходах к решению евклидовой задачи коммивояжера. Обзор Берна и Эппстайна [7] представляет состояние дел в исследованиях геометрических евклидовых задач коммивояжера вплоть до 1995 года; Арора в своем обзоре [2] рассматривает работы, выполненные после 1995 года. | ||
== Основные результаты == | == Основные результаты == | ||
Известно, что в графах общего вида задача коммивояжера является NP-полной; то же верно для евклидовой задачи коммивояжера [11], [14]. | Известно, что в графах общего вида задача коммивояжера является NP-полной; то же верно для евклидовой задачи коммивояжера ([11], [14]). | ||
'''Теорема 1. Евклидова задача коммивояжера является NP-полной.''' | '''Теорема 1. Евклидова задача коммивояжера является NP-полной.''' | ||
Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства | Как ни удивительно, до сих пор неизвестно, является ли «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.''' | '''Теорема 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]). Для | '''Теорема 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] впоследствии расширили эту теорему, предложив следующую. | Рао и Смит [15] впоследствии расширили эту теорему, предложив следующую. | ||
Существует рандомизированный алгоритм Монте-Карло, который достигает успеха с вероятностью не менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для | |||
'''Теорема 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)-аппроксимацию для оптимальной траектории движения коммивояжера за время <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 точек в евклидовом пространстве | ''Евклидова задача нахождения минимального дерева Штейнера''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> найти путь с минимальной стоимостью сети, соединяющий все точки S (стоимость сети равна сумме длин дуг, ее определяющих). | ||
'''Теорема 7 ([1, 15]). Для | '''Теорема 7 ([1, 15]). Для любого константного значения d евклидова задача нахождения минимального дерева Штейнера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
Для заданного множества S из n точек в евклидовом пространстве | ''Евклидова задача нахождения k медиан''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти k медиан между точками S, таких, что сумма расстояний от каждой точки S до ближайшей к ней медианы минимальна. | ||
'''Теорема 8 ([5]). Для | '''Теорема 8 ([5]). Для любого константного значения d евклидова задача нахождения k медиан на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
Для заданного множества S из n точек в евклидовом пространстве | ''Евклидова задача коммивояжера с k точками''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти путь минимальной длины, проходящий не менее чем через k точек множества S. | ||
Для заданного множества S из n точек в евклидовом пространстве | ''Евклидова задача нахождения минимального дерева Штейнера с k точками''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S. | ||
'''Теорема 9 ([1]). Для | '''Теорема 9 ([1]). Для любого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на <math>\mathbb{R} ^d</math> имеют PTAS.''' | ||
Для заданного множества S из n точек в евклидовом пространстве | ''Евклидова задача нахождения k-связного подграфа минимальной стоимости''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным. | ||
'''Теорема 10 ([9]). Для | '''Теорема 10 ([9]). Для любого константного значения d и константного k, евклидова задача нахождения k-связного подграфа минимальной стоимости на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных схем | |||
Техники, разработанные Аророй [1] и Митчеллом [13], также привели к созданию квазиполиномиальных аппроксимационных схем – то есть алгоритмов с временем выполнения <math>n^{O(log \; n)}</math>. К примеру, Арора и Карокостас [4] создали аппроксимационную схему с квазиполиномиальным временем выполнения для решения евклидовой задачи нахождения минимального времени ожидания; Реми и Стегер [16] предложили аппроксимационную схему с полиномиальным временем выполнения для решения задачи триангуляции с минимальным весом. | |||
Более подробные обзоры можно найти в [2] и [10]. | Более подробные обзоры можно найти в [2] и [10]. | ||
== Расширение на планарные графы == | == Расширение на планарные графы == | ||
Подход динамического программирования, используемый | Подход динамического программирования, используемый Аророй [1] и Митчеллом [13], также имеет отношение к недавним достижениям в области нескольких проблем оптимизации для планарных графов. В частности, Арора и коллеги [3] разработали PTAS для задачи коммивояжера на взвешенных планарных графах; существует также PTAS для задачи нахождения двусвязного остовного подграфа планарного графа, имеющего минимальную стоимость [6]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается неясным интересный вопрос: могут ли | Остается неясным интересный вопрос: могут ли упомянутые выше квазиполиномиальные аппроксимационные схемы (для нахождения минимального времени ожидания и триангуляции с минимальным весом) быть расширены для получения аппроксимационных схем с полиномиальным временем выполнения. Другие открытые вопросы можно найти в [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].
См. также
- Метрическая задача коммивояжера
- Минимальные 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)
