Entwurfsprinzipien Bearbeiten

Auf dieser Seite werden wir und mit Entwurfsprinzipien und einer Einführung in die Entwurfsmuster beschäftigen. Die Ableitung eines optimalen Algorithmus aus Anforderungsbeschreibungen ist nicht automatisierbar. Der Algorithmenentwurf ist eine kreative Tätigkeit, die durch Muster ( best practices) unterstützt wird. Vergleichbar ist das mit Mustern von Gebäuden in der Architektur oder mit Mustern aus der Softwarearchitektur.

Schrittweise Verfeinerung Bearbeiten

Der Entwurf von Algorithmen erfolgt nach dem Prinzip der schrittweisen Verfeinerung von Pseudo Code Algorithmen. Pseudo Code Teile werden im ersten Schritt durch verfeinerten Pseudo Code ersetzt und im nächsten Schritt durch Programmiersprachen Code.

Beispiel 1 Bearbeiten

1. Pellkartoffeln kochen

verfeinert zu :

1.1 Fülle Topf mit Kartoffeln

1.2 Füge Wasser dazu

1.3 Stelle topf auf Herdplatte

1.4 Stelle Drehknopf auf 7

1.5 Koche das Wasser

Beispiel 2 Bearbeiten

Wir benutzen die Fakultät als Prozeduraufruf

Factorial(n)

Nun schreiben wir die Fakultät als Algorithmus

Fac: var X;Y:int;
input X; 
Y:=1;
while X>1 do Y:=Y*X; X:=  X-1 od
output Y

Nun schreiben wir die Fakultät als Implementierungscode

public static int factorial (int x) {
...
}

Einsatz von Algorithmenmustern Bearbeiten

Die Idee ist, dass generische Algorithmenmuster für bestimmte Problemklassen an eine konkrete Aufgabe angepasst werden. Das Lösungsverfahrens wird am Beispiel eines einfachen Vertreters der Problemklasse dokumentiert. Es wird eine Bibliothek von Mustern (Design Pattern) zur Ableitung eines abstrakten Programmrahmens benutzt. Durch parametrisierte Algorithmen und Vererbung wird die Programmiersprache unterstützt.

Greedyalgorithmus Bearbeiten

Auf dieser Seite wird der Greedyalgorithmus behandelt.

Greedy bedeutet "gierig". Der Algorithmus erfolgt nach dem Prinzip, dass versucht wird mit jedem Teilschritt so viel wie möglich zu erreichen. Greedy-Algorithmen (gierige Algorithmen) zeichnen sich dadurch aus, dass sie immer denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht.

Lokales Optimum Bearbeiten

Der Greedy Algorithmus berechnet in jedem Schritt das lokale Optimum, dabei kann jedoch das globale Optimum verfehlt werden.

Jedoch entspricht in vielen Fällen das lokale Optimum auch dem globalem Optimum, bzw. es reicht ein lokales Optimum aus.

Problemklasse Bearbeiten

Gegebene Menge von Eingabewerten
Menge von Lösungen, die aus Eingabewerten aufgebaut sind
Lösungen lassen sich schrittweise aus partiellen Lösungen, beginnend bei der leeren Lösung, durch Hinzunahme von Eingabewerten aufbauen. Alternativ: bei einer ganzen Menge beginnend schrittweise jeweils ein Element wegnehmen
Bewertungsfunktion für partielle und vollständige Lösungen
Gesucht wird die/eine optimale Lösung

Das Münzwechselproblem Bearbeiten

Auf dieser Seite wird das Münzwechselproblem NICHT behandelt.

Beispiel Bearbeiten

Als Beispiel nehmen wir die Herausgabe von Wechselgeld auf Beträge unter 1€. Verfügbar sind die Münzen mit den Werten 50ct, 10ct, 5ct, 2ct, 1ct. Unser Ziel ist, so wenig Münzen wie möglich in das Portemonnaie zu bekommen.

Ein Beispiel: $78ct=50+2\cdot 10+5+2+1$

