Ein einfacher Lösungsalgorithmus
Alle Rundreisen
Ein einfaches Verfahren zur Bestimmung der kürzesten Rundreise besteht darin, alle möglichen Rundreisen zu erzeugen und jeweils die Länge der Rundreise zu bestimmen. Aus den erzeugten Längenwerten lässt sich dann die optimale Route bestimmen.
Aufgabe 1
Lade den komprimierten Ordner simulationsprogramm.zip
herunter und führe das Programm GUITestApp.py
aus. Bestimme mit dem Simulationsprogramm
den kürzesten Rundweg bei den vorgegebenen Hauptstädten.
Algorithmus
Das Simulationsprogramm basiert auf dem folgenden Algorithmus:
startRouteOhneStartKnoten = Liste aller Knotennamen ohne den startKnoten
startRoute = [startKnoten] + startRouteOhneStartKnoten + [startKnoten]
routeOhneStartKnoten = Kopie von startRouteOhneStartKnoten
route = startRoute
minLaenge = Länge von route
minRoute = route
endePermutationen = False
while not endePermutationen:
routeOhneStartKnoten = naechste_permutation(routeOhneStartKnoten)
route = [startKnoten] + routeOhneStartKnoten + [startKnoten]
if self.laenge(route) < minLaenge:
minLaenge = self.laenge(route)
minRoute = route
endePermutationen = (routeOhneStartKnoten == startRouteOhneStartKnoten)
Zunächst wird eine Startroute aus den gegebenen Knotennamen erzeugt und ihre Länge bestimmt.
Anschließend wird Schritt für Schritt eine neue Route festgelegt und bei der Bestimmung der optimalen Route berücksichtigt. Herbei wird systematisch eine neue Reihenfolge (Permutation) der zu besuchenden Städte erzeugt.
Quellen
Karte: Positionskarte Europa - Urheber: Alexrk2 - Lizenz: CreativeCommons by-sa-3.0