Implementierung der Näherungsverfahren

Die benutzte Klasse zur Verwaltung von Graphen

Die Implementierung benutzt die Klasse GraphMitDaten (siehe graph.txt)

Strategie: Zum am nächst liegenden Knoten

Ein mögliches Näherungsverfahren beruht auf der Strategie, vom jeweils aktuellen Knoten zum am nächst liegenden Knoten zu gehen. Ein Algorithmus zu diesem Verfahren könnte wie folgt aussehen:

ALGORITHMUS rundreiseNaeherung1(g, startKnoten):
    füge startKnoten in eine Liste route ein
    füge alle Knoten des Graphen außer startKnoten in eine Liste knotenRestListe ein
    SOLANGE die Liste knotenRestListe nicht leer ist:
        bestimme den letzten Knoten in route und verwalte ihn mit aktuellerKnoten
        bestimme minKnoten so, 
        dass die Kante von aktuellerKnoten zu minKnoten
        minimales Gewicht hat
        füge minKnoten am Ende der Liste route ein
        entferne minKnoten aus der Liste knotenRestListe
    füge startKnoten am Ende der Liste route ein
    bestimme die Länge der route und verwalte sie mit laengeRoute
    Rückgabe: (route, laengeRoute)

Aufgabe 1

Implementiere die Funktion rundreiseNaeherung1(g, startKnoten).

Zum Testen kannst du die Daten der EU-Hauptstädte in den folgenden Dateien benutzen: graph_eu_6.xml, graph_eu_9.xml, graph_eu_12.xml, graph_eu_15.xml, graph_eu_25.xml, graph_eu_27.xml. Beachte, dass die Hauptstadt der BRD in der 6-, 9- und 12er-Gemeinschaften Bonn und dass die Hauptstadt in der 15-, 25- und 27er-Gemeinschaften Berlin ist.

Strategie: Integration der am weitesten entfernten Knoten

Die Stategie Integration der am weitesten entfernten Knoten beruht auf der folgenden Idee: Es wird jeweils die Stadt gesucht, die zu den Knoten des aktuellen Rundreisegerüsts den größten Abstand hat. Diese Stadt wird jetzt so in das Rundreisengerüst eingebaut, dass das neue Rundreisegerüst eine möglichst geringe Länge hat. Ein Algorithmus zu diesem Verfahren könnte wie folgt aussehen:

ALGORITHMUS rundreiseNaeherung2(g, startKnoten):
    rundreisegeruest = [startKnoten, startKnoten]
    laenge = 0
    füge alle Knoten des Graphen außer startKnoten in eine Liste knotenRestListe ein
    SOLANGE die Liste knotenRestListe nicht leer ist:
        bestimme maxKnoten aus der Liste knotenRestListe so,
        dass der Abstand zu rundreisegerust 
        (d.h. dass der gringste Abstand zu einem Knoten aus rundreisegeruest)
        maximal ist
        füge maxKnoten so in die Liste rundreisegeruest ein,
        dass das neue rundreisegeruest eine minimale Länge hat
        entferne maxKnoten aus der Liste knotenRestListe
    route = rundreisegeruest
    bestimme die Länge der route und verwalte sie mit laengeRoute
    Rückgabe: (route, laengeRoute)

Aufgabe 2

Implementiere die Funktion rundreiseNaeherung2(g, startKnoten).

Zum Testen kannst du die Daten der EU-Hauptstädte in den folgenden Dateien benutzen: graph_eu_6.xml, graph_eu_9.xml, graph_eu_12.xml, graph_eu_15.xml, graph_eu_25.xml, graph_eu_27.xml. Beachte, dass die Hauptstadt der BRD in der 6-, 9- und 12er-Gemeinschaften Bonn und dass die Hauptstadt in der 15-, 25- und 27er-Gemeinschaften Berlin ist.

Experimente

Eine Implementierung der beiden Verfahren findest du in implementierungnaeherungsverfahren.zip.

Aufgabe 3

Teste die Implementierung. Du kannst verschiedene EU-Hautstadtdateien auswerten lassen. Beachte, dass die Hauptstadt der BRD in der 6-, 9- und 12er-Gemeinschaften Bonn und dass die Hauptstadt in der 15-, 25- und 27er-Gemeinschaften Berlin ist. Beachte auch, dass die exakte Lösung nur für kleine Gemeinschaften in vertretbarer Zeit berechnet werden kann.