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.