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.
Quellen
Karte: Positionskarte Europa - Urheber: Alexrk2 - Lizenz: CreativeCommons by-sa-3.0