Divide and Conquer

Auf dieser Seite wird Divide and Conquer behandelt. Divide and Conquer bedeutet "Teile und Herrsche". Quick Sort und Merge Sort sind typische Vertreter. Es verfolgt das Prinzip, dass auf identische Probleme mit einer kleinen Eingabemenge eine rekursive Rückführung geschieht.

Grundidee

Teile das gegebene Problem in mehrere getrennte Teilprobleme auf, löse diese einzeln und setze die Lösungen des ursprünglichen Problems aus den Teillösungen zusammen. Wende dieselbe Technik auf jedes der Teilprobleme an, dann auf deren Teilprobleme, usw, bis die Teilprobleme klein genug sind, dass man eine Lösung explizit angeben kann. Strebe an, dass jedes Teilproblem von derselben Art ist wie das ursprüngliche Problem, so dass es mit demselben Algorithmus gelöst werden kann.

Muster

procedure DIVANDCONQ (P: problem)
begin
	…
	if [P klein ]
	then [explizite Lösung ]
	else [ Teile P auf in P1, …, Pk ];
		DIVANDCONQ (P1 ) ;
		… ;
		DIVANDCONQ (Pk) ;
		[ Setze Lösung für P aus Lösungen für P1, …, Pk zusammen ]
	fi
end

Beispiel

Wir nehmen als Beispiel die Spielpläne für Turniere. Gegeben sind $n=2^{k}$ Spieler, wobei k ganzzahlig und größer 0 ist. Des weiteren sind mindestens n-1 Turniertage gegeben und jeder Spieler spielt gegen jeden anderen. Der Turnierplan $T_{k}$ ist bekannt und die Aufgabe ist $T_{k+1}$ für $m=2n=2^{k+1}$ zu konstruieren (Rekursionsprinzip).

Spielplan für $T_{2}$

	Tag 1	Tag 2	Tag 3
Spieler 1	2	3	4
Spieler 2	1	4	3
Spieler 3	4	1	2
Spieler 4	3	2	1

Spielplan für $T_{1}$ Für kleine Problemgröße kann Lösung direkt angegeben werden:

	Tag 1
Spieler 1	2
Spieler 2	1

Nun konstruieren wir $T_{k+1}$ aus $T_{k}$ .

	Tag 1...n-1	Tag n...m-1
Spieler 1... $n=2^{k}$	$T_{k}$	$S_{k}$
n+1... $m=2{k+1}$	$T_{k}^{[+n]}$	$Z_{k}$

$T_{k}^{[+n]}:T_{k}$ mit jeweils um n erhöhten Elementen
$S_{k}:(n~x~n)$ Matrix, konstruiert durch zyklisches Verschieben der Spalte (n+1,…,m) für $n=2^{k}~und~m=2^{k+1}$
$Z_{k}:(n~x~n)$ Matrix, konstruiert durch zyklisches Verschieben der Zeile (1,2,..., n)

$Z_{2}={\begin{pmatrix}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\\\end{pmatrix}}$

$S_{2}={\begin{pmatrix}5&8&7&6\\6&5&8&7\\7&6&5&8\\8&7&6&5\\\end{pmatrix}}$

Spielplan für $T_{3}$

	Tag 1	Tag 2	Tag 3	Tag 4	Tag 5	Tag 6	Tag 7
Spieler 1	2	3	4	5	8	7	6
Spieler 2	1	4	3	6	5	8	7
Spieler 3	4	1	2	7	6	5	8
Spieler 4	3	2	1	8	7	6	5
Spieler 5	6	7	8	1	2	3	4
Spieler 6	5	8	7	2	3	4	1
Spieler 7	8	5	6	3	4	1	2
Spieler 8	7	6	5	4	1	2	3

$T_{k}=$ Spieler 1-4 Tag 1-3

$S_{k}=$ Spieler 1-4 Tag 4-7

$T_{k}^{[+n]}=$ Spieler 5-8 Tag 1-3

$Z_{k}=$ Spieler 5-8 Tag 4-7

Türme von Hanoi

Bei den Türmen von Hanoi sind 3 Stapel mit Scheiben unterschiedlicher Größe gegeben. In jedem Schritt darf eine Scheibe, die ganz oben auf einem Stapel liegt, auf einen anderen Stapel gelegt werden. Allerdings unter der Bedingung, dass sie nur auf eine kleinere Scheibe gelegt werden darf.

Das Ziel ist es alle Scheiben vom ganz linken Stapel auf den ganz rechten Stapel zu verschieben.

Illegale Spielzüge sind dabei, wenn eine größere Scheibe auf eine kleinere Scheibe gelegt wird.

Algorithmenentwurf

Reduziere das Problem n Scheiben zu verschieben darauf nur noch n-1 Scheiben zu verschieben, bis schlussendlich nur noch eine Scheibe übrig bleibt.

Dies ist ein ähnliches Prinzip wie bei Induktionsbeweisen. Dabei kann das Nutzen des Algorithmus für n-1 Scheiben als der Induktionsschritt gesehen werden. Der Basisfall, also der Induktionsanfang, ist dabei, wenn es nur eine Scheibe gibt.

