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

Предположим, мне дан конечный набор точек на плоскости, и меня просят нарисовать дважды дифференцируемую кривую через , чтобы ее периметр был как можно меньше. Предполагая, что и , я могу формализовать эту проблему следующим образом: С ( Р ) р я р я = ( х я , у я ) х I < х я + $p_1,p_2,..p_n$$C(P)$$p_i$$p_i=(x_i,y_i)$$x_i<x_{i+1}$

Задача 1 ( под редакцией в ответ на комментарии Suresh в) Определить функции параметра таким образом, что длина дуги сведена к минимуму, при и для всех , мы имеем . х ( т ) , у ( т ) т л = ∫ [ т ∈ 0 , 1 ] $C^2$$x(t),y(t)$$t$x(0)=x1,x(1)=xnti:x(ti)=xiy(ti)=yi$L = \int_{[t \in 0,1]} \sqrt{x'^2+y'^2}dt$$x(0) = x_1, x(1) = x_n$$t_i: x(t_i) = x_i$$y(t_i)=y_i)$

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

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

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

Требование дифференцируемости не меняет природу проблемы: требование (непрерывность) или (бесконечная дифференцируемость) дает одинаковую нижнюю границу для длины и одинаковую порядок баллов и эквивалентен решению задачи коммивояжера.C $\mathcal{C}^0$$\mathcal{C}^{\infty}$

Если у вас есть решение для TSP, у вас есть кривая которая проходит через все точки. И наоборот, предположим, что у вас есть кривая конечной длины, проходящая через все точки, и пусть будет порядка в который пересекает точки и соответствующие параметры (если кривая пересекает точку более одного раза, выберите любое из возможных значений ). Затем кривая строится из сегментовC 0 p σ ( 1 ) ,…, p σ ( n ) t 1 ,…, t n tn[ p σ ( 1 ) , p σ ( 2 ) ],…,[ p σ ( n - 1 ) , p σ ( n ) ],[ p $\mathcal{C}^0$$\mathcal{C}^0$$p_{\sigma(1)}, \ldots, p_{\sigma(n)}$$t_1,\ldots,t_n$$t$$n$$[p_{\sigma(1)},p_{\sigma(2)}], \ldots, [p_{\sigma(n-1)},p_{\sigma(n)}], [p_{\sigma(n)},p_{\sigma(1)}]$короче, потому что для каждого сегмента прямая линия короче, чем любая другая кривая, соединяющая точку. Таким образом, для каждого упорядочения точек наилучшая кривая является решением TSP, а решение TSP обеспечивает наилучшее упорядочение точек.

Теперь давайте покажем, что требование, чтобы кривая была (или для любого ), не меняет лучшего порядка точек. Для любого решения TSP общей длины и любого мы можем округлить каждый угол, то есть построить кривую которая проходит точки в том же порядке и имеет длину в most (явная конструкция опирается на алгебраические функции и для определения ударных функций и из этих гладких связей между сегментами кривой, такими как который соединяется сС к клepsi>0 C ∞ л+epsi ; е - 1 / т 2 е 1 - 1 / х 2 (х- е - 1 / ( 1 - х ) 2 )у=0х=$\mathcal{C}^{\infty}$$\mathcal{C}^k$$k$$\ell$$\epsilon > 0$$\mathcal{C}^{\infty}$$\ell + \epsilon$$e^{-1/t^2}$$e^{1-1/x^2} (x-e^{-1/(1-x)^2})$$y=0$ при и с при ; утомительно делать их явными, но они вычислимы); следовательно, нижняя граница для кривой такая же, как и для набора сегментов (обратите внимание, что нижняя граница в общем случае не достигается).$x=0$x = 1 C $y=x$$x=1$$\mathcal{C}^{\infty}$