Es wird jeweils immer die größte Münze unter dem Zielwert genommen und von diesem abgezogen. Das wird so lange durchgeführt, bis der Zielwert Null ist.

Formalisierung Bearbeiten

Gesucht ist ein Algorithmus der folgende Eigenschaften beschreibt.

Bei der Eingabe muss gelten

1. dass die eingegebene Zahl eine natürliche Zahl ist, also

amount>0

2. dass eine Menge von Münzwerten zur Verfügung steht

currency=\{c_{1},...,c_{n}\}\ {\text{z.B.}}\{1,2,5,10,20,50\}

Die Ausgabe besteht dann aus ganzen Zahlen $change[1],...,change[n]$ . Dabei ist $change[i]$ die Anzahl der Münzen des Münzwertes für $c_{i}$ für $i=1,...,n$ und haben die Eigenschaften

1.

change[1]\cdot c_{1}+...+change[n]\cdot c_{n}=amount

2.

change[1]+...+change[n]

ist minimal unter allen Lösungen für 1.

Algorithmus Bearbeiten

1. Nehme jeweils immer die größte Münze unter dem Zielwert und ziehe sie von diesem ab.

2. Verfahre derart, bis der Zielwert gleich Null ist.

Der dazugehörige Code in Java:

public int[] moneyChange(int[] currency, int amount){
   int[] change = new int[currency.length];
   int currentCoin = currency.length-1;
   while(amount > 0){
      while(amount < currency[currentCoin] && currentCoin > 0)
         currentCoin--;
      if(amount >= currency[currentCoin] && currentCoin >= 0){
         amount -= currency[currentCoin];
         change[currentCoin]++;
      } else return null;
   }
   return change;
}

Die Methode moneyChange wird dabei aufgerufen durch:

int[] currency = {1,2,5,10,20,50};
int amount = 78;
int[] change = moneyChange(currency, amount);

Lokales Optimum Bearbeiten

Der Greedy Algorithmus berechnet im jedem Schritt das lokale Optimum, dabei kann jedoch das globale Optimum verfehlt werden.

Beispiel: Münzen 11ct, 5ct und 1ct. Unser Zielwert ist 15ct. Nach Greedy benutzen wir 11+1+1+1+1, das Optimum wäre aber 5+5+5.

Analyse Bearbeiten

Theorem Bearbeiten

Für $currency$ endlicher Länge und mit endlichen positiven Werten und endlichem positivem $amount$ , terminiert der Algorithmus moneyChange nach endlich viele Schritten.

Beweis Bearbeiten

In Zeile 03 wird $currentCoin$ mit einem endlichen positiven Wert initialisiert
In Zeile 05 und 06 wird $currentCoin$ nur dekrementiert, spätestens beim Wert 0 wird die Schleife beendet (also eine endliche Wiederholung)
Falls die Zeilen 08 und 09 nicht ausgeführt werden, endet die Berechnung direkt in 10; andernfalls wird $amount$ in Zeile 08 echt kleiner
Irgendwann ist also der Bedingung in Zeile 04 nicht mehr gegeben und die Berechnung terminiert

Theorem Bearbeiten

Für Eingabe $currency$ mit $|currency|=m$ und $amount=n$ hat der Algorithmus moneyChange eine Laufzeit von O(m+n).

Beweis Bearbeiten

Die Zeile 6 wird maximal m-mal ausgeführt
Die Zeile 8 wird maximal n-mal ausgeführt, falls es nur eine Münze mit dem Wert "1" gibt

Theorem Bearbeiten

Der Algorithmus moneyChange löst für $currency=\{1,2,5,10,20,50\}$ das Münzwechselproblem.

Beweis Bearbeiten

Bei der Lösung musste zum Einen gelten, dass $change[1]\cdot c_{1}+...+change[n]\cdot c_{n}=amount$ ist. Da der Wert $amount$ stets um den Wert einer Münze $c_{i}$ verringert wird, während $change[i]$ um eins inkrementiert wird, ist dies erfüllt.

