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.
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:
Tabelle 1 zeigt die Eintrittspreise für die gewünschten Aktivitäten in jeder der beiden Städte.
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.
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:
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.
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.
Ä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.
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.
Viel Spaß!