Zum Inhalt springen

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

Aus Wikiversity




Rucksackproblem als Backtracking

[Bearbeiten]

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 verschiedene Möglichkeiten, wir generieren und testen alle möglichen Rucksäcke und wir wenden Rekursion an.

Rekursionseinstieg

[Bearbeiten]
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

[Bearbeiten]
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

[Bearbeiten]

Das Problem ist hier, dass es einen extrem hohen Berechnungsaufwand für die große Auswahl an Objekten gibt. Die Komplexität liegt bei . 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.


Discussion