Um die Aufgabe zu lösen, muss beim Verschieben von mehr als einer Scheibe der dritte Stapel immer als "Zwischenlager" genutzt werden. Welcher der drei Stapel das "Zwischenlager" ist, kann ja nach Schritt wechseln. In dem Beispiel bei 5 Scheiben auf dem linken Stapel(A), dient dieser als Startstapel und soll auf den linken Stapel(C), also auf den Zielstapel, verschoben werden. Im ersten Schritt dient der mittlere Stapel(B) somit als Zwischenlager.

Das erste Unterziel ist es die obersten vier Scheiben von A zu verschieben. Dafür dient A als Startstapel, B als Zielstapel und C als Zwischenlager.

Weiterhin muss gewährleistet sein, dass das Zwischenlager nach Abschluss wieder genauso aussieht wie zuvor.

Der Pseudocode sieht wie folgt aus:

Algorithmus hanoi
Eingabe:
   Startstapel S,
   Zielstapel Z,
   Zwischenlager L,
   Anzahl der Scheiben n
Ausgabe:
   Aktionenfolgen um alle Scheiben von S nach L zu verschieben

Falls n=1
   Entferne die oberste Scheibe k von S und füge sie Z hinzu
   Gib aus "Verschiebe k von S nach Z"
Ansonsten
   hanoi(S,L,Z,n-1);
   Entferne die oberste Scheibe k von S und füge sie Z hinzu
   Gib aus "Verschiebe k von S nach Z"
   hanoi(L,Z,S,n-1);

Für die Implementierung in Java wird als Repräsentation der Stapel je ein $Stack$ und für eine Scheibe je ein $int$ verwendet. Bei den Scheiben gibt der Wert jeweils die Größe der Scheibe an.

public void hanoi(Stack<Integer> start, Stack<Integer> goal, Stack<Integer> tmp, int numDiscs){
   if(numDiscs == 1){
      int disc = start.pop();
      goal.push(disc);
      System.out.println("Moving disc " + disc);
   }else{
      hanoi(start, tmp, goal, numDiscs-1);
      int disc = start.pop();
      goal.push(disc);
      System.out.println("Moving disc " + disc);
      hanoi(tmp, goal, start, numDiscs-1);
   }
}

Der Aufruf erfolgt durch:

Stack<Integer> start = new Stack<Integer>();
for(int i = 5; i > 0; i--) start.push(i);
hanoi(start, new Stack<Integer>(), new Stack<Integer>(), 5);

Analyse

Theorem

Der Algorithmus $hanoi$ terminiert nach endlich vielen Schritten, wenn die Anzahl der Scheiben positiv ist.

Beweis

Die Zeile 03 stellt das Rekursionsende da und der Algorithmus terminiert bei numDiscs = 1
Die Else-Bedingung führt dazu, dass durch die rekursiven Aufrufe der Wert von numDiscs sich immer um 1 verringert.

Theorem

Für n Schreiben hat der Algortihmus $hanoi$ eine Laufzeit von $O(2^{n})$ .

Beweis

Die Rekursionsgleichung für $hanoi$ ist:

$T(n):=\left\{{\begin{array}{ll}1&{\text{falls}}\ n=1\\2\cdot T(n-1)+O(1)&sonst\end{array}}\right.$

Der Beweis erfolgt damit durch Induktion.

Theorem

Der Algorithmus $hanoi$ löst das Problem der Türme von Hanoi.

Beweis

Zu zeigen gelten:

Der Algorithmus hält sich an die Spielregeln, dass in jedem Zug nur eine Scheibe von oben von einem Stapel entfernt werden darf und auf einen leeren Stapel oder auf eine größere Scheibe gelegt wird.
Bei der Terminierung sind alle Scheiben auf dem Zielstapel.

Beide Aussagen kann man durch Induktion nach der Anzahl der Scheiben n beweisen.

Für $n=1$ : hier wird eine Scheibe direkt vom Startstapel zum leeren Zielstapel verschoben. In diesem Fall sind beide Bedingungen erfüllt.

Für $n-1\rightarrow n$ : Es sind n Scheiben von Stapel A zu C zu verschieben. Dazu sei B der dritte Stapel. Zunächst wird der Algorithmus rekursiv für die obersten n-1 Scheiben mit Zielstapel B aufgerufen. Da alle diese n-1 Scheiben kleiner als die unterste Scheibe ist und diese nicht bewegt wird, ist dies das gleiche Problem, als wenn die unterste Scheibe gar nicht da wäre. Nach rekursiven Aufruf werden also die n-1 Scheiben legal nach B verschoben. C ist dabei anschließend wieder leer. Die Verschiebung der untersten Scheibe nach C ist legal. Die rekursive Verschiebung der auf B liegenden n-1 Scheiben nach C ist nun wieder legal, aufgrund der Tatsache, dass auf C nur eine größere Scheibe liegt.

Der Algorithmus ist ebenso optimal, das heißt, er findet eine minimale Anzahl von Zügen zur Lösung des Problems.

Weiterhin ist eine Animation des Algorithmus verfügbar.