Tsp

Wissenschaft Informatik
#1

hi,

das traveling salesman problem ist np-vollständig. so viel ich weiß, gibt es heute noch keinen nachweis, dass es exakte problemlösungen mit nicht-exponenziellem (bloß-polynomialen) zeitbedarf gibt (trotz plotnikov 2000).

frage: wie ist es dann möglich, für doch sehr große zahlen von „städten“ offenbar exakte lösungen zu haben?

link: http://www.tsp.gatech.edu/

dort sieht man lösungen zu (z.b.) n=24978 (schweden, 2004).

sind das lösungen nur für spezielle anordnungen?
oder sind das „näherungslösungen“?
wie ist das mit exponenziell steigendem zeitbedarf?
oder ist es so (was ich vermute), dass es zwar deutlich bessere verfahren als „brute force“ gibt, die aber trotzdem exponenziell steigenden zeitbedarf haben?

???

m.

#2

Moien

das traveling salesman problem ist np-vollständig. so viel ich
weiß, gibt es heute noch keinen nachweis, dass es exakte
problemlösungen mit nicht-exponenziellem (bloß-polynomialen)
zeitbedarf gibt

Da fehlt ein kleines, aber entscheidendes Wort: deterministische. Die ganze Diskussion zu NP und P ist hinfällig sobald ein Zufall in’s Spiel kommt.

(trotz plotnikov 2000).

Streitet man da immernoch oder wurde schon ein Gegenbeispiel gefunden ?

frage: wie ist es dann möglich, für doch sehr große zahlen von
„städten“ offenbar exakte lösungen zu haben?

Jede Aufgabenstellung zum TSP hat mindestens eine exakte Lösung, man kennt sie nur nicht unbedingt. TSP fragt ja nur nach dem kürzesten Weg…

sind das lösungen nur für spezielle anordnungen?
oder sind das „näherungslösungen“?
wie ist das mit exponenziell steigendem zeitbedarf?

Einfach: man kann schnell feststellen ob eine Lösung optimal ist (such im Netz, beim TSP fällt mir gerade nicht mehr ein wie…). Also benutzt man einen Zufallsalgo der wahrscheinlich „gute“ Lösungen erzeugt und überprüft diese. Bei vielen Fällen (die nicht gerade mit der Absicht den Zufallsalgo zu stören) findet sich so sehr schnell die Lösung.

cu

#3

hi,

Jede Aufgabenstellung zum TSP hat mindestens eine exakte
Lösung, man kennt sie nur nicht unbedingt. TSP fragt ja nur
nach dem kürzesten Weg…

das ist klar. TSP ist ein endliches problem. (mindestens) eine der endlich vielen möglichkeiten muss optimal sein.

sind das lösungen nur für spezielle anordnungen?
oder sind das „näherungslösungen“?
wie ist das mit exponenziell steigendem zeitbedarf?

Einfach: man kann schnell feststellen ob eine Lösung optimal
ist (such im Netz, beim TSP fällt mir gerade nicht mehr ein
wie…). Also benutzt man einen Zufallsalgo der wahrscheinlich
„gute“ Lösungen erzeugt und überprüft diese. Bei vielen Fällen
(die nicht gerade mit der Absicht den Zufallsalgo zu stören)
findet sich so sehr schnell die Lösung.

die antwort hilft mir noch nicht weiter.
wie ist das mit „nicht-polynomialen zeitbedarf“? wofür?

m.

#4

Hi,

so ganz verstehe ich Deine Frage nicht. Auf der von Dir verlinkten Seite:

link: http://www.tsp.gatech.edu/

steht doch genau, wie sie auf die Lösung gekommen sind.

sind das lösungen nur für spezielle anordnungen?
oder sind das „näherungslösungen“?

Bei speziellen Problemen kann man Heuristiken zur Problemlösung mit einbeziehen und den Algorithmus entsprechend modifizieren.
Man kann eben auch aus einer Näherungslösung eine „exakte“ Lösung berechnen.

wie ist das mit exponenziell steigendem zeitbedarf?

Kannst Du die Frage präzisieren?

oder ist es so (was ich vermute), dass es zwar deutlich
bessere verfahren als „brute force“ gibt, die aber trotzdem
exponenziell steigenden zeitbedarf haben?

Wie gesagt: Für ein bestimmtes Problem lassen sich Heuristiken zur Optimierung einsetzen. In der Regel bleibt der Zeitbedarf dennoch exponentiell.

Gruss,

Herb

#5

Moien

wie ist das mit „nicht-polynomialen zeitbedarf“? wofür?

Für NP-vollständige:

Wenn du ohne zu raten vorgehst wird dein Algo in irgendeinem Fall eine exponentielle Zeit brauchen. Es gibt keinen Algo der immer ein Ergebnis in poly. Zeit liefert.

Wenn du mit Raten anfängst KANN dein Algo wesentlich schneller sein. Muss aber nicht. In der Praxis baut man sich halt Fälle in denen das Raten möglichst erfolgreich ist …

Wenn dein Problem in P liegt (und damit auch in NP, aber nicht NP-vollständig ist):

Es gibt einen Algo der ohne zu raten immer, wirklich immer und bei jeden Werten eine Lösung in poly. Zeit findet.

cu

1 Like
#6

oder ist es so (was ich vermute), dass es zwar deutlich
bessere verfahren als „brute force“ gibt, die aber trotzdem
exponenziell steigenden zeitbedarf haben?

Ja, so ist es. Man geht von der Formulierung des Problems als ganzzahliges lineares Programm aus und bemüht sich dann um gute Algorithmen, die das Problem lösen können. Angefangen mit Schnittebenenverfahren über Branch&Bound, kombiniert mit guten Heuristiken, um schnell gute obere Schranken zu bekommen, Lagrange Relaxation für gute untere Schranken usw… googlen nach den genannten Begriffen sollte dich weiterbringen.

Nichtsdestotrotz sind das keine Algorithmen, die das Problem optimal in Polynomialzeit lösen.