inf-schule | Rundreisen in Graphen » Ein einfacher Lösungsalgorithmus

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.