inf-schule | Rundreisen in Graphen » Näherungsverfahren

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.