4430
правок
Евклидова задача коммивояжера: различия между версиями
Материал из WEGA
Евклидова задача коммивояжера (посмотреть исходный код)
Версия от 14:25, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показаны 34 промежуточные версии этого же участника) | |||
| Строка 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>cost(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] содержит полную информацию о подходах к решению евклидовой задачи коммивояжера. Обзор Берна и Эппстайна [7] представляет состояние дел в исследованиях геометрических евклидовых задач коммивояжера вплоть до 1995; Арора в своем обзоре [2] рассматривает работы, выполненные после 1995 года. | Классическая работа Лоулера и коллег [12] содержит полную информацию о подходах к решению евклидовой задачи коммивояжера. Обзор Берна и Эппстайна [7] представляет состояние дел в исследованиях геометрических евклидовых задач коммивояжера вплоть до 1995 года; Арора в своем обзоре [2] рассматривает работы, выполненные после 1995 года. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 28: | Строка 28: | ||
Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз). | Как ни удивительно, до сих пор неизвестно, является ли «decision»-версия этой задачи NP-полной [11] («decision»-версия евклидовой задачи коммивояжера заключается в поиске ответа на вопрос, существует ли для заданных евклидового пространства <math>\mathbb{R} ^d</math> и числа t простой путь с длиной, меньшей t, проходящий через каждую точку ровно один раз). | ||
Аппроксимируемость евклидовой задачи коммивояжера в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют неравенству треугольника (этот случай обозначается как [[метрическая задача коммивояжера]]), существует алгоритм 3/2-аппроксимации с полиномиальным временем | Аппроксимируемость евклидовой задачи коммивояжера в последние десятилетия активно изучалась. Нетрудно увидеть, что эта задача неаппроксимируема за полиномиальное время (если только не окажется верным P = NP) для произвольных графов с произвольной стоимостью дуг. Если веса удовлетворяют [[неравенство треугольника|неравенству треугольника]] (этот случай обозначается как [[метрическая задача коммивояжера]]), существует алгоритм 3/2-аппроксимации с полиномиальным временем выполнения, разработанный Кристофидесом [8]; также известно, что PTAS для этого случая не существует (если только не верно P = NP). Тревизан [17] усилил этот результат, включив евклидовы графы более высоких размерностей (тот же результат имеет место для любой <math>\ell _p</math>-метрики). | ||
| Строка 36: | Строка 36: | ||
Тот же результат | Тот же результат верен для любой <math>\ell _p</math>-метрики. Кроме того, из теоремы 2 следует, что евклидова задача коммивояжера на <math>\mathbb{R} ^{log \; n}</math> является APX PB-полной при ограничении по E и APX-полной при ограничении по AP. | ||
Считалось, что теорема 2 может выполняться для небольших значений d, в частности, для d = 2, однако это было независимым образом опровергнуто Аророй [1] и Митчеллом [13]. | Считалось, что теорема 2 может выполняться для небольших значений d, в частности, для d = 2, однако это было независимым образом опровергнуто Аророй [1] и Митчеллом [13]. | ||
| Строка 45: | Строка 45: | ||
Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме. | ||
Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время | Исходные алгоритмы, представленные в первой версии [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, Рао и Смит продемонстрировали следующий результат. | ||
Существует рандомизированный алгоритм Монте-Карло, который не достигает успеха с вероятностью менее 1/2, вычисляя (1 + 1/c)-аппроксимацию для | '''Теорема 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 точек в евклидовом пространстве <math>\mathbb{R} ^d</math> найти путь с минимальной стоимостью сети, соединяющий все точки S (стоимость сети равна сумме длин дуг, ее определяющих). | ||
'''Теорема 7 ([1, 15]). Для любого константного значения d евклидова задача нахождения минимального дерева Штейнера на <math>\mathbb{R} ^d</math> имеет PTAS.''' | |||
''Евклидова задача нахождения k медиан'' | ''Евклидова задача нахождения k медиан''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти k медиан между точками S, таких, что сумма расстояний от каждой точки S до ближайшей к ней медианы минимальна. | ||
Для | '''Теорема 8 ([5]). Для любого константного значения d евклидова задача нахождения k медиан на <math>\mathbb{R} ^d</math> имеет PTAS.''' | ||
''Евклидова задача коммивояжера с k точками'' | ''Евклидова задача коммивояжера с k точками''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти путь минимальной длины, проходящий не менее чем через k точек множества S. | ||
''Евклидова задача нахождения минимального дерева Штейнера с k точками'' | ''Евклидова задача нахождения минимального дерева Штейнера с k точками''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти кратчайшее дерево, содержащее не менее k точек множества S. | ||
Для | '''Теорема 9 ([1]). Для любого константного значения d евклидовы задачи коммивояжера с k точками и нахождения минимального дерева Штейнера с k точками на <math>\mathbb{R} ^d</math> имеют PTAS.''' | ||
''Евклидова задача нахождения k-связного подграфа минимальной стоимости'' | ''Евклидова задача нахождения k-связного подграфа минимальной стоимости''. Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R} ^d</math> и целого числа k найти подграф полного графа S минимальной стоимости, являющийся k-связным. | ||
Для | '''Теорема 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]. | ||
== См. также == | == См. также == | ||
