Robert Sedgewick: Algorithmen

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


42. Dynamische Programmierung



Das Rucksack-Problem

Ein Dieb, der einen Safe ausraubt, findet in ihm N Typen von Gegenständen unterschiedlicher Größe und unterschiedlichen Werts, hat aber nur einen kleinen Rucksack der Größe M zur Verfügung, um die Gegenstände zu tragen. Das Rucksack-Problem besteht darin, diejenige Kombination von Gegenständen zu finden, die der Dieb für seinen Rucksack auswählen sollte, so daß der Gesamtwert der von ihm geraubten Gegenstände maximal wird.

Nehmen wir zum Beispiel an, daß er einen Rucksack mit dem Fassungsvermögen 17 besitzt, und daß der Safe viele Gegenstände der in Abbildung 42.1 dargestellten Größen mit den angegebenen Werten enthält. (Wie üblich verwenden wir für die Gegenstände im Beispiel aus einem Buchstaben bestehende Bezeichnungen und ganzzahlige Indizes in den Programmen, wobei klar ist, daß kompliziertere Bezeichnungen unter Benutzung von Standard-Suchverfahren in ganze Zahlen umgewandelt werden können.) Der Dieb kann dann fünf Gegenstände A (jedoch nicht sechs) mitnehmen, so daß die gesamte Beute den Wert 20 hat, oder er kann seinen Rucksack mit einem D und einem E füllen, was einen Gesamtwert von 24 ergibt, oder er kann viele weitere Kombinationen ausprobieren. Doch für welche Kombination wird der Gesamtwert maximal?

Abbildung 42.1
Abbildung 42.1 Rucksack-Problgm.

Natürlich gibt es viele Situationen im kommerziellen Bereich, in denen eine Lösung des Rucksack-Problems von Bedeutung sein könnte. Zum Beispiel ist es für eine Reederei von Interesse, die beste Möglichkeit zu kennen, wie ein Lastkraftwagen oder ein Transportflugzeug mit Gütern für die Verschiffung beladen werden kann. Bei solchen Anwendungsfällen können auch andere Varianten dieses Problems auftreten: Es könnte zum Beispiel sein, daß von jedem Gegenstand nur eine begrenzte Anzahl vorhanden ist. Für viele solche Varianten ist der gleiche Ansatz geeignet, den wir nunmehr für die Lösung des oben beschriebenen Ausgangsproblems betrachten.

Zur Lösung des Rucksack-Problems mit Hilfe der dynamischen Programmierung berechnen wir die beste Kombination für alle Größen eines Rucksacks bis M. Es zeigt sich, daß diese Berechnung in sehr effizienter Weise realisiert werden kann, indem die Operationen in einer zweckmäßigen Reihenfolge ausgeführt werden:

    for j:=1 to N do
      begin
      for i:=1 to M do
        if i-size[j]>=0 then
          if cost[i]<(cost[i-size[j]]+val[j]) then
            begin
            cost[i]:=cost[i-size[j]]+val[j];
            best[i]:=j
            end;
      end;

In diesem Programm ist cost[i] der größte Wert, der mit einem Rucksack mit dem Fassungsvermögen i erzielt werden kann, und best[i] ist das letzte Element, das hinzugefügt wurde, um dieses Maximum zu realisieren (wie weiter unten beschrieben wird, wird dieses Element verwendet, um den Inhalt des Rucksacks nachträglich zu bestimmen). Zuerst berechnen wir für alle Größen des Rucksacks den maximalen Wert, wenn nur Elemente vom Typ A verwendet werden, danach berechnen wir den maximalen Wert, wenn nur Elemente A und B verwendet werden, usw. Die Lösung reduziert sich auf eine einfache Berechnung von cost[i]. Nehmen wir an, daß ein Element j für den Rucksack gewählt wird; dann wäre der beste Gesamtwert, der erzielt werden könnte, val[j] (für das Element) plus cost[i - size[j]] (um den Rest des Rucksacks aufzufüllen). Wenn dieser Wert den besten Wert übersteigt, der ohne ein Element j erreicht werden kann, aktualisieren wir cost[i] und best[i]; andernfalls lassen wir diese Größen unverändert. Ein einfacher Beweis mittels Induktion zeigt, daß das Problem mit dieser Strategie gelöst werden kann.

In Abbildung 42.2 ist die Berechnung für unser Beispiel dargestellt. Das erste Zeilenpaar zeigt den maximalen Wert (den Inhalt der Felder cost und best), wenn nur Elemente A benutzt werden; das zweite Zeilenpaar zeigt den maximalen Wert, wenn nur Elemente A und B verwendet werden, usw. Der höchste Wert, der mit einem Rucksack der Größe 17 erreicht werden kann, ist 24. Im Verlaufe der Berechnung dieses Ergebnisses haben wir auch viele kleinere Teilprobleme gelöst. Zum Beispiel ist der größte Wert, der mit einem Rucksack der Größe 16 erreicht werden kann, 22, wenn nur Elemente A, B und C verwendet werden.

Abbildung 42.2
Abbildung 42.2 Lösung des Rucksack-Problems.

Der tatsächliche Inhalt des optimalen Rucksacks kann mit Hilfe des Feldes best berechnet werden. Per Definition ist best[M] in ihm enthalten, und der restliche Inhalt ist der gleiche wie im optimalen Rucksack der Größe M - size[best[M]]. Daher ist best[M - size[best[M]]] im Rucksack enthalten, usw. Für unser Beispiel ist best[17]=C; danach finden wir ein anderes Element vom Typ C bei der Größe 10, dann ein Element vom Typ A bei der Größe 3.

Eigenschaft 42.1 Für die Lösung des Rucksack-Problems mit Hilfe der dynamischen Programmierung wird eine zu NM proportionale Zeit benötigt.

Dies ergibt sich offensichtlich aus dem Programm. w.z.b.w.

Somit kann das Rucksack-Problem leicht gelöst werden, wenn M nicht groß ist; für große Fassungsvermögen kann die Laufzeit jedoch unvertretbar groß werden. Ein weiterer entscheidender Punkt, der nicht übersehen werden darf, ist die Tatsache, daß das Verfahren überhaupt nicht anwendbar ist, wenn M und die Größen oder Werte zum Beispiel reelle Zahlen anstatt ganzer Zahlen sind. Dies ist mehr als eine kleine Unzulänglichkeit: Es ist eine grundlegende Schwierigkeit. Für dieses Problem ist keine gute Lösung bekannt, und in Kapitel 45 werden wir sehen, daß viele Fachleute der Ansicht sind, daß keine gute Lösung existiert. Um eine Vorstellung von der Komplexität dieses Problems zu erhalten, möge der Leser versuchen, einen Fall zu lösen, bei dem alle Gegenstände den Wert 1 haben, der j-te Gegenstand die Größe sqrtj hat und M gleich N/2 ist.

Wenn jedoch die Fassungsvermögen sowie die Größen und Werte der Gegenstände ganze Zahlen sind, so gilt das grundlegende Prinzip, daß optimale Entscheidungen nicht geändert werden müssen, nachdem sie einmal getroffen wurden. Nachdem wir einmal den besten Weg ermittelt haben, um Rucksäcke einer beliebigen Größe mit den ersten j Gegenständen zu füllen, brauchen wir diese Probleme nicht wieder zu betrachten, gleichgültig, welches die nächsten Gegenstände sind. Jedesmal, wenn dieses allgemeine Prinzip zur Anwendung gebracht werden kann, ist die dynamische Programmierung anwendbar. In diesem Falle führt das Verfahren zum Ziel, da ganzzahlige Größen uns die Möglichkeit geben, exakte, »optimale« Entscheidungen zu treffen.

Bei diesem Algorithmus muß nur wenig Information über frühere optimale Entscheidungen gespeichert werden, falls M nicht groß ist. Bei unterschiedlichen Anwendungen der dynamischen Programmierung sind die diesbezüglichen Anforderungen sehr verschieden; weiter unten betrachten wir weitere Beispiele.


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