Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 16.05.2006
Norbert Heidenbluth Blatt 4


Uni Logo



Allgemeine Informatik II (SS 2006)
für
(Wirtschafts-)Mathematiker/Physiker und E-Techniker



Abgabetermin: 01. Juni 2006

Auch in diesem Übungsblatt widmen wir uns erneut dem Thema Algorithmen. Nachdem wir bisher die ``Divide-And-Conquer''-Algorithmen kennengelernt haben, beschäftigen wir uns auf diesem Übungsblatt mit der sogenannten ``Dynamischen Programmierung'' - einem Paradigma zum algorithmischen Lösen von Optimierungsproblemen wie zum Beispiel jenem auf diesem Blatt. Ähnlich wie beim Divide-And-Conquer-Prinzip setzen wir die gesuchte (optimale) Lösung aus (optimalen) Lösungen kleinerer Probleme zusammen. Der wesentliche Unterschied ist aber, daß ``teure'' Rekursionen vermieden und stattdessen die Zwischenergebnisse in einer Tabelle gespeichert werden.

Aufgabe 8: Ein Schwabe im Rheinland (20 Punkte)

Da wir in unseren Übungsblättern schon lange keine primitiven Klischees mehr bedient haben, holen wir das in dieser Woche mal nach und beschäftigen uns mit Schwaben, Düsseldorfern und Kölnern.

Konkrekt schicken wir einen Schwaben auf einen Bummel ins Rheinland. Für Ortsunkundige sei erwähnt, daß man es dort mit einem speziellen Problem der ``Parallelgesellschaften'' zu tun hat: neben den Düsseldorfern gibt es auch noch die Kölner! Jedenfalls möchte unser Schwabe unbedingt sechs verschiedenen Aktivitäten bzw. Unternehmungen in einer vorgegebenen Reihenfolge im Rheinland nachgehen.

Weil Düsseldorf Landeshauptstadt, Medienhauptstadt, kreative Ader des Rheinlands und in jeder Hinsicht eine Reise wert ist, gibt es eigentlich keinen Grund, nach Köln zu fahren. Andererseits ist der Schwabe an sich ja immer auf Sparsamkeit bedacht und hat deshalb vor Beginn seiner Reise intensive Preisvergleiche angestellt. Und siehe da: Manche der geplanten Aktivitäten sind in Düsseldorf preisgünstiger, andere in Köln1. Andererseits fallen bei einer Rheinüberquerung auch Kosten für die Fähre an. Außerdem sind noch die Taxikosten vom Hotel in die Stadt bzw. zurück unterschiedlich. Damit setzt sich der Gesamtpreis seiner Tour, der natürlich möglichst gering sein soll, aus den folgenden Bestandteilen zusammen:

  1. Fahrtkosten vom Hotel zur ersten Station (Stadtrundfahrt)
  2. Preise für die jeweiligen Aktivitäten
  3. eventuell: Kosten für die Rheinüberquerung nach einer Aktivität
  4. Fahrtkosten für die Rückfahrt ins Hotel nach der letzten Station (Absacker trinken)

Tabelle 1 zeigt die Eintrittspreise für die gewünschten Aktivitäten in jeder der beiden Städte.


Tabelle: Preise für Aktivitäten $A_n$
Stadtrundfahrt ($A_1$) Museumsbesuch ($A_2$) Imbiß ($A_3$)
Düsseldorf 7 9 3
Köln 8 5 6
Andenken kaufen ($A_4$) Opernbesuch ($A_5$) Absacker trinken ($A_6$)
Düsseldorf 4 8 4
Köln 4 5 7

Nach jeder ausgeführten Aktivität gilt: Falls der Wechsel von Düsseldorf nach Köln (oder umgekehrt) für die folgende Aktivität gewünscht ist, fallen Fährkosten über den Rhein an. Diese gibt Tabelle 2 an.


Tabelle: Preise für Rheinfähre nach Aktivität $A_n$
$A_1$ $A_2$ $A_3$ $A_4$ $A_5$
Düsseldorf 2 3 1 3 4
Köln 2 1 2 2 1

Dann bleiben noch die Fahrtkosten vom Hotel zur ersten Station bzw. von der letzten Station zurück zum Hotel. Diese sind in Tabelle 3 zusammengefasst:


Tabelle: Preise für den Hoteltransfer
Transfer Hotel $\rightarrow A_1$ Transfer $A_6 \rightarrow$ Hotel
Düsseldorf 2 3
Köln 4 2

Gerade in den Wochen, als ihm die Informatik-Übungsblätter zum Thema Algorithmen zu schwer erschienen, hat unser Schwabe die Vorlesung und Übungen nicht mehr besucht. Tja, und so steht er nun mächtig auf dem Schlauch, wie er denn wohl die preisgünstigste Route bestimmen soll.

Glücklicherweise sind Sie ja noch aktiv bei Vorlesung und Übung dabei und können unserem armen Schwaben nun helfen, die preisgünstigste Route zu berechnen.

Teil a -- 12 Punkte

Schreiben Sie ein Java-Programm, das aus den gegebenen Informationen die optimale (also preisgünstigste Tour) berechnet. Die Reihenfolge der Aktivitäten muß dabei der angegebenen entsprechen, und jede Aktivität muß genau einmal durchgeführt werden. Desweiteren muß der verwendete Algorithmus dem Paradigma des ``Dynamischen Programmierens'' genügen!

Für diese Aufgabe brauchen die Daten noch nicht zur Laufzeit eingelesen werden. Hier steht der Algorithmus im Vordergrund, so daß Sie die Daten ausnahmsweise auch ``hart codieren'' dürfen.

Teil b -- 8 Punkte

Ändern Sie Ihr Programm (sofern nicht ohnehin schon geschehen) dahingehend, daß es die Daten nun doch dynamisch einliest. Lagern Sie die Einleseoperationen nach Möglichkeit (sinnvolle) in eine eigene Klasse aus.

Hinweis:

Für diese Teilaufgabe wird es nicht ``die eine'' richtige Lösung geben, sondern viele Möglichkeiten, die sich letztlich im ``Design'' unterscheiden. Lassen Sie sich also nicht entmutigen, wenn Ihre Lösung völlig anders ausschaut, als Lösungen anderer Gruppen.

Beispiel

Eine Möglichkeit, wie Teilaufgabe b) aussehen könnte ist die Folgende:

theseus$ cat eingabeDaten
6             // Anzahl der Aktivitaeten
7 9 3 4 8 4   // Kosten der Aktivitaeten in D'dorf
2 3 1 3 4     // Faehrkosten D'dorf-Koeln
2             // Transfer Hotel -> 1. Station D'dorf
3             // Transfer letzte Station -> Hotel D'dorf
8 5 6 4 5 7   // Analog fuer Koelner Daten
2 1 2 2 1
4
2

java Tour < eingabeDaten
Der Tourplaner fuer preisbewusste Schwaben empfiehlt:
Mache Standrundfahrt in Duesseldorf.
Mache Museumsbesuch in Koeln.
[...]   // usw.

Hinweise

Sensationelle Skizze zur Aufgabe:

\resizebox{!}{12.5cm}{\includegraphics{skizze.eps}}

Viel Spaß!



Fußnoten

... Köln1
bei unterstellter ``gleicher Art und Güte''!


Norbert Heidenbluth 2006-05-16