Nochmal der traveller

Wissenschaft Informatik
#1

Hallo,

ich kapiers einfach nicht.

In einem Beitrag der „Spektrum der Wissenschaft“ wurde vor einiger Zeit (Exemplar in der Bibliothek gerade nicht einsehbar :wink: ) 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.

#2

In einem Beitrag der „Spektrum der Wissenschaft“ wurde vor
einiger Zeit (Exemplar in der Bibliothek gerade nicht
einsehbar :wink: ) 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