Un problème d'optimisation continue qui se réduit à TSP

Supposons que je me donne un ensemble fini de points dans le plan, et a demandé de tracer une courbe C ( P ) deux fois différenciable à travers les p i , de sorte que son périmètre soit aussi petit que possible. En supposant que p i = ( x i , y i ) et x i < x i + 1 , je peux formaliser ce problème comme suit:$p_1,p_2,..p_n$$C(P)$$p_i$$p_i=(x_i,y_i)$$x_i<x_{i+1}$

Problème 1 (édité en réponse aux commentaires de Suresh) Déterminer les fonctions x ( t ) , y ( t ) d'un paramètre t tel que l'arclength L = ∫ [ t $C^2$$x(t),y(t)$$t$ est minimisé, avecx(0)=x1,x(1)=xnet pour toutti:x(ti)=xi, on ay(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)$

Comment puis-je prouver (ou peut-être réfuter) que le problème 1 est NP-difficile?

Pourquoi je soupçonne la dureté NP Supposons que l' hypothèse soit relâchée. De toute évidence, la fonction de la longueur d'arc minimale est la visite du voyageur de commerce du p $C^2$$p_i$ . Peut-être que la contrainte ne fait que rendre le problème beaucoup plus difficile?$C^2$

Le contexte Une variante de ce problème a été publiée sur MSE . Il n'a pas reçu de réponse là-bas et le MO . Étant donné qu'il n'est pas trivial de résoudre le problème, je veux établir à quel point il est difficile.

L'exigence de différentiabilité ne change pas la nature du problème: exiger (continuité) ou C ∞ (différentiabilité infinie) donne la même borne inférieure pour la longueur et le même ordre de points, et équivaut à résoudre le problème du voyageur de commerce .$\mathcal{C}^0$$\mathcal{C}^{\infty}$

Si vous avez une solution au TSP, vous avez une courbe qui passe par tous les points. Inversement, supposons que vous ayez une courbe C 0 de longueur finie qui passe par tous les points, et que p σ ( 1 ) , … , p σ ( n ) soit l'ordre dans lequel elle parcourt les points et t 1 , … , t n les paramètres correspondants (si la courbe traverse un point plusieurs fois, choisissez l'une des valeurs possibles de t ). Ensuite, la courbe construite à partir de n segments $\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)}]$ is shorter, because for each segment a straight line is shorter than any other curve that connects the point. Thus for every ordering of the points, the best curve is a TSP solution, and the TSP solution provides the best ordering of the points.

Let's now show that requiring the curve to be $\mathcal{C}^{\infty}$ (or $\mathcal{C}^k$ for any $k$) doesn't change the best ordering of points. For any TSP solution of total length $\ell$ and any $\epsilon > 0$, we can round every corner, i.e. build a $\mathcal{C}^{\infty}$ curve that traverses the points in the same order and has a length of at most $\ell + \epsilon$ (the explicit construction relies on algebraic functions and $e^{-1/t^2}$ to define bump functions and from those smooth connections between curve segments such as $e^{1-1/x^2} (x-e^{-1/(1-x)^2})$ which connects with $y=0$ at $x=0$ and with $y=x$ at $x=1$; it is tedious to make these explicit, but they are computable); hence, the lower bound for a $\mathcal{C}^{\infty}$ curve is the same as for a collection of segments (note that the lower bound is not reached in general).