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

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Rucksackproblem als Backtracking

Nun wird das Rucksackproblem mit Backtracking gelöst. Das Grundprinzip ist es, die optimale Lösung durch systematisches Absuchen des gesamten Lösungsraums zu finden. Angewandt auf unser Rucksackproblem bedeutet das, es gibt $2^{n}$ verschiedene Möglichkeiten, wir generieren und testen alle möglichen Rucksäcke und wir wenden Rekursion an.

Rekursionseinstieg

static Rucksack packeOptimalmitBacktracking() {
   return rucksackRekursiv(0, new Rucksack());
}

• Erster Parameter: Level i – Entscheidung, ob Objekt i in den Rucksack kommt
• Durchlaufen des Auswahl-Arrays von links nach rechts
• Aufrufgraph: Aufspannen eines binären Baumes durch ja/nein-Entscheidungen

Rekursion

static rucksackRekursiv(int i, Rucksack r) {
		if (i==auswahlObjekte.length) return r;
		// Objekt i nicht nehmen und rekurrieren
		Rucksack r1 = new Rucksack(r);
		r1 = rucksackRekursiv(i+1, r1);
		// Objekt i – falls moeglich – nehmen und rekurrieren
		if (r.gewicht()+auswahlObjekte[i].gewicht<=kapazitaet){
			Rucksack r2 = new Rucksack(r);
			r2.auswahl[i] = true;
			r2 = rucksackRekursiv(i+1,r2);
			// Den besseren Rucksack immer zurueckgeben
			if (r2.nutzen() > r1.nutzen()) 
				return r2;
		}	
		return r1; 
	}

Analyse

Das Problem ist hier, dass es einen extrem hohen Berechnungsaufwand für die große Auswahl an Objekten gibt. Die Komplexität liegt bei $O(2^{n})$. Der Vorteil ist, dass man garantiert die optimale Lösung finden, da im schlimmsten Fall jede Möglichkeit ausprobiert wird. Also wird in jedem Fall ein Optimum gefunden.