Aufgabe 1
"Abwasserentsorgung"
Erste Überlegungen zur Lösung
Die Ausgangssituation kann als Baumgraph aufgefasst werden, wobei die einzelnen Häuser
als Knoten und die Entfernungen zwischen ihnen als Kanten dargestellt sind. Nun muss dieser
Graph, es handelt sich hierbei um einen Spannbaum, von überflüssigen Kanten zu "säubern".
Dazu werden alle Zyklen innerhalb des Graphen entfernt. Desweiteren wird der Graph so
konstruiert, daß immer zuerst die kleinste Kante gezeichnet wird und dann aufsteigend alle
anderen. Diese Methode nennt man Greedy-Algorithmus . Der Graph wird in unserem
Programm in ML als Liste von Elementen geführt.
Dieser minimale Graph enthält nun alle Kanten bzw. Wege von Haus zu Haus. Jetzt muss
eine Möglichkeit gefunden werden, um den zentralsten Punkt dieses Graphen zu finden. Der
zentrale Punkt, der gesucht wird, in diesem Fall eins der Häuser der Kolonie, ist ein Knoten
in unserem Graphen. Dort wird die Kläranlage errichtet.
Aufteilung der Aufgaben und allgemeine Algorithmenerklärung
Dirk Bussler und Thomas Neumann arbeiten an dem Programmstück, welches die
Ausgangsliste nach dem kleinsten Weg, hier der kleinsten Kante des Graphen, durchsucht
und diesen in eine neue Liste legt. Dieses Element wird aus der Ausgangsliste gelöscht. Die
neue Liste wird zum Test ob ein Zyklus in ihr enthalten ist, zum Programm stück von Daniel
Stebner übergeben. Dort wird jedes einzelne Element der Liste auf sich wiederholende
Kanten getestet.
Dabei wird jeder Weg verfolgt.
zB.: Von Knoten 1 führt ein Weg nach Knoten 2 und nach Knoten 3.
Von Knoten 2 führt ein Weg nach Knoten 3.
Aber von Knoten 3 führt ein Weg nach Knoten 4 und ein Weg nach Knoten 1. Da Knoten 1
bereits bearbeitet wurde existiert ein Zyklus, eine Schleife.
Dieser Zyklus wird entfernt, indem man eine Kante entfernt, je nachdem welche am
kostengünstigsten ist.
Die Liste von Dirk und Thomas wird nach diesem Prinzip komplett getestet. Sind alle Zyklen
entfernt und ist die Ausgangsliste leer, so wird diese nun sortierte und geprüfte Liste an
Kay`s Programm übergeben.
Seine Aufgabe ist das Finden des zentralsten Knoten, hier also den zentralen Punkt der
Kolonie, welches ein Haus ist. Dieses Haus wird aus seiner idyllischen Umgebung
herausgerissen und kurzerhand kostengünstig in eine Kläranlage verwandelt. Die Suche
danach beginnt bei den Blättern des Graphen. Nicht in Frage als dieser Punkt kommen
natürlich die äusseren Blätter, sie sind zuweit von Zentrum entfernt. Nun wird von den
restlichen Knoten alle Wege zu einem Blatt ermittelt. Und aus dieser Liste der Strecken wird
wiederum die kürzeste Strecke ausgewählt. Diese Strecke bzw. der Ursprungsprungsknoten
dieser Strecke ist das gesuchte Ziel.
Wir diskutierten zu Beginn der Programmierarbeit welche Algorithmen wir nutzen sollten.
Dabei wurde auch der Greedy-Algorithmus angesprochen und wir waren der Meinung das
diese Methode wohl die Beste zur Lösung unseres Ausgangsproblems ist.
Bevor ich nun zur genaueren Beschreibung des eigendlichen Programms komme, möchte ich
noch einige Worte zur Anwendung sagen.
Benutzung des Programms
Um in den Genuss dieses Programms zu kommen, muss Version 0.93 des New Jersey
Standart ML vorliegen. Das Programm selbst heißt "shortway". Zu finden ist es unter:
http://www.didaktik.cs.uni-potsdam.de/lehre/adp2/projekttage/tag1/
Um es zu starten, kopieren Sie es in Ihr Homeverzeichnis und starten Sie ML.
Läuft ML, kann das Programmmit der Eingabe von use"shortway"; wird es eingeladen und
von ML kompiliert. Treten keine Fehlermeldungen auf ist alles ok. Bevor Sie jedoch dieses
Programm starten, sollten Sie den Ausgangsgraphen
als Konstante definieren, diese Konstante wird vom Programm benötigt.
Am besten ist es wenn man sich den Graphen aufzeichnet und alle Knoten durchnummeriert
und die Weglängen zwischen ihnen festlegt.
Die Festlegung der Eingabe erfolgt so:
-val graph=[(x,y,z),a,b,c,...];
Dabei stellt x die Nummer des einen Knotens und y die des anderen dar. z ist die Weglänge
zwischen x und y.
Simultan gilt es für a,b und c usw. Bei der Aufstellung des Graphen und der Eingabe ist
darauf zu achten, daß jeder auftretende Weg zwischen 2 Knoten in diesem Graphen
berücksichtigt wird.
Zur Beschreibung des Programms
Wir haben uns dazu entschieden, das ML programm nicht seperat zu Dokumentieren, da es
zu verwirrend sein könnte. Wir haben den Quellcode mit sehr vielen Kommentaren versehen,
die die Funktion der einzelnen Abschnitte beschreiben. Dies ist besser als Dokumentation und
Programm seperat vorzuliegen zu haben.
Abschlussbemerkung
Leider war es uns nicht möglich die Programmierung bis zum Abgabetermin zu beenden,da
das Programm von Kay doch einige erhebliche Probleme brachte.
Bei der Programmierung des Programms wurden die Vorteile von ML in der funktionalen
Programmierung deutlich. Durch die Nutzung von Rekursivität. kann der Quellcode doch
recht verkürzt werden. In Pascal waren im Internet auch einige Beispiele zu diesen und
ähnlichen Problemen vorhanden, die zeigten, das dieses Problem auch in anderen
Programmiersprachen behandelt wurde. Der Quellcode von Pascal war gegenüber unserem
zwar etwas kürzer, wohl auch weil die Algorithmen effizienter und besser durchdacht wurden,
aber an sich währe nach unserer Methode der Pascalcode erheblich komplexer.
Dieser Projekttag zeigte doch, das wenn man von Anfang an die Aufgaben gut verteilt und
im Team arbeitet ist eine Lösung zu vereinbartem Abgabetermin möglich. Unser Fehler war
es, daß wir uns zu Beginn zu viel Zeit vergeudet haben indem wir teilweise aneinander
vorbeidiskutiert haben und uns etwas zu sehr auf unsere eigenen Theorien versteiften.
Thomas Fromm
Anhang:
-Aufgabenstellung
-Quellcode
-Dokumentation