Die zweite Aussage zur Lösung war, dass $change[1]+...+change[n]$ minimal unter allen Lösungen sein soll. Dies wird hier nur für Münzen vom Wert 1,2 und 5 betrachtet, wobei es für die Münzen 10, 20 und 50 analog zu beweisen ist.

Zunächst gilt, dass 2er-Münzen stets 1er-Münzen zu bevorzugen sind, da es keinen Sinn macht im Algorithmus auf eine 2er-Münze zu verzichten, um dann im nächsten Schritt mehr 1er-Münzen zu bekommen. Das bedeutet, dass eine optimale Lösung maximal eine 1er-Münze beinhaltet.

Weiterhin gilt, eine optimale Lösung hat nicht mehr als zwei 2er-Münzen. Sollten drei 2er-Münzen in der Lösung sein, ist es besser diese durch eine 1er und eine 5er-Münze zu ersetzen.

Des Weiteren gilt, eine optimale Lösung kann nicht gleichzeitig eine 1er-Münze und zwei 2er-Münzen enthalten, weil dies durch eine 5er-Münze dargestellt werden kann.

Es folgt, dass der durch 1er- und 2er-Münzen dargestellte Betrag nicht mehr als 4 sein kann. Also ist eine maximale Wahl von 5er-Münzen im Greedy-Verfahren optimal.

Divide and Conquer Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

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.

Backtracking Bearbeiten

Auf dieser Seite wird das Backtracking behandelt.

Die Idee des Backtracking ist das Versuchs-und-Irrtum-Prinzip (trial and error). Versuche, die erreichte Teillösung schrittweise zu einer Gesamtlösung auszubauen. Falls die Teillösung nicht zu einer Lösung führen kann, dann nimm den letzten Schritt bzw. die letzten Schritte zurück und probiere stattdessen alternative Wege.Alle in Frage kommenden Lösungswege werden ausprobiert. Vorhandene Lösung wird entweder gefunden (unter Umständen nach sehr langer Laufzeit) oder es existiert definitiv keine Lösung. Backtracking (“Zurückverfolgen“) ist eine allgemeine systematische Suchtechnik. KF ist die Menge von Konfigurationen. $K_{0}$ ist die Anfangskonfiguration. Für jede Konfiguration $K_{i}$ gibt es eine direkte Erweiterung $K_{i,1},...,K_{i,n_{i}}$ . Außerdem ist für jede Konfiguration entscheidbar, ob sie eine Lösung ist. Aufgerufen wird Backtracking mit $BACKTRACK(K_{0})$ .

Labyrinth Suche Bearbeiten

Backtracking1

Backtracking2

Backtracking Muster Bearbeiten

procedure BACKTRACK (K: Konfiguration)
begin
	…
	if [ K ist Lösung ]
	then [ gib K aus ]
	else
		for each [ jede direkte Erweiterung K0 von K ]
			do
				BACKTRACK (K0)
			od
	fi
end

Einsatzfelder Bearbeiten

