Implementierung des Lösungsalgorithmus
Die benutzte Klasse zur Verwaltung von Graphen
Die Implementierung benutzt die Klasse GraphMitDaten
.
(siehe graph.txt)
Erzeugung von Permutationen
Zur Erzeugung aller möglichen Rundreisen benutzen wir eine Funktion naechste_permutation
, die systematisch
neue Reihenfolgen der zu besuchenden Städte erzeugt.
def naechste_permutation(L):
# bestimme den maximalen Index i mit L[i] < L[i+1]
i = len(L)-2
gefunden = False
while not gefunden:
if i < 0:
gefunden = True
else:
if L[i] < L[i+1]:
gefunden = True
else:
i = i-1
if i >= 0:
# bestimme den maximalen Index j mit L[j] > L[i]
j = i+1
m = j
while j < len(L)-1:
j = j+1
if L[j] > L[i]:
m = j
j = m
# vertausche L[i] und L[j]
h = L[i]
L[i] = L[j]
L[j] = h
# kehre die Restliste ab Position i+1 um
i = i+1
j = len(L)-1
while i < j:
h = L[i]
L[i] = L[j]
L[j] = h
i = i+1
j = j-1
else:
# Liste ist absteigend sortiert
# kehre Liste um
i = 0
j = len(L)-1
while i < j:
h = L[i]
L[i] = L[j]
L[j] = h
i = i+1
j = j-1
return L
Aufgabe 1
Teste die Funktion naechste_permutation
durch Funktionsaufrufe wie die folgenden:
>>> naechste_permutation(['A', 'B', 'C', 'D', 'E'])
['A', 'B', 'C', 'E', 'D']
>>> naechste_permutation(['A', 'B', 'C', 'E', 'D'])
['A', 'B', 'D', 'C', 'E']
Aufgabe 2
Entwickle ein Testprogramm, mit dem man ermitteln kann, wie viele verschiedene Permutationen bei einer Liste mit 5 verschiedenen Elementen (Städten) möglich sind.
Suche nach der kürzesten Rundreise
Mit Hilfe der Funktion naechste_permutation
lässt sich die Erzeugung und Verarbeitung der
Rundreisen wie folgt implementieren.
from graph import *
def naechste_permutation(L):
# siehe oben
def laenge(g, rundreise):
weglaenge = 0
anzahlKnoten = len(rundreise)
i = 1
while i < anzahlKnoten:
weglaenge = weglaenge + float(g.getGewichtKante(rundreise[i-1], rundreise[i]))
i = i+1
return weglaenge
def minRundreise(g, startKnoten):
startRouteOhneStartKnoten = []
for knoten in g.getAlleKnoten():
if knoten != startKnoten:
startRouteOhneStartKnoten = startRouteOhneStartKnoten + [knoten]
startRoute = [startKnoten] + startRouteOhneStartKnoten + [startKnoten]
routeOhneStartKnoten = startRouteOhneStartKnoten[:]
route = startRoute
minLaenge = laenge(g, route)
minRoute = route
endePermutationen = False
while not endePermutationen:
routeOhneStartKnoten = naechste_permutation(routeOhneStartKnoten)
route = [startKnoten] + routeOhneStartKnoten + [startKnoten]
if laenge(g, route) < minLaenge:
minLaenge = laenge(g, route)
minRoute = route
endePermutationen = (routeOhneStartKnoten == startRouteOhneStartKnoten)
return (minRoute, minLaenge)
# Erzeugung des Graph-Objekts
g = GraphMitDaten()
# Erzeugung der Knoten und Kanten aus einer GraphML-Datei
datei = open("graph_eu_6.xml", "r")
xml_quelltext = datei.read()
g.graphmlToGraph(xml_quelltext)
# Test des Rundreise-Algorithmus
(minRoute, minLaenge) = minRundreise(g, 'Bonn')
print('Route:', minRoute)
print('Länge:', minLaenge)
Zum Testen benötigst du noch die Datei graph_eu_6.xml
Aufgabe 3
Führe das Testprogramm aus. Ändere es auch wie folgt ab: Es sollen alle erzeugten Routen mit ihren Längen ausgegeben werden. Es soll zusätzlich mitgezählt werden, wie viele Routen erzeugt werden (zur Kontrolle: 120).