Vorlesung Algorithmen, Daten und Programme II, SS 98
Programmierung elementarer Algorithmen
Aufgabe 1
"Abwasserentsorgung"
Die ersten 20000 Siedler haben ihre Häuser in den Siedlungsebenen
Alpha, Beta und Gamma errichtet, ohne dass konkrete Planungen zur Abwasserentsorgung
von den Behörden erstellt wurden (auch in diesem Jahrtausend mahlen
die Mühlen langsam). Bevor der Planet Erde2 nun zur Kloake wird, soll
Ihre Firma dieses Problem für die derzeitigen und zukünftig zu
besiedelnden Ebenen des Planeten lösen; denn auch bei der Erschließung
neuer Wohnflächen werden die Pioniere zunächst planlos ihre Häuser
aufstellen. Natürlich sollen die Kosten minimal gehalten werden.
Schreiben Sie ein Programm, welches ausgehend von den bekannten Entfernungen
zwischen einzelnen Häusern ein Kanalsystem entwirft, das eine minimale
Länge aufweist und alle Häuser an die Abwasserentsorgung anschließt.
In jeder Ebene soll eine geruchsfreie Kläranlage/Sammelstelle eingerichtet
werden. Hierzu wird eines der Siedlerhäuser umgebaut. Ermitteln Sie
den jeweils günstigsten Standort.
Beispiel für eine Siedlungsebene:
von Hausnr
zu Hausnr:
Entfernung
1
2
20
1
3
23
1
4
1
2
4
4
2
5
15
3
4
36
3
6
28
4
5
9
4
7
16
4
6
25
5
7
3
6
7
17
Stichworte: Minimaler Spannbaum, Greedy-Algorithmen
Literatur: Duden Informatik, Ottmann/Widmayer S. 402ff, Güting
S. 170ff
