Problem ciągłej optymalizacji, który ogranicza się do TSP

Załóżmy, że mam podane skończony zbiór punktów w płaszczyźnie i poprosiła zwrócić krzywej dwukrotnie różniczkowalnymi C ( P ) przez P i jest tak, że jego obwód jest tak mała jak to możliwe. Zakładając, że p i = ( x i , y i ) oraz x i < x i + 1 , mogę sformalizować ten problem jako:$p_1,p_2,..p_n$$C(P)$$p_i$$p_i=(x_i,y_i)$$x_i<x_{i+1}$

Zadanie 1 (wydanej w odpowiedzi na uwagi Suresh'S) Określić funkcji x ( t ) , y ( t ) parametru T tak, że długość łuku L = ∫ [ t ∈ 0 , 1 ] $C^2$$x(t),y(t)$$t$ jest zminimalizowane, przy czymx(0)=x1,x(1)=xn,a dla wszystkichti:x(ti)=ximamyy(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)$

Jak udowodnić (lub obalić), że problem 1 jest trudny do NP?

Dlaczego podejrzewam twardość NP Załóżmy, że założenie jest złagodzone. Najwyraźniej funkcją minimalnego arclue jest trasa Traveling Salesman po p i . Być może ograniczenie C 2 tylko utrudnia problem?$C^2$$p_i$$C^2$

Kontekst Odmiana tego problemu została opublikowana na MSE . Nie otrzymał odpowiedzi zarówno tam, jak i na MO . Biorąc pod uwagę, że rozwiązanie problemu nie jest łatwe, chcę ustalić, jak trudne jest.

Wymóg różniczkowalności nie zmienia charakteru problemu: wymaganie (ciągłość) lub C ∞ (nieskończona odmienność) daje to samo dolne ograniczenie dla długości i tej samej kolejności punktów i jest równoważne rozwiązaniu problemu podróżującego sprzedawcy .$\mathcal{C}^0$$\mathcal{C}^{\infty}$

Jeśli masz rozwiązanie TSP, masz krzywą która przechodzi przez wszystkie punkty. Odwrotnie, załóżmy, że masz C 0 krzywą skończonej długości, który przechodzi przez wszystkie punkty i niech p σ ( 1 ) , ... , p σ ( n ) jest kolejność, w jakiej ona przechodzi przez punkty i t 1 , ... , t n odpowiednie parametry (jeśli krzywa przemierza punkt więcej niż jeden raz, wybierz dowolną z możliwych wartości t ). Następnie krzywa zbudowana z n segmentów $\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)}]$jest krótsza, ponieważ dla każdego odcinka linia prosta jest krótsza niż jakakolwiek inna krzywa łącząca punkt. Zatem dla każdego uporządkowania punktów najlepszą krzywą jest rozwiązanie TSP, a rozwiązanie TSP zapewnia najlepsze uporządkowanie punktów.

Pokażmy teraz, że wymaganie, aby krzywa była (lub C k dla dowolnego k ), nie zmienia najlepszej kolejności punktów. Dla każdego rozwiązania TSP o całkowitej długości ℓ i dowolnym ϵ > 0 możemy zaokrąglić każdy narożnik, tj. Zbudować krzywą C ∞, która przecina punkty w tej samej kolejności i ma długość co najwyżej ℓ + ϵ (wyraźna konstrukcja opiera się na funkcje algebraiczne i e - 1 / t 2 do definiowania funkcji wypukłości oraz z tych płynnych połączeń między segmentami krzywej, takich jak$\mathcal{C}^{\infty}$$\mathcal{C}^k$$k$$\ell$$\epsilon > 0$$\mathcal{C}^{\infty}$$\ell + \epsilon$$e^{-1/t^2}$ który łączy się zy = 0 przy x = 0 oraz zy = x przy x = 1 ; wyraźne jest uciążliwe, ale można je obliczyć); stąd dolna granica dlakrzywej C ∞ jest taka sama jak dla zbioru segmentów (zauważ, że dolna granica nie jest ogólnie osiągana).$e^{1-1/x^2} (x-e^{-1/(1-x)^2})$$y=0$$x=0$$y=x$$x=1$$\mathcal{C}^{\infty}$