Näherungsverfahren
Mit Köpfchen statt dem Holzhammer
Bisher haben wir den kürzesten Rundweg mit der Holzhammer-Methode
bestimmt, indem
wir alle möglichen Rundreisen erzeugt und bei der Bestimmung der kürzesten Rundreise berücksichtigt haben.
Dabei wird eine riesige Anzahl an Möglichkeiten durchgespielt, die sicher nicht zu einer optimalen Rundreise
führen. So ist es bei 27 Haupstädten sicher nicht sinnvoll, eine Rundreise von Berlin aus über
Rom, Stockholm und London zu beginnen. Der gesunde Menschenverstand sagt einem direkt, dass solche
Zickzackrouten
nicht zu einer kurzen Rundreise führen.
Aufgabe 1
Überlege dir eine Strategie, wie man mit Köpfchen
bei der Suche nach der kürzesten Rundreise
vorgehen könnte.
Zum am nächst liegenden Knoten
Eine naheliegende Strategie besteht darin, vom jeweils aktuellen Knoten zum am nächst liegenden Knoten zu gehen.
Vom Startknoten Berlin aus führt diese Route zunächst nach Prag, Wien, Bratislava, Budapest, Ljubljana usw..
Aufgabe 2
Die Abbildung zeigt die Route, die nach der Strategie zum am nächst liegenden Knoten
berechnet wurde. Versuche, die Route / Strategie zu bewerten: Gibt es kürzere Routen?
Welche Nachteile hat die Strategie?
Integration der am weitesten entfernten Knoten
Eine andere Strategie versucht, jeweils die am weitesten entfernten Knoten intelligent
in die
aktuelle Rundreise zu integrieren. Diese Strategie wird im Folgenden am Beispiel erläutert.
Die Rundreise über 27 Hauptstädte der EU beginnt und endet in Berlin.
In einem ersten Schritt wird die Stadt gesucht, die am weitesten von Berlin entfernt ist. Im vorliegenden Fall ist es die Hauptstadt Nikosia von Zypern. Das Rundreisegerüst besteht jetzt aus Berlin - Nikosia - Berlin.
In einem nächsten Schritt wird die Stadt gesucht, die zu den Knoten des aktuellen Rundreisegerüsts den größten Abstand hat. Im vorliegenden Fall ist es die Hauptstadt Lissabon von Portugal. Diese Stadt wird jetzt so in das Rundreisengerüst eingebaut, dass das neue Rundreisegerüst eine möglichst geringe Länge hat. Es ergibt sich Berlin - Nikosia - Lissabon - Berlin.
Genauso verfahren wir jetzt in jedem Schritt: Es wird die Stadt gesucht, die zu den Knoten des aktuellen Rundreisegerüsts den größten Abstand hat. Im vorliegenden Fall ist es Valetta, die die Hauptstadt von Malta. Diese Stadt wird jetzt so in das Rundreisengerüst eingebaut, dass das neue Rundreisegerüst eine möglichst geringe Länge hat. Es ergibt sich Berlin - Nikosia - Valetta - Lissabon - Berlin.
Noch ein Schritt soll hier verdeutlicht werden: Es wird die Stadt gesucht, die zu den Knoten des aktuellen Rundreisegerüsts den größten Abstand hat. Im vorliegenden Fall ist es Dublin, die die Hauptstadt von Irland. Diese Stadt wird jetzt so in das Rundreisengerüst eingebaut, dass das neue Rundreisegerüst eine möglichst geringe Länge hat. Es ergibt sich Berlin - Nikosia - Valetta - Lissabon - Dublin - Berlin.
Wenn man auf diese Weise weiterverfährt, ergibt sich insgesamt die folgende Rundreise:
Vom Startknoten Berlin aus führt diese Route über Kopenhagen, Stockholm, Helsinki, Tallinn, Riga, Wilna, Warschau, Budapest, Sofia, Bukarest, Nikosia, Athen, Valetta, Rom, Madrid, Lissabon, Dublin, London, Den Haag, Brüssel, Paris, Luxemburg, Ljubljana, Bratislava, Wien, Prag wieder nach Berlin.
Aufgabe 3
Vergleiche das Ergebnis der Stategie Integration der am weitesten entfernten Knoten
mit dem Ergebnis der Strategie zum am nächst liegenden Knoten
.
Kann man mit Sicherheit behaupten, dass die Strategie Integration der am weitesten entfernten Knoten
die kürzeste Rundreise liefert?
Näherungslösungen statt exakter Lösungen
Bei 27 Hauptstädten ist es unmöglich, die exakte Lösung nach der Holzhammer-Methode
in
der zur Verfügung stehenden Zeit zu bestimmen.
In vertretbarem Aufwand (mehrere Stunden) geht das noch bei 12 Hauptstädten. Hier ist dann ein Vergleich
der exakten Lösung mit Näherungslösungen möglich.
Zunächst das Ergebnis, das nach der Strategie zum am nächst liegenden Knoten
ermittelt wurde:
Mit der Strategie Integration der am weitesten entfernten Knoten
erhält man das folgende Ergebnis:
Mit der Holzhammer-Methode
erhält man schließlich folgendes Ergebnis:
Aufgabe 4
Vergleiche die Längen der jeweiligen Routen (siehe Abbildungen). Beurteile auf Grund der gezeigten Ergebnisse die Brauchbarkeit von Näherungslösungen.
Quellen
Karte: Positionskarte Europa - Urheber: Alexrk2 - Lizenz: CreativeCommons by-sa-3.0