Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


42. Dynamische Programmierung



Übungen

  1. In dem für das Rucksack-Problem angegebenen Beispiel sind die Gegenstände ihrer Größe nach sortiert. Führt der Algorithmus auch dann noch zum Ziel, wenn sie in beliebiger Reihenfolge angeordnet sind?
  2. Modifizieren Sie das Programm für das Rucksack-Problem dahingehend, daß eine weitere Nebenbedingung berücksichtigt wird, die durch ein Feld num[1..N] definiert ist, das die Anzahl der von jedem Typ verfügbaren Gegenstände enthält.
  3. Was würde das Programm für das Rucksack-Problem liefern, wenn einer der Werte negativ wäre?
  4. Ist folgende Aussage wahr oder falsch: Wenn bei einer Multiplikation mehrerer Matrizen eine Multiplikation einer Matrix der Dimension 1 x k mit einer Matrix der Dimension k x 1 auftritt, so existiert eine optimale Lösung, für die diese Multiplikation die letzte ist. Begründen Sie Ihre Antwort.
  5. Erstellen Sie ein Programm, das die Multiplikation einer Reihe von N Matrizen in optimaler Weise ausführt. Setzen Sie voraus, daß die Matrizen in einem dreidimensionalen Feld matrices[1..Nmax, 1..Dmax, 1..Dmax] gespeichert sind, wobei Dmax die maximale Dimension ist und die i-te Matrix in matrices[i, 1..r[i], 1..r[i+1]] gespeichert ist.
  6. Skizzieren Sie den optimalen Suchbaum für das Beispiel aus dem vorliegenden Kapitel, wobei jedoch alle Häufigkeiten um eins erhöht seien.
  7. Erstellen Sie das Programm für die Erzeugung des optimalen binären Suchbaums.
  8. Angenommen, für eine gewisse Menge von Schlüsseln und Häufigkeiten wurde der optimale binäre Suchbaum berechnet, und eine Häufigkeit wurde um eins erhöht. Erstellen Sie ein Programm zur Berechnung des neuen optimalen Baums.
  9. Warum kann das Rucksack-Problem nicht in der gleichen Weise gelöst werden wie die Probleme der Multiplikation mehrerer Matrizen und des optimalen binären Suchbaums: durch Minimieren der Summe aus dem besten erreichbaren Wert für einen Rucksack der Größe k und dem besten erreichbaren Wert für einen Rucksack der Größe M - k über k von 1 bis M?
  10. Erweitern Sie das Programm für das Problem der kürzesten Pfade dahingehend, daß eine Prozedur paths(i,j: integer) eingefügt wird, die ein Feld path mit dem kürzesten Pfad von i nach j belegt. Diese Prozedur sollte jedesmal, wenn sie aufgerufen wird, eine der Länge des Pfades proportionale Zeit erfordern, wobei eine Hilfs-Datenstruktur benutzt wird, die mit Hilfe einer modifizierten Variante des in Kapitel 32 angegebenen Programms erzeugt wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]