inf-schule | Rundreisen in Graphen » Anwendbarkeit des Algorithmus

Anwendbarkeit des Algorithmus

Erweiterungen der EU

Die EU (bzw. EWG bzw. EG) ist seit ihrer Gründung 1957 mehrfach erweitert worden. Zu Beginn bestand sie aus 6 Mitgliedsstaaten. Diese 6-er-Gemeinschaft ist 1973 zu einer 9-er-Gemeinschaft, 1981 bis 1986 zu einer 12-er-Gemeinschaft, 1995 zu einer 15-er-Gemeinschaft, 2004 zu einer 25-er-Gemeinschaft und 2007 zu einer 27-er-Gemeinschaft gewachsen. Weitere Staaten warten auf den baldigen Beitritt zu dieser Gemeinschaft.

Für neue Außenminister der BRD wird es mit wachsender Zahl von Mitgliedsstaaten immer schwieriger, alle Hauptstädte in vertretbarer Zeit zu besuchen.

Auch die Planung einer kürzesten Rundreise durch alle Mitgliedsstaaten führt zu Schwierigkeiten. Diese sollen im Folgenden etwas genauer untersucht werden.

Erzeugung aller möglichen Rundreisen

Mit dem Programm GUITestApp.py in simulationsprogramm.zip kann man alle möglichen Rundreisen bei einer vorgegebenen EU-Gemeinschaft systematisch erzeugen. Für die jeweilige EU-Gemeinschaft findest du die passende XML-Datei im entpackten Ordner.

Aufgabe 1

Starte das Simulationsprogramm mit einer bestimmten Anzahl von Hauptstädten (z.B. 15). Erzeuge Schritt für Schritt neue Rundreise und merke dir die kürzeste. Hast du Lust und Zeit, alle möglichen Rundreisen durchzuspielen?

Aufgabe 2

Bevor du anfängst, bei 27 (bzw. 25) Hauptstädten alle Rundreisen zu erzeugen, berechne erst einmal, wie viele das sind. Dabei kannst du folgendermaßen vorgehen:

Vom Startort Berlin aus gibt es 26 Möglichkeiten, den nächsten Ort zu wählen. Von jedem dieser 26 Orte gibt es dann noch 25 Möglichkeiten, den nächsten Ort zu wählen, usw.. (Du musst hier nicht berücksichtigen, dass jeweils zwei Rundreisen bis auf die Reihenfolge übereinstimmen).

Aufwand zur Erzeugung aller möglichen Rundreisen

Die Problemgröße wird durch die Anzahl n der Mitgliedsländer der EU (Knoten des Graphen) festgelegt. Je größer n ist, desto größer ist auch der Aufwand zur Berechnung der Problemlösung.

Als Kostenmaß für den Berechnungsaufwand wählen wir die Anzahl der zu erzeugenden und verarbeitenden Rundreisen R(n). Wir gehen dabei davon aus, dass jede zu erzeugende und verarbeitende Rundreise in etwa den gleichen Berechnungsaufwand hat.

Für R(n) kann man einen recht einfachen Berechnungsterm entwickeln:

Bei n Knoten gibt es vom Startknoten aus n-1 Möglichkeiten, den nächsten Knoten zu wählen. Von jedem dieser n-1 Knoten gibt es dann noch n-2 Möglichkeiten, den nächsten Knoten zu wählen, usw.. Insgesamt erhält man die folgende Formel:

R(n) = (n-1)*(n-2)*...*2*1

Für das Produkt (n-1)*(n-2)*...*2*1 schreibt man auch kurz (n-1)! (gelesen: n-1 Fakultät).

Aufgabe 3

Entwickle ein Testprogramm zur Berechnung von Fakultäten. Es kann z.B. folgende Ausgaben erzeugen:

0 ! = 1
1 ! = 1
2 ! = 2
3 ! = 6
4 ! = 24
5 ! = 120
6 ! = 720
7 ! = 5040
8 ! = 40320
9 ! = 362880
10 ! = 3628800
11 ! = 39916800
12 ! = 479001600
13 ! = 6227020800
14 ! = 87178291200
15 ! = 1307674368000
16 ! = 20922789888000
17 ! = 355687428096000
18 ! = 6402373705728000
19 ! = 121645100408832000
20 ! = 2432902008176640000
21 ! = 51090942171709440000
22 ! = 1124000727777607680000
23 ! = 25852016738884976640000
24 ! = 620448401733239439360000
25 ! = 15511210043330985984000000

Anwendbarkeit des Algorithmus

Kann man den Algorithmus (bzw. seine Implementierung) aus dem letzten Abschnitt zur Bestimmung der kürzesten Rundreise benutzen? Theoretisch ja, aber praktisch?

Man kann recht einfach ermitteln, wie lange ein Rechner zur Erzeugung und Verarbeitung einer Rundreise benötigt: Ergänze hierzu einen Zähler und eine Ausgabe des Zählers nach z.B. 1000 oder 10000 oder 100000 Zählschritten. Aus der grob gemessenen Zeit kann man dann die gesuchte Zeit abschätzen. Wir gehen im folgenden davon aus, dass man für 1000 Rundreisen etwa 1 Sekunde benötigt.

Aufgabe 3

Schätze mit den oben gezeigten Daten ab, wie lange es dauert, bis die kürzeste Rundreise mit dem vorliegenden Algorithmus bei 25 Knoten gefunden ist (Zur Kontrolle: Es sind etwas weniger als 20000000000000 Jahre.) Beurteile mit dem Ergebnis die praktische Anwendbarkeit des Algorithmus.