inf-schule | Rundreisen in Graphen » Implementierung des Lösungsalgorithmus

Implementierung des Lösungsalgorithmus

Die benutzte Klasse zur Verwaltung von Graphen

Die Implementierung benutzt die Klasse GraphMitDaten.

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).