Rundreiseproblem für große Werte

05/06/2008 - 23:46 von Jan Fricke | Report spam
Hallo!
Heute gab es hier einen sehr interessanten Vortrag von Prof. Dr. Peter
Gritzmann, "Über U-Bahn-Fahren, Schiffe versenken und heiße Laptops:
Mathematische Probleme im Alltag". Unter anderem wurde das
Rundreiseproblem angesprochen und dafür Beispiele gezeigt. Dabei war die
Anzahl der Knoten in der Größenordnung von 700 (wenn ich mich recht
erinnere), und es wurde von einem Weg behauptet, dass er der kürzeste
sei. Wie kann man so etwas nachweisen? Die Orte hatten eine recht
zufàllige geometrische Struktur, das kann also nichts mit dem speziellen
Beispiel zu tun haben.


Viele Grüße Jan
 

Lesen sie die antworten

#1 Alexander Streltsov
06/06/2008 - 00:15 | Warnen spam
Jan Fricke schrieb:
Hallo!
Heute gab es hier einen sehr interessanten Vortrag von Prof. Dr. Peter
Gritzmann, "Über U-Bahn-Fahren, Schiffe versenken und heiße Laptops:
Mathematische Probleme im Alltag". Unter anderem wurde das
Rundreiseproblem angesprochen und dafür Beispiele gezeigt. Dabei war die
Anzahl der Knoten in der Größenordnung von 700 (wenn ich mich recht
erinnere), und es wurde von einem Weg behauptet, dass er der kürzeste
sei. Wie kann man so etwas nachweisen? Die Orte hatten eine recht
zufàllige geometrische Struktur, das kann also nichts mit dem speziellen
Beispiel zu tun haben.


Viele Grüße Jan



Das Problem ist als Travelling Salesman Problem bekannt.
Man kann trivial eine kürzeste Rundreise erhalten indem man alle
möglichen Rundreisen betrachtet und ihre Lànge ausrechnet. Von diesen
gibt es (n-1)!/2, wenn n die Anzahl der Stàdte ist und jede Stadt mit
jeder Verbunden ist. Allerdings ist dieses triviale Verfahren bei großer
Stàdtezahl unbrauchbar. Man verwendet vor allem Nàherungsverfahren.

Ähnliche fragen