Wie kann man die Permutationen von n Elementen systematisch erzeugen?
Jedes Element steht einmal vorne, während die restlichen n - 1 Elemente zu permutieren sind (0 oder 1 Element sind leicht zu permutieren) Rekursiver Ansatz
Wie können die erzeugten Permutationen aus dem Inneren von rekursiven Aufrufen nach außen geliefert werden?
Ein nebenläufiger Prozess (Thread) kann die Permutationen erzeugen und über einen Puffer bereitstellen.
Vollständige Aufzählung (5)
class Perm extends Thread{ private int[] a, b; // a Arbeitsarray, b Puffer private int max; // maximaler Index private boolean bufferfull = false; // Pufferkontrolle Perm (int n){ // Konstruktor n = Math.abs (n); // n darf nicht negativ sein a = new int[n]; // Indices: 0 .. n-1 max = n-1; for (int i=0; i<=max; i++) a[i]=i; // a fuellen this.start (); // run-Methode beginnt zu laufen } // Konstruktor public void run (){ perm (1); // a[0] bleibt fest; permutiere ab 1 a = null; // Anzeige, dass fertig put (); // in Puffer uebertragen } ... } // Perm
Vollständige Aufzählung (6)
class Perm extends Thread{ ... private void perm (int i){ // permutiere ab Index i int h; if (i >= max){ // eine Permutation fertig put (); // in Puffer uebertragen return; // zurueck (und weiter) } perm (i+1); // rekursiver Aufruf ab i+1 for (int j=i+1; j<=max; j++){ // jedes nach Vorne h = a[i]; a[i] = a[j]; a[j] = h; // swap (i,j) perm (i+1); // und Rekursion } h = a[i]; // restauriere Array for (int j=i; j
Vollständige Aufzählung (7)
class Perm extends Thread{ ... synchronized int[] getNext (){ // liefert naechste Permutation try{ while (!bufferfull) wait (); // non busy waiting bufferfull = false; // leere Puffer } catch (InterruptedException e){} notify (); // wecke anderen Thread return b; // liefere Permutationsarray } private synchronized void put (){ // fuelle Puffer try{ while (bufferfull) wait (); // non busy waiting b = a == null ? a : (int[]) a.clone(); // Uebertragung bufferfull = true; // Puffer voll } catch (InterruptedException e){} notify (); // wecke anderen Thread } } // Perm
Backtracking (1)
Backtracking ist eine spezielle Methode zur systematischen und erschöpfenden Suche im Raum sämtlicher Möglichkeiten. Korrekte Teillösungen werden schrittweise bis zu Gesamtlösungen erweitert.
Ist die Erweiterung der aktuellen Teillösung nicht mehr möglich, wird der vorhergehende Schritt zurückgenommen und durch den nächsten Erweiterungsschritt ersetzt.
Beispiel: N-Dame Problem
Gegeben: N × N Schachbrett S
Aufgabe: Positioniere N Damen auf S, so dass sie sich gegenseitig (nach Schachregeln) nicht schlagen können. (Keine zwei Damen dürfen die gleiche Zeile, Spalte, oder Diagonale besetzen.)
4-Damen Problem
4-Damen Problem
Backtracking (2)
Die Lösungen lassen sich als Vektoren schreiben: (1, 3, 0, 2) bedeutet, dass die Dame in Spalte 0 in Zeile 1 steht, die folgenden in den Zeilen 3, 0, 2.
Aufsteigende Diagonalen (von links nach rechts) können mit (i + j) durchnummeriert werden, absteigende mit (i - j + N - 1); die Nummern sind dann jeweils 0, . . . (2N - 2). D D D i=0 1 2 3 j=0 1 2 3 D Beispiel für N = 4:
Backtracking (3)
public class Dameproblem { public static void main(String args[]){ int n = Integer.parseInt (args[0]); if (n <= 0) { System.out.println("Der Parameter sollte positiv sein!"); return; } Schachbrett s = new Schachbrett (n); System.out.println("Die Loesungen des "+n+"-Dameproblems sind:"); long cnt = 0; // Zaehler fuer Loesungen int i = 0; // Index der aktuellen Spalte while (i >= 0) { if (i == n) { cnt++; // Loesung! Zaehle Anzahl mit System.out.println (s); // gib Loesung aus i--; // zum Finden weiterer Loesungen } if (s.rueckeDame (i)) i++; // Naechste Position in Spalte i else i--; // Backtrack !! } System.out.println("Es gab "+cnt+" Loesungen des "+n+"-Dameproblems."); } }
Backtracking (4)
class Schachbrett { private int [] a; // das Array fuer die Damen private boolean [] u, d, z; // Arrays fuer die Diagonalen und Zeilen Schachbrett (int n) { // Konstruktor a = new int [n]; u = new boolean [2*n-1]; // aufsteigende Diagonale (up) d = new boolean [2*n-1]; // absteigende Diagonale (down) z = new boolean [n]; // Zeilen for (int i=0; i < a.length; i++) { a[i] = -1; z[i] = true; // Zeilen & Spalten sind frei } for (int i=0; i < u.length; i++) u[i] = d[i] = true; // Diagonalen sind frei } public String toString () { // erzeugt druckbare Darstellung String s = ""; for (int i=0; i < a.length; i++) s += a[i]+" "; return s; } // ... (weitere Methoden) }
Backtracking (5)
class Schachbrett { // ... boolean rueckeDame (int i) { // versuche Dame von Spalte i int j = a[i]; // in naechste Zeile zu setzen if (j >= 0) aendereBelegung (i,j); // befreie Feld (i,j) for (; ++j < a.length ;) if (unbedroht (i,j)) { aendereBelegung (i,j); // besetze Feld return true; // Versuch erfolgreich } // return false; // oder nicht erfolgreich } private void aendereBelegung (int i, int j) { // belege oder befreie u [i+j] = d [i-j+a.length-1] = z[j] = a[i] == j; // Feld (i,j) a[i] = z[j] ? -1 : j; } boolean unbedroht (int i, int j) { // testet, ob Feld (i,j) unbedroht ist return u [i+j] && d [i-j+a.length-1] && z[j]; } }
Backtracking (6)
Kennzeichen von Problemen, bei denen Backtracking Anwendung findet:
Lösung kann als Vektor a [0], a [1], . . . (möglicherweise unbestimmter, aber) endlicher Länge codiert werden.
Jedes Element a [i] ist ein Element einer endlichen Menge A[i].
Für jedes a A[i] kann entschieden werden, ob es als Erweiterung einer Teillösung a [0], . . . , a [i - 1] in Frage kommt.
Beispiele für die Anwendbarkeit von Backtracking:
Labyrinth-Suche: Finde einen Weg vom Start zum Ziel.
Hamiltonscher Zyklus in einem Graphen: Finde einen Weg durch einen Graphen, der jeden Knoten genau einmal berührt und dann zum Ausgangspunkt zurückkehrt.
Scan- oder Sweep-Verfahren
Merkmal: Eine räumliche Dimension wird in eine zeitliche Dimension verwandelt. Ein statisches d-dimensionales Problem wird als ein dynamisches (d - 1)-dimensionales Problem behandelt. Dazu wird eine Linie (Ebene, . . . ) entlang einer Dimension geführt und eine damit verbundene Datenstruktur konsistent bei gewissen Ereignissen geändert (Invariante).
Bsp: Maximum-Subarray Problem; statisches 1-dim. Problem wird als dynamisches 0-dim. Problem behandelt.
Weitere Problem-Beispiele:
Dichtestes Paar einer Menge von n reellen Zahlen
Dichtestes Paar einer Menge von n Punkten in
k Schnittpunkte einer Menge von n Liniensegmenten in der Ebene
Scan-Line-Verfahren für das Maximum-Subarray Problem (1)
Das Maximum-Subarray Problem:
Gegeben: Folge X von n ganzen Zahlen im Array
Gesucht: Maximale Summe einer zusammenhängenden Teilfolge von X und deren Index-Grenzen
Beispiel:
31 -41 59 26 -53 58 97 -93 -23 84
Das ist hier maximal
Frage: Wie findet man die maximale Teilfolge — möglichst effizient?
Scan-Line-Verfahren für das Maximum-Subarray Problem (2) Scan-Line Ansatz
Der Scan-Line Ansatz:
scanMax = 0;
bisMax = 0;
für i von 1 bis n:
scanMax += X[i]
falls (scanMax < 0) scanMax = 0;
bisMax = max(scanMax, bisMax);
max = bisMax;
Die Lösung des Maximum-Subarray Problems erfordert einen Aufwand in
(Jedes Element muss mindestens einmal betrachtet werden) Scan-Line-Verfahren für das Maximum-Subarray Problem (3)
Comments