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 przez jest tak, że jego obwód jest tak mała jak to możliwe. Zakładając, że oraz , 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 parametru tak, że długość łuku $C^2$ $x(t),y(t)$ $t$ jest zminimalizowane, przy czyma dla wszystkichmamy. $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 . Być może ograniczenie 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.

— PKG
źródło

Ograniczenie, że

wydaje się znacznie ułatwiać problem. W szczególności, jeśli teraz zrzucisz ograniczenie

, dlaczego ten problem nie zostanie rozwiązany w sposób trywialny, ponieważ łączysz punkty prostymi liniami?

x_{i} < x_{i + 1}

$x_i < x_{i+1}$

C_{2}

$C_2$

— Suresh

To nie jest funkcja. Jeśli „zapętlisz się” od

, pod warunkiem, że

, twoja krzywa będzie przecinać linię pionową dwa razy.

p_{3}

$p_3$

p_{2}

$p_2$

x_{1} < x_{2} < x_{3}

$x_1 < x_2 < x_3$

— Suresh

Nie jest jasne, musisz podać tutaj, co masz na myśli, określając. To nie jest standardowa terminologia. Nie jest to nawet problem decyzyjny, więc użycie terminu NP-hard nie ma sensu.

— Kaveh

@Suresh, czy możesz rozwinąć część wyjściową? Zgaduję, że masz na myśli wyprowadzenie nazwy klątwy z wymiennego zestawu krzywych. Zauważ, że w takim przypadku nie jest jasne, czy optymalna krzywa zawsze będzie pochodzić z tej klasy. Z drugiej strony, jeśli chcemy znaleźć najlepszy lub dobry między nimi (lub przybliżeniem do pewnego danego parametru do krzywej optymalnej), należy podać klasę krzywych parametrycznych, w przeciwnym razie pytanie będzie niepełne i nie będzie możliwe odpowiedział

— Kaveh

Dane wejściowe / wyjściowe nie są już obiektami skończonymi, np. Jeśli naprawdę masz do czynienia z liczbami rzeczywistymi / funkcjami, to masz większy problem. Każdy nieskończony obiekt otrzymuje nieskończona seria przybliżeń do zamierzonego obiektu. Strona sieci CCA zawiera więcej linków, jeśli jesteś zainteresowany.

— Kaveh

Wymóg różniczkowalności nie zmienia charakteru problemu: wymaganie (ciągłość) lub (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 krzywą skończonej długości, który przechodzi przez wszystkie punkty i niech jest kolejność, w jakiej ona przechodzi przez punkty i odpowiednie parametry (jeśli krzywa przemierza punkt więcej niż jeden raz, wybierz dowolną z możliwych wartości ). Następnie krzywa zbudowana z 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 dla dowolnego ), nie zmienia najlepszej kolejności punktów. Dla każdego rozwiązania TSP o całkowitej długości i dowolnym możemy zaokrąglić każdy narożnik, tj. Zbudować krzywą 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 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ę przy oraz przy ; wyraźne jest uciążliwe, ale można je obliczyć); stąd dolna granica dlakrzywej 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}$

— Gilles „SO- przestań być zły”
źródło

Jest to dokładnie argument Szukałem przez długi czas! Czy możesz podać odniesienie do żmudnej konstrukcji?

— PKG

Nie jest to całkowicie rygorystyczne, zwłaszcza że w płaszczyźnie można uzyskać dowolnie dobre przybliżenie do TSP w czasie wielomianowym.

— Suresh

Myślałem, że możesz zbliżyć TSP tylko w czasie 2 razy w czasie wielokrotnym?

— PKG

@PKG Konstrukcja prawdopodobnie ma nazwę, ale obawiam się, że moje klasy rachunku różniczkowego były zbyt dawno temu, żebym je zapamiętał. Właśnie pamiętam, że podstawowe połączenie nazywa się funkcją wypukłości.

— Gilles „SO- przestań być zły”

To nie jest błąd sam w sobie. Twoja redukcja jest przybliżona - do pewnego terminu błędu

. Ma to znaczenie, ponieważ redukcja może być kosztowna (tj. Wykładnicza w

). Więc redukcja nie jest dokładna. @PKG można przybliżać TSP do współczynnika 3/2 w ogólnych przestrzeniach metrycznych i dowolnie zamykać (w zakresie

) w płaszczyźnie lub dowolnej przestrzeni euklidesowej.

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

1 + ϵ

$1+\epsilon$

— Suresh