Ein kontinuierliches Optimierungsproblem, das sich auf TSP reduziert

11

Angenommen, ich bekomme eine endliche Menge von Punkten p1,p2,..pn in der Ebene und gebeten, eine doppelt differenzierbare Kurve C(P) durch die zu zeichnen pi, so dass ihr Umfang so klein wie möglich ist. Angenommen, und , kann ich dieses Problem wie folgt formalisieren:pi=(xi,yi)xi<xi+1

Aufgabe 1 (bearbeitet als Antwort auf Sureshs Kommentare) Bestimmen Sie die -Funktionen eines Parameters so, dass die Bogenlänge wird minimiert, mit und für alle haben wir . x ( t ) , y ( t ) t L = [ t 0 , 1 ] C2x(t),y(t)tL=[t0,1]x2+y2dtx(0)=x1,x(1)=xnti:x(ti)=xiy(ti)=yi)

Wie kann ich beweisen (oder vielleicht widerlegen), dass Problem 1 NP-schwer ist?

Warum ich NP-Härte vermute Angenommen, die Annahme ist gelockert. Offensichtlich ist die Funktion der minimalen Bogenlänge die Travelling Salesman-Tour der . Vielleicht macht die Beschränkung das Problem nur viel schwieriger?p i C 2C2piC2

Kontext Eine Variante dieses Problems wurde auf MSE veröffentlicht . Es hat dort und auf MO keine Antwort erhalten . Da es nicht trivial ist, das Problem zu lösen, möchte ich feststellen, wie schwierig es ist.

PKG
quelle
1
Die Einschränkung, dass scheint das Problem viel einfacher zu machen. Insbesondere wenn Sie jetzt die C 2 -Einschränkung fallen lassen, warum ist dieses Problem nicht trivial gelöst, weil Sie die Punkte durch gerade Linien verbinden? xi<xi+1C2
Suresh
1
Das ist keine Funktion. Wenn Sie von nach p 2 "schleifen" , unter der Bedingung, dass x 1 < x 2 < x 3 ist , schneidet Ihre Kurve zweimal eine vertikale Linie. p3p2x1<x2<x3
Suresh
1
Es ist nicht klar, Sie müssen hier angeben, was Sie unter "bestimmen" verstehen. Es ist keine Standardterminologie. Es ist nicht einmal ein Entscheidungsproblem, daher macht es keinen Sinn, den Begriff NP-hart zu verwenden.
Kaveh
1
@Suresh, können Sie den Ausgabeteil erweitern? Ich vermute, Sie meinen, Sie geben den Namen eines Fluches aus einer Reihe von Kurven aus. Beachten Sie, dass in diesem Fall nicht klar ist, dass die optimale Kurve immer aus dieser Klasse stammt. Wenn wir andererseits den besten oder einen guten zwischen diesen finden wollen (oder eine Annäherung an einen bestimmten Parameter an die optimale Kurve), sollte die Klasse der parametrischen Kurven angegeben werden, andernfalls ist die Frage unvollständig und kann nicht sein antwortete.
Kaveh
1
Die Eingabe / Ausgabe ist kein endliches Objekt mehr, z. B. wenn Sie sich wirklich mit reellen Zahlen / Funktionen beschäftigen, ist Ihr Problem vom höheren Typ. Jedes unendliche Objekt wird durch eine unendliche Reihe von Annäherungen an das beabsichtigte Objekt gegeben. Die Seite des CCA-Netzwerks enthält weitere Links, wenn Sie interessiert sind.
Kaveh

Antworten:

12

Die Differenzierungsanforderung ändert nichts an der Art des Problems: Das Erfordernis von (Kontinuität) oder C (unendliche Differenzierbarkeit) ergibt dieselbe Untergrenze für die Länge und dieselbe Reihenfolge von Punkten und entspricht der Lösung des Problems des reisenden Verkäufers .C0C

Wenn Sie eine Lösung für den TSP haben, haben Sie eine -Kurve, die alle Punkte durchläuft. Nehmen wir umgekehrt an, Sie haben eine C 0 -Kurve endlicher Länge, die durch alle Punkte verläuft, und lassen Sie p σ ( 1 ) , , p σ ( n ) die Reihenfolge sein, in der sie die Punkte und t 1 , , t durchquert n die entsprechenden Parameter (wenn die Kurve einen Punkt mehr als einmal durchquert, wählen Sie einen der möglichen Werte von t ). Dann wird die Kurve aus n Segmenten aufgebaut [C0C0pσ(1),,pσ(n)t1,,tntn[pσ(1),pσ(2)],,[pσ(n1),pσ(n)],[pσ(n),pσ(1)]ist kürzer, weil für jedes Segment eine gerade Linie kürzer ist als jede andere Kurve, die den Punkt verbindet. Somit ist für jede Reihenfolge der Punkte die beste Kurve eine TSP-Lösung, und die TSP-Lösung bietet die beste Reihenfolge der Punkte.

Lassen Sie uns nun zeigen, dass das Erfordernis, dass die Kurve (oder C k für jedes k ), die beste Reihenfolge der Punkte nicht ändert. Für jede TSP-Lösung mit der Gesamtlänge und jeder ϵ > 0 können wir jede Ecke abrunden, dh eine C -Kurve erstellen , die die Punkte in derselben Reihenfolge durchläuft und eine Länge von höchstens + ϵ hat (die explizite Konstruktion basiert auf algebraische Funktionen und e - 1 / t 2 zur Definition von Höckerfunktionen und aus diesen glatten Verbindungen zwischen Kurvensegmenten wie zCCkkϵ>0C+ϵe1/t2 das mit y = 0 bei x = 0 und mit y = x bei x = 1 verbunden ist ; es ist mühsam, diese explizit zu machen, aber sie sind berechenbar); Daher ist die Untergrenze für eine C -Kurve dieselbe wie für eine Sammlung von Segmenten (beachten Sie, dass die Untergrenze im Allgemeinen nicht erreicht wird).e11/x2(xe1/(1x)2)y=0x=0y=xx=1C

Gilles 'SO - hör auf böse zu sein'
quelle
Dies ist genau das Argument, nach dem ich lange gesucht habe! Können Sie eine Referenz für die mühsame Konstruktion geben?
PKG
1
Dies ist nicht ganz streng, zumal man in der Ebene eine beliebig gute Annäherung an TSP in Polynomzeit erhalten kann.
Suresh
Ich dachte, Sie könnten TSP in Poly-Zeit nur auf einen Faktor von 2 approximieren?
PKG
@PKG Die Konstruktion hat wahrscheinlich einen Namen, aber ich fürchte, meine Kalkülklassen sind zu lange her, als dass ich mich daran erinnern könnte. Ich habe mich gerade daran erinnert, dass die grundlegende Verbindung als Bump-Funktion bezeichnet wird.
Gilles 'SO - hör auf böse zu sein'
1
Es ist an sich kein Fehler. Ihre Reduzierung ist ungefähr - bis zu einem Fehlerbegriff . Dies ist wichtig, da die Reduzierung teuer sein kann (dh exponentiell in 1 / ϵ ). Die Reduzierung ist also nicht genau. @PKG Sie können TSP in allgemeinen metrischen Räumen auf den Faktor 3/2 approximieren und in der Ebene oder einem beliebigen euklidischen Raum beliebig nahe (innerhalb von 1 + ϵ ) schließen. ϵ1/ϵ1+ϵ
Suresh