Zu den typischen Einsatzfeldern von Backtracking gehören zum Beispiel einige Spielprogramme (Schach, Dame, Labyrinthsuche,…). Aber auch die Erfüllbarkeit von logischen Aussagen wie logische Programmiersprachen, Optimierung von Gattern oder Model checking (Theorembeweiser). Ein weiteres Einsatzfeld sind Planungsprobleme und Konfigurationen wie logistische Fragestellungen (Traveling Salesman, der kürzeste Wege, die optimale Verteilung, das Färben von Landkarten oder auch nichtdeterministisch-lösbare Probleme.

Beispiel Acht Damen Problem Bearbeiten

Acht Damen Problem

Gesucht sind alle Konfigurationen von 8 Damen auf einem 8 x 8-Schachbrett, so dass keine Dame eine andere bedroht. Gesucht ist nun ein geeignetes KF. Für jede Lösungskonfigurationen L mit gelten $L\subseteq KF$ . Für jedes $k\in KF$ ist leicht entscheidbar, ob $k\in L$ . Die Konfigurationen lassen sich schrittweise erweitern und wir erhalten eine hierarchische Struktur. Es sollte auch beachtet werden, dass KF nicht zu groß sein sollte.

$L_{1}$ : Es sind 8 Damen auf dem Brett

$L_{2}$ : Keine zwei Damen bedrohen sich.

KF wird so gewählt, dass die Konfiguration mit je einer Dame in den ersten n Zeilen, $1\leq n\leq 8$ , so dass diese sich nicht bedrohen.

Acht Damen Problem2

Diese Konfiguration ist nun nicht mehr erweiterbar. Jedes Feld in Zeile 7 ist bereits bedroht.

procedure PLATZIERE (i:[1..8]);
begin
   var h: [1..8];
   for h:=1 to 8 do
      if [Feld in Zeile i, Spalte h nicht bedroht]
      then
         [Setze Dame auf dieses Feld (i,h)];
         if [Brett voll] /* i=8*/
         then [Gib Konfiguration aus ]
         else PLATZIERE (i+1)
         fi
      fi
   od
end

Acht Damen Problem4

Die Array Repräsentation ist [4,1,3,5,0,0,0,0]. Die Diagonalen sind belegt wenn:

i+h = i+h

i-h = i-h

(i = Spalte, h = Zeile)

Die Zeilen snd belegt, wenn die Position im Array besetzt ist und die Spalten sind belegt, wenn die Nummer im Array existiert.

Der initiale Aufruf geschieht mir Platziere(1). Es gibt insgesamt 92 Lösungen. Die Konfigurationen ist etwa als zweidimensionales boolesches Array oder als eindimensionales Array mit einer Damenposition pro Zeile realisierbar. Redundante Informationen über bedrohte Spalten und Diagonalen bieten Optimierungspotential.

Algorithmus in Java Bearbeiten

Der Code zu dem Problem im allgemeinen Fall sieht in Java wie folgt aus.

public boolean isValid(int[] board, int current, int place){
   for(int i = 0; i < current-1; i++){
      if(board[i] == place) return false;
      if(place+current == board[i] + (i+1)) return false;
      if(place-current == board[i] - (i+1)) return false;
   }
   return true;
}

public int[] placeQueen(int[] board, int current){
   int[] tmp;
   for(int i=0; i< board.length; i++){
      if(isValid(board, current, i)){
         board[current-1] = i;
         if(current == board.length) return board;
         else{
            tmp = placeQueen(board, current+1);
            if(tmp != null) return tmp;
         }
      }
   }
   return null;
}

Aufgerufen wird der Code durch:

int[] result = placeQueen(new int[8], 1);

Analyse Bearbeiten

Theorem

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

Beweis

Die Methode $isValid$ terminiert offensichtlich immer.

In $placeQueen$ wird rekursiv $placeQueen$ stets um einen erhöhten Parameter $current$ aufgerufen. Die for-Schleife hat auch stets eine konstante Zahl an Durchgängen.

Theorem

Für ein Feld der Größe n x n hat der Algorithmus $placeQueen$ eine Laufzeit von $O(n^{n})$ .

Beweis

Im schlimmsten Fall werden alle Konfigurationen betrachtet:

n Positionen für eine einzelne Dame
n Damen sind zu plazieren

Die tatsächliche Laufzeit ist weitaus geringer, da viele Konfigurationen schon früh als nicht-erweiterbar erkannt werden. Dennoch ist die Laufzeit im schlimmsten Fall exponentiell $O(2^{n})$ .

Theorem

Der Algorithmus $placeQueen$ löst das n-Damenproblem.

Dynamische Programmierung Bearbeiten

Auf dieser Seite wird die dynamische Programmierung behandelt.

Die dynamische Programmierung vereint die Ideen verschiedener Muster. Zum einen die Wahl der optimalen Teillösung des Greedy Musters und zum anderen die Rekursion und den Konfigurationsbaum aus Divide and Conquer und Backtracking. Die Unterschiede sind, dass Divide and Conquer unabhängige Teilprobleme löst und in der dynamischen Programmierung eine Optimierung von abhängigen Teilproblemen durchgeführt wird. Die dynamische Programmierung ist eine „bottom-up“-Realisierung der Backtracking-Strategie. Die Anwendungsbereiche sind die selben wie bei Greedy, jedoch wird dynamische Programmierung insbesondere dort angewandt, wo Greedy nur suboptimale Lösungen liefert.

Idee Bearbeiten

Bei der dynamischen Programmierung werden kleinere Teilprobleme zuerst gelöst, um aus diesen größere Teillösungen zusammenzusetzen. Das Problemlösen geschieht quasi auf Vorrat. Es werden möglichst nur die Teilprobleme gelöst, die bei der Lösung der großen Probleme auch tatsächlich benötigt werden. Wir erzielen einen Gewinn, wenn identische Teilprobleme in mehreren Lösungszweigen betrachtet werden. Rekursives Problemlösen wird ersetzt durch Iteration und abgespeicherte Teilergebnisse.

Nicht immer ist es überhaupt möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die Lösung eines größeren Problems ergibt. Die Anzahl der zu lösenden Probleme kann unvertretbar groß werden. Es können zu viele Teillösungen entstehen, die dann doch nicht benötigt werden oder der Gewinn der Wiederverwendung ist zu gering, da die Lösungszweige disjunkt sind.

Beispiel Editierdistanz Bearbeiten

Gegeben sind zwei Zeichenketten s und t, was ist die minimale Anzahl an Einfüge-, Lösch- und Ersetzoperationen um s in t zu transformieren?

Als Beispiel entspricht s "Haus" und t "Maus". Die Lösung ist hier, dass "H" durch "M" ersetzt wird. Bei s= "Katze" und t="Glatze" wird "K" durch "G" ersetzt und "I" hinzugefügt. Die Editierdistanz kommt in der Rechtschreibprüfung und Plagiatserkennung zur Anwendung.

Formalisierung Bearbeiten

Definition ( Ein-Schritt Modifikation)

Beachte $s=s_{1}...s_{m}$

Jedes $s'=s_{1}...s_{i-1}s_{i+1}....s_{m}$ (für $i=1,...,m$ )
Jedes $s'=s_{1}...s_{i-1}xs_{i+1}....s_{m}$ (für $i=1,...,m~und~x!=s_{i}$ )
Jedes $s'=s_{1}...s_{i}xs_{i+1}....s_{m}$ (für $i=0,1,...,m~und~bel.~x$ )

heißt Ein-Schritt Modifikation von s.

Definition (k-Schritt Modifikation) Eine Zeichenkette t heißt k-Schritt Modifikation $(k>1)$ von s, wenn es Zeichenketten u gibt mit:

u ist eine Ein-Schritt Modifikation von s
t ist eine k-1-Schritt Modifikation von u

Definition (Editierdistanz, auch Levenshtein-Distanz) $D(s,t)=min\{d|s~ist~eine~d-Schritt~Modifikation~von~t\}$

Ist s eine d-Schritt Modifikation von t, so ist auch s eine d+2j Modifikation von t für jedes j>0.Eine minimale Modifikation muss nicht eindeutig sein. Wir sind aber hier nur an dem Wert einer minimalen Modifikation interessiert.

Charakterisierung und Algorithmus Bearbeiten

Die Idee ist, dass die Berechnung von D(s,t) auf die Berechnung von D auf die Präfixe von s und t zurückgeführt wird.

Definition $D_{ij}(s,t)$

Sei $s=s_{1}...s_{m}~und~t=t_{1}...t_{n}$

Definiere $D_{ij}(s,t)=D(s_{1}...s_{i},t_{1}...t_{j})(fueri=0,...,m,j=0,...,n)$

Beachte für z.B i=0 haben wir $s_{1}...s_{i}=\epsilon$ (leerer String).

Wir beobachten, dass gilt $D_{mn}(s,t)=D(s,t)$ . Dies ist nun zu berechnen. Zudem ist $D_{00}(s,t)=D(\epsilon ,\epsilon )=0$ , also sind zwei leere Strings identisch.

$D_{0j}(s,t)=D(\epsilon ,t)=j$ für j=1,..,n. Also alle Zeichen $t_{1}...t_{j}$ müssen eingefügt werden.

$D_{i0}(s,t)=D(s,\epsilon )=i$ für i=1,...,m. Also alle Zeichen $s_{1}...s_{i}$ müssen eingefügt werden.

Theorem der zentralen Charakterisierung der Editierdistanz Bearbeiten

Falls $s_{i}=t_{j}:D_{ij}(s,t)=D_{i-1,j-1}(s,t)$ .

Ansonsten: $D_{ij}(s,t)=min:=\left\{{\begin{array}{ll}D_{i-1,j-1}(s,t)+1&Ersetzung\\D_{i,j-1}(s,t)+1&Einfuegung\\D_{i-1,j}(s,t)+1&Loeschung\end{array}}\right.$

Algorithmus Bearbeiten

For j=0,...,n set  $D_{0j}$ (s,t)=j
For i=0,...,m set  $D_{i0}$ (s,t)=i
For i=1,..,m
   For j=1,...,n
      If  $s_{i}=t_{j}$  set  $D_{ij}(s,t)=D_{i-1,j-1}(s,t)$ 
      else  $D_{ij}(s,t)=$ 
         min { $D_{i-1,j-1}(s,t)+1,D_{i,j-1}(s,t)+1,D_{i-1,j}(s,t)+1$ }
Return  $D_{mn}(s,t)$

Analyse Bearbeiten

Theorem

Für endliche Zeichenketten s und t terminiert der Algorithmus editdistance nach endlich vielen Schritten.

Beweis

Der Beweis folgt auf dem nächsten Theorem.

Theorem

Für die Eingaben $s=s_{1}...s_{m}$ und $t=t_{1}...t_{n}$ hat der Algorithmus eine Laufzeit von $\Theta (mn)$ .

Beweis

Der Beweis besteht aus einer einfachen Schleifenanalyse.

Theorem

Der Algorithmus editdistance berechnet die Editierdistanz zweier Zeichenketten s und t.

Beweis

Der Beweis folgt direkt aus der zentralen Charakterisierung der Editierdistanz.

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Entwurfsmuster Druckversion

Entwurfsprinzipien Bearbeiten

Schrittweise Verfeinerung Bearbeiten

Beispiel 1 Bearbeiten

Beispiel 2 Bearbeiten

Einsatz von Algorithmenmustern Bearbeiten

Greedyalgorithmus Bearbeiten

Lokales Optimum Bearbeiten

Problemklasse Bearbeiten

Das Münzwechselproblem Bearbeiten

Beispiel Bearbeiten

Formalisierung Bearbeiten

Algorithmus Bearbeiten

Lokales Optimum Bearbeiten

Analyse Bearbeiten

Theorem Bearbeiten

Beweis Bearbeiten

Theorem Bearbeiten

Beweis Bearbeiten

Theorem Bearbeiten

Beweis Bearbeiten

Divide and Conquer Bearbeiten

Grundidee Bearbeiten

Muster Bearbeiten

Beispiel Bearbeiten

Türme von Hanoi Bearbeiten

Algorithmenentwurf Bearbeiten

Analyse Bearbeiten

Backtracking Bearbeiten

Labyrinth Suche Bearbeiten

Backtracking Muster Bearbeiten

Einsatzfelder Bearbeiten

Beispiel Acht Damen Problem Bearbeiten

Algorithmus in Java Bearbeiten

Analyse Bearbeiten

Dynamische Programmierung Bearbeiten

Idee Bearbeiten

Beispiel Editierdistanz Bearbeiten

Formalisierung Bearbeiten

Charakterisierung und Algorithmus Bearbeiten

Theorem der zentralen Charakterisierung der Editierdistanz Bearbeiten

Algorithmus Bearbeiten

Analyse Bearbeiten