Wikiversity

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Beispiel:Rucksackproblem dynamisch

< Kurs:Algorithmen und Datenstrukturen | Vorlesung



Startseite
Vorlesung


Rucksackproblem als dynamische Programmierung

Bearbeiten

Nun wird das Rucksackproblem mit dynamischer Programmierung gelöst. Wir erinnern uns, dass das Grundprinzip der dynamischen Programmierung die Wiederverwendung von bereits berechneten Teillösungen ist. Aber an dieser Stelle ist Vorsicht geboten mit den anderen Lösungen aus den vorherigen Seiten, wo Teillösungen Bottom up zusammengesetzt wurden. Hier basieren die Lösungen auf der Backtracking Variante. Teillösungen werden zwischengespeichert. Die Existenz von Teillösungen wird als Abbruchkriterium für die Rekursion verwendet.

Rekursionseinstieg

Bearbeiten 
static Rucksack packeMitDynamischerProgrammierung()
   Rucksack [][] zwischenErgebnisse=
      new Rucksack[kapazitaet+1][anzahlObjekte];
   return rucksackRekursivDP (0, new Rucksack(), zwischenErgebnisse);
}

Ein Eintrag zwischenErgebnisse[g][i] bedeutet, dass wir schon ein mal dabei waren, das Objekt i in einen Rucksack mit dem Gewicht g zu legen. In diesem Fall können wir alle vor berechneten Entscheidungen für die Objekte i bis anzahlObjekte −1 wiederverwenden, da diese bereits optimal sind (Backtracking: äquivalenter Teilbaum).

Rekursion

Bearbeiten 
static Rucksack rucksackRekursivDP (int i, Rucksack r, Rucksack [][] zwischenErgebnisse){
   if (i == auswahlObjekte.length) return r;
   int gewicht = r.gewicht();
   // Wiederverwendung von Teillösungen:
   if (zwischenErgebnisse[gewicht][i] != null}{
      for (int j = i; j < anzahlObjekte; j++)
         r.auswahl[j] = zwischenErgebnisse[gewicht][i].auswahl[j];
      return r;
   }
   Rucksack r1 = new Rucksack (r);
   r1 = rucksackRekursivDP(i+1, r1, zwischenErgbenisse);
   if (gewicht+auswahlObjekte[i].gewicht <= kapazitaet){
      Rucksack r2 = new Rucksack (r);
      r2.auswahl[i] = true;
     
      if (r2.nutzen() > r1.nutzen()) r1 = r2;
   }
   // Merken von Teillösungen:
   zwischenErgebnisse[gewicht][i] = r1;
   return r1;
}

Analyse

Bearbeiten

Die Vorteile der dynamischen Programmierung sind, dass auf jeden Fall die optimale Lösung gefunden wird. In vielen Fällen hat sie auch einen geringeren Aufwand als Backtracking. Das Problem ist allerdings, dass die Anwendbarkeit und der Aufwand abhängig von der Größe und der Struktur des Suchraums sind. Die Komplexität beträgt O(z), wobei z die Anzahl der möglichen Zwischenergebnisse ist. Zum Beispiel: bei vielen unterschiedlichen Gewichtskombinationen kaum Ersparnis (Erhöhen von MAX_GEWICHT). Außerdem existieren polynomielle Approximationen!


     

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Beispiel:Rucksackproblem_dynamisch&oldid=628974“