Непрерывная задача оптимизации, которая сводится к TSP

11

Предположим, мне дан конечный набор точек на плоскости, и меня просят нарисовать дважды дифференцируемую кривую через , чтобы ее периметр был как можно меньше. Предполагая, что и , я могу формализовать эту проблему следующим образом: С ( Р ) р я р я = ( х я , у я ) х I < х я + 1p1,p2,..pnC(P)pipi=(xi,yi)xi<xi+1

Задача 1 ( под редакцией в ответ на комментарии Suresh в) Определить функции параметра таким образом, что длина дуги сведена к минимуму, при и для всех , мы имеем . х ( т ) , у ( т ) т л = [ т 0 , 1 ] C2x(t),y(t)tx(0)=x1,x(1)=xnti:x(ti)=xiy(ti)=yi)L=[t0,1]x2+y2dtx(0)=x1,x(1)=xnti:x(ti)=xiy(ti)=yi)

Как доказать (или, возможно, опровергнуть), что задача 1 является NP-трудной?

Почему я подозреваю , что NP-твердость Пусть предположения расслабилось. Очевидно, что функция минимальной длины дуги является коммивояжера туром «с. Может быть, ограничение только делает проблему гораздо сложнее?p i C 2C2piC2

Контекст Вариант этой проблемы была размещена на MSE . Он не получил ответа и там и МО . Учитывая , что это нетривиально решить эту проблему, я хочу , чтобы установить , насколько это тяжело.

PKG
источник
1
Ограничение, , кажется, делает эту проблему намного проще. В частности, если вы сейчас уронить ограничение, почему эта проблема не решается тривиально , потому что вы соедините точки прямыми линиями? C 2xi<xi+1C2
Суреш
1
Это не функция. Если вы «петлю вокруг» от к под ограничение , что , ваша кривая будет пересекать вертикальную линию дважды. p 2 x 1 < x 2 < x 3p3p2x1<x2<x3
Суреш
1
Не ясно, что вам нужно заявить , что вы имеете в виду под «определить» здесь. Это не стандартная терминология. Это даже не проблема , решение так использовать термин NP-жесткий , не имеет смысла.
Кава
1
@Suresh, вы можете расширить на выходной части? Я предполагаю, что вы имеете в виду вывод имени проклятия из множества перечисляемых кривых. Обратите внимание, что в этом случае не ясно, что оптимальная кривая всегда будет из этого класса. С другой стороны, если мы хотим найти лучший или хороший выбор между ними (или приближение с точностью до некоторого заданного параметра к оптимальной кривой), то следует указать класс параметрических кривых, в противном случае вопрос является неполным и не может быть ответил.
Кава
1
Ввод / вывод не конечный объект больше, например , если вы действительно имеет дела с вещественными числами / функция , то ваша проблема выше типа. Каждый бесконечные объекты задаются бесконечной серией приближений к предполагаемому объекту. Сеть CCA страница «s содержит больше ссылок , если вы заинтересованы.
Кава

Ответы:

12

Требование дифференцируемости не меняет природу проблемы: требование (непрерывность) или (бесконечная дифференцируемость) дает одинаковую нижнюю границу для длины и одинаковую порядок баллов и эквивалентен решению задачи коммивояжера.C C0C

Если у вас есть решение для TSP, у вас есть кривая которая проходит через все точки. И наоборот, предположим, что у вас есть кривая конечной длины, проходящая через все точки, и пусть будет порядка в который пересекает точки и соответствующие параметры (если кривая пересекает точку более одного раза, выберите любое из возможных значений ). Затем кривая строится из сегментовC 0 p σ ( 1 ) ,, p σ ( n ) t 1 ,, t n tn[ p σ ( 1 ) , p σ ( 2 ) ],,[ p σ ( n - 1 ) , p σ ( n ) ],[ p σC0C0pσ(1),,pσ(n)t1,,tntn[pσ(1),pσ(2)],,[pσ(n1),pσ(n)],[pσ(n),pσ(1)]короче, потому что для каждого сегмента прямая линия короче, чем любая другая кривая, соединяющая точку. Таким образом, для каждого упорядочения точек наилучшая кривая является решением TSP, а решение TSP обеспечивает наилучшее упорядочение точек.

Теперь давайте покажем, что требование, чтобы кривая была (или для любого ), не меняет лучшего порядка точек. Для любого решения TSP общей длины и любого мы можем округлить каждый угол, то есть построить кривую которая проходит точки в том же порядке и имеет длину в most (явная конструкция опирается на алгебраические функции и для определения ударных функций и из этих гладких связей между сегментами кривой, такими как который соединяется сС к клepsi>0 C л+epsi ; е - 1 / т 2 е 1 - 1 / х 2 (х- е - 1 / ( 1 - х ) 2 )у=0х=0CCkkϵ>0C+ϵe1/t2e11/x2(xe1/(1x)2)y=0 при и с при ; утомительно делать их явными, но они вычислимы); следовательно, нижняя граница для кривой такая же, как и для набора сегментов (обратите внимание, что нижняя граница в общем случае не достигается).x=0x = 1 C y=xx=1C

Жиль "ТАК - прекрати быть злым"
источник
Это именно тот аргумент, который я долго искал! Можете ли вы дать ссылку на утомительную конструкцию?
PKG
1
Это не совсем строго, особенно потому, что на плоскости вы можете получить сколь угодно хорошее приближение к TSP за полиномиальное время.
Суреш
Я думал, что вы могли бы приблизить TSP только с точностью до коэффициента 2 в поли времени?
PKG
@PKG У конструкции, вероятно, есть имя, но я боюсь, что мои классы исчисления были слишком давнишними, чтобы я мог их запомнить. Я только что вспомнил, что основное соединение называется функцией Bump.
Жиль "ТАК - перестань быть злым"
1
Это не ошибка как таковая. Ваше сокращение приблизительное - до некоторой ошибки . Это важно, потому что сокращение может быть дорогим (то есть экспоненциальным в ). Таким образом, сокращение не является точным. @PKG вы можете приблизить TSP к фактору 3/2 в общих метрических пространствах и произвольно приблизиться (с точностью до ) в плоскости или любом евклидовом пространстве. 1 / ϵ 1 + ϵϵ1/ϵ1+ϵ
Суреш