programm lösung Punkt bibliothek Optimierung Jeep Traveller

Nochmal der traveller...

Von: , Frage gestellt am Do, 23. Nov 2000

Hallo,

ich kapiers einfach nicht.

In einem Beitrag der "Spektrum der Wissenschaft" wurde vor einiger Zeit (Exemplar in der Bibliothek gerade nicht einsehbar ;-) ) vorgestellt, wie sich mit ganz wenig Aufwand Probleme der Art des "travelling salesman" lösen lassen.

Dazu muß eine Matrik aufgestellt werden, die von jedem Punkt zu jedem Punkt die zu optimierende Größe enthält , dann wird schrittweise die ungünstigste Verbindung in jeder Zeile gestrichen, bis gerade noch ein geschlossener Graph übrigbleibt (so in der Art). Dies ist dann die optimale Verbindung aller Punkte.

Ich habe ernsthaft geglaubt, damit wäre dieses Problem nun endlich gelöst, und schon mit einer Flut von Optimierern gerechnet, die nach diesem Prinzip arbeiten. Abgesehen davon, daß der salesman überall ähnliche Optimierungsprobleme finden wird.

Das ganze scheint dann so einfach zu sein, daß es selbst mein Windows-Rechner wieder optimieren könnte...

Warum ist dies offenbar nicht der Weisheit letzter Schluß, wenn doch immer wieder neue Optimierungsprogramme vorgestellt werden und noch ganz andere Lösungsansätze diskutiert werden (die sich dann von dem hier nur kurz dargestellten Ansatz deutlich unterscheiden)? Und die von sich behaupten, die Lösung für den traveller zu sein?

Danke für jeden Tip,

Lutz.

1 Antworten zu dieser Frage

1. Antwort von nach 55 Minuten hilfreich

   Re: Nochmal der traveller...

   In einem Beitrag der "Spektrum der Wissenschaft" wurde vor
   einiger Zeit (Exemplar in der Bibliothek gerade nicht
   einsehbar ;-) ) vorgestellt, wie sich mit ganz wenig Aufwand
   Probleme der Art des "travelling salesman" lösen lassen.
   
   Dazu muß eine Matrik aufgestellt werden, die von jedem Punkt
   zu jedem Punkt die zu optimierende Größe enthält , dann wird
   schrittweise die ungünstigste Verbindung in jeder Zeile
   gestrichen, bis gerade noch ein geschlossener Graph
   übrigbleibt (so in der Art). Dies ist dann die optimale
   Verbindung aller Punkte.
   
   Ich habe ernsthaft geglaubt, damit wäre dieses Problem nun
   endlich gelöst, und schon mit einer Flut von Optimierern
   gerechnet, die nach diesem Prinzip arbeiten. Abgesehen davon,
   daß der salesman überall ähnliche Optimierungsprobleme finden
   wird.
   
   Warum ist dies offenbar nicht der Weisheit letzter Schluß,
   wenn doch immer wieder neue Optimierungsprogramme vorgestellt
   werden und noch ganz andere Lösungsansätze diskutiert werden
   (die sich dann von dem hier nur kurz dargestellten Ansatz
   deutlich unterscheiden)? Und die von sich behaupten, die
   Lösung für den traveller zu sein?
   1. Es gibt noch keinen Polynomzeit Algorithmus füe das Traveling-Salesman Problem.
   
   2. Es gibt ein voll polynomielles Approximationsschema für den euklidischen Fall (Arora)
   
   3. Heuristiken erreichen heute Abweichungen von wenigen Promille, können diese aber natürlich nicht garantieren. (s. z.B. die Steuerung des ROSAT-satelliten im Arithmeum in Bonn).
   
   4. An den Artikel kann ich mich glaube ich erinnern. Das Beispiel war, einen Jeep durch die Wüste zu steuern, wobei an jedem Knoten
   eine ausreichende Menge Treibstoff gelagert ist. Die Aufgabe ist nun zu bestimmen, wie gross der Tank von dem Jeep sein muss, damit man üebrall hinkommt. Dazu streicht man so lange die "maximalen verbleibdenden" Werte, bis nur noch ein spannender Baum uebrigbleibt.
   
   Zu dem Thema gibts haufenweise Bücher,Papers und Seiten im Netz.
   MFG
   Martin
   

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!