Elementare Algorithmen

Divide-and-Conquer-Strategie

Statt das Problem A durch ein direktes Verfahren zu lösen und so zur Lösung A zu gelangen, wird Problem A mithilfe von Divide in eine Menge von Teilproblemen B gleicher Art, aber kleinerer Größe zerlegt. Diese Teilprobleme werden gelöst (Conquer); es ergibt sich eine Menge von zugehörigen Teillösungen B. Mithilfe von Combine werden diese Teillösungen B zur gesuchten Lösung A wieder zusammengesetzt.

	Problem `A`	(direktes Verfahren)	Lösung `A`
*Divide*				*Combine*
	{ Teilprobleme `B` }	*Conquer*	{ Teillösungen `B` }

Die Divide-and-Conquer-Strategie ist immer dann vielversprechend, wenn der Aufwand zur Lösung der Teilprobleme B zusammengenommen geringer ist als der Aufwand zur Lösung des Gesamtproblems A. Hinzu kommt allerdings noch der Aufwand für Divide und für Combine; dieser darf nicht zu groß sein, sonst lohnt sich die Divide-and-Conquer-Strategie möglicherweise doch nicht.

Beispiel: Ein einfaches Sortierverfahren, z.B. Insertionsort, benötigt zum Sortieren einer Datenfolge der Länge n im direkten Verfahren n²/2 – n/2 Schritte. Zerlegen wir die Datenfolge in zwei Teilstücke der Länge n/2 und sortieren diese jeweils für sich mit Insertionsort, so benötigen wir 2 · (n²/8 – n/4) = n²/4 – n/2 Schritte, also weniger als halbsoviele Schritte wie im direkten Verfahren.

Hinzurechnen müssen wir allerdings noch den Aufwand für Divide und für Combine. Das Zerlegen der Folge in zwei Teilstücke (Divide) verursacht keinen Aufwand, wohl aber das Zusammenfügen (Combine) der jeweils für sich sortierten Teilstücke zu einer insgesamt sortierten Folge. Tatsächlich aber beträgt dieser Aufwand nur n Schritte, sodass wir mit n²/4 – n/2 + n = n²/4 + n/2 Schritten immer noch günstiger dastehen als beim direkten Verfahren, jedenfalls für n > 4.

Die Divide-and-Conquer-Strategie hat sich also in diesem Fall gelohnt. Richtig lohnend wird sie allerdings erst dann, wenn wir zum Sortieren der Teilstücke der halben Länge nicht das direkte Verfahren, sondern ebenfalls wieder die Divide-and-Conquer-Strategie anwenden, für die dabei entstehenden Teilstücke ebenfalls wieder usw., solange bis kein Divide mehr möglich ist. Beim Zerlegen einer Folge in Teilstücke ist dies dann erreicht, wenn nur noch Teilstücke der Länge 1 vorhanden sind.

Das Ergebnis ist das Sortierverfahren Mergesort.

Weiter mit: