close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Backtracking Übersicht Übersicht Was ist das?

EinbettenHerunterladen
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Übersicht
Backtracking
Hallo Welt für Fortgeschrittene
Katrin Giese
katti@andariel.informatik.uni-erlangen.de
3. Mai 2006
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning search und A*
4
Färbeproblem
5
Zusammenfassung
6
Literatur
1
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Backtracking
2
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Was ist das?
Übersicht
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning Search und A*
4
Färbeproblem
5
Zusammenfassung
6
Literatur
Definition
Der Begriff Rücksetzverfahren oder englisch Backtracking
(Rückverfolgung) realisiert eine allgemeine systematische
Suche, die einen vorgegebenen Lösungsraum komplett
bearbeitet. Wenn man in einer Teillösung in eine Sackgasse
kommt, wird jeweils der letzte Schritt rückgängig gemacht.
Der Begriff „backtrack“ wurde durch den amerikanischen
Mathematiker D.H.Lehmer in den 1950er Jahren geprägt.
wichtiger Such- und Optimierungsalgorithmus
Katrin Giese
Backtracking
3
Katrin Giese
Backtracking
4
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (I)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (II)
alle möglichen Ergebnisse sind Blätter in einem Baum
Prinzip: Baum mit Tiefensuche
innere Knoten sind Teillösungen
durch Abarbeitung des Lösungsbaums trifft man auf
„Sackgassen“→ zur letzten noch nicht bearbeitende
Abzweigung zurückgehen
Programm geht durch jeden möglichen Pfad
Start des Programms ist die Wurzel
1
Beginn mit Anfangskonfiguration
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
2
falls Ergebnis falsch, gehe Schritt zurück und versuche
nächsten unbearbeiteten Weg
falls Ergebnis richtig, Ergebnis speichern, ein Schritt
zurückgehen und versuche nächsten unbearbeiteten Weg
(um alle Möglichkeiten zu finden)
5
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Backtracking
6
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Katrin Giese
Backtracking
7
Katrin Giese
Backtracking
8
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
9
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Backtracking
10
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Katrin Giese
Backtracking
11
Katrin Giese
Backtracking
12
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Verfahren (III)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (I)
Labyrinth
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
13
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (II)
Backtracking
14
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (III)
Katrin Giese
Backtracking
15
Katrin Giese
Backtracking
16
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (IV)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (V)
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
17
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (VI)
Backtracking
18
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (VII)
Eingabe ist eine Matrix (inklusive Größe, die das Labyrinth
beschreibt
Programm terminiert, wenn Matrix die Größe 0 ist
Beispiel
#include <iostream>
bool laby(int, int, char);
char* weg;
int cnt,n,m;
char** lab;
int main(){
int c = 1;
while(true){
//initialisieren und einlesen
int a = 0, b = 0;
std::cin>>n>>m;
if(n == 0 && m == 0) break;
char mem;
lab = new char*[n];
for(int i = 0;i < n; i++) lab[i] = new char [m];
weg = new char[n*m];
for(int i = 0; i < n*m; i++) weg[i] = 0;
for(int i = 0;i < n; i++){
for(int j = 0; j < m; j++){
std::cin>>mem;
lab[i][j] = mem;
}
} ...
5 9
S10000000
011011110
001010000
011011010
00000101G
0 0
Katrin Giese
Backtracking
19
Katrin Giese
Backtracking
20
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (VIII)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel (IX)
cnt = 0;
for(int i = 0; i < n; i++){
// Start suchen
for(int j = 0; j < m; j++){
if(lab[i][j] == ’S’){
a = i;
b = j;
break;
}
}
if(lab[a][b] == ’S’) break;
}
if(laby(a,b,’S’)){
// Ausgabe
std::cout<<"Labyrinth #"<<c<<std::endl<<"Weg: ";
cnt--;
while(cnt >= 0) {
std::cout << weg[cnt];
cnt--;
}
std::cout << std::endl;
}
c++;
bool laby(int s, int t, char pfad) {
if(s >= 0 && t >= 0 && s < n && t < m){
//sind wir am Ziel?
if(lab[s][t] == ’G’) return true;
//sind wir in einer Wand?
if(lab[s][t] == ’1’) return false;
//auf weg und weitergehen?
if(lab[s][t] == ’0’ || lab[s][t] == ’S’) {
//koennen wir nach oben?
if(pfad != ’u’ && laby(s-1,t,’o’)) {
weg[cnt] = ’o’;
cnt++;
return true;
}
//koennen wir nach unten?
else if(pfad != ’o’ && laby(s+1,t,’u’)) {
weg[cnt] = ’u’;
cnt++;
return true;
} ...
}
return 0;
}
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
21
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Backtracking
22
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Terminierung
Beispiel (X)
//koennen wir nach links?
else if(pfad != ’r’ && laby(s,t-1,’l’)) {
weg[cnt] = ’l’;
cnt++;
return true;
}
else if(pfad != ’l’ && laby(s,t+1,’r’)) {
weg[cnt] = ’r’;
cnt++;
return true;
}
else
//wir koennen also nirgendwo hin... :-(
return false;
nur garantiert für:
einmaliges Betreten einer Konfiguration eines Weges
endlichen Lösungsraum
}
}
std::cout<<"geht net"<<std::endl;
return false;
}
Katrin Giese
Backtracking
23
Katrin Giese
Backtracking
24
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Heuristiken (I)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Heuristiken (II)
Definition
Als Heuristik (zu deutsch „ich finde“) bezeichnet man eine
Strategie, die ermöglicht, eine optimale oder zumindest
passable Lösung schnell zu finden (jedoch ohne Garantie).
Heuristiken können die Zeitkomplexität von Backtracking
verringern:
1
2
Heuristiken geben keine Garantie für Verbesserungen
Schätzung einer günstigen Lösung oder der günstigsten
Lösung
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
25
heuristische Steuerung der Reihenfolge, in welcher der
Suchbaum durchquert wird
durch geschickt gewählte Bewertungsfunktion, die die
Länge der zur Auswahl stehenden Wege bis zum Ziel
schätzt
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel - Springerproblem (I)
Backtracking
26
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel - Springerproblem (II)
Springerproblem ist kombinatorisches Problem
Finde für einen Springer auf einem leeren Schachbrett
eine Route, auf der der Springer alle Felder, aber jedes nur
genau einmal besucht
http://www.axel-conrad.de/springer/springer.html
Katrin Giese
Backtracking
27
Katrin Giese
Backtracking
28
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel - Springerproblem (III)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel - Springerproblem (IV)
#include <iostream>
using namespace std;
int field[8][8];
void init();
bool springer(int x, int y);
int fertig();
int main(){
int n,m;
cin>>n>>m;
init();
if(springer(n,m)){
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
cout<<field[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
http://de.wikipedia.org/wiki/Springerproblem
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
29
Beispiel - Springerproblem (V)
30
Was ist Backtracking?
Heuristiken
Zeitkomplexität
bool springer(int x, int y){
int cnt = 1;
int c = 0;
if((c = fertig()) == 65) return true;
if(x < 0 || y < 0 || x > 7 || y > 7){
cout<<"OutOfBounds"<<endl;
return false;
}
if(field[x][y] > 0){
cout<<"belegt"<<endl;
return false;
}
field[x][y] = c;
cnt++;
...
int fertig(){
int c = 0;
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
if(field[i][j] > 0) c++;
}
}
return c+1;
}
Backtracking
Backtracking
Beispiel - Springerproblem (VI)
void init(){
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
field[i][j] = 0;
}
}
}
Katrin Giese
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
31
Katrin Giese
Backtracking
32
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Beispiel - Springerproblem (VII)
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Heuristik von Warnsdorf
...
//Zugmoeglichkeiten
if(springer(x+1,y+2)) return true;
else if(springer(x+1,y-2)) return true;
else if(springer(x+2,y+1)) return true;
else if(springer(x+2,y-1)) return true;
else if(springer(x-1,y+2)) return true;
else if(springer(x-1,y-2)) return true;
else if(springer(x-2,y+1)) return true;
else if(springer(x-2,y-1)) return true;
else{
field[x][y] = 0;
cnt--;
return false;
}
Ziel: Schnellere Laufzeit
Anspringen der Felder, die am schlechtesten erreichbar
sind
Faustregel: Je weniger Felder man vom Standpunkt
anspringen kann, umso schlechter ist das Feld
Dadurch schneller lösbar
}
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
33
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Was ist Backtracking?
Heuristiken
Zeitkomplexität
Zeitkomplexität
Backtracking
34
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Übersicht
Merke: Baum mit Tiefensuche
z mögliche Verzweigungen von jeder Teillösung
Lösungsbaum mit maximaler Tiefe von N
daraus folgt:
im schlechtesten Fall eine Erweiterung mit
1 + z + z 2 + z 3 . . . + z N Knoten
somit worst-case: O(z N ) → exponentielle Laufzeit
deshalb: Backtracking primär für kleine Suchbäume
geeignet, sehr schlecht für große Suchbäume
Katrin Giese
Backtracking
35
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning search und A*
4
Färbeproblem
5
Zusammenfassung
6
Literatur
Katrin Giese
Backtracking
36
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Lineare Rekursion
Was ist das?
Definition
Eine Funktion ist genau dann linear rekursiv, wenn ihre
Aufrufstruktur linear ist.
Definition
Rekursion ist die Definition eines Problems, einer Funktion oder
eines Verfahrens durch sich selbst.
Existenz einer Abbruchbedingung notwendig
Bedingung:
ohne Abbruchbedingung gelangt das Programm in eine
Endlosschleife
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
maximal ein Selbstaufruf der Funktion in jedem Zweig
37
Lineare Rekursion - Beispiel
Backtracking
38
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Lineare Rekursion - Beispiel
Fakultät mit n! = n*(n-1)!
Fakultät mit n! = n*(n-1)!
int fak(int n){
if(n <= 1) return 1;
else return fak(n-1)*n;
}
int fak(int n){
if(n <= 1) return 1;
else return fak(n-1)*n;
}
Platzverbrauch ist O(n)
Katrin Giese
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Platzverbrauch ist O(n)
Backtracking
39
Katrin Giese
Backtracking
40
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Lineare Rekursion - Beispiel
Repetitive Rekursion (I)
Fakultät mit n! = n*(n-1)!
Definition
Eine Rekursion ist repetitiv, wenn jeder Selbstaufruf einer linear
rekursiven Funktion bzw. Funktionsdeklaration, der letzte
auszuwertende (Teil-) Ausdruck ist.
int fak(int n){
if(n <= 1) return 1;
else return fak(n-1)*n;
}
auch Rumpf-Rekursion genannt oder auf englisch: tail
recursion
Platzverbrauch ist O(n)
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Backtracking
41
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Backtracking
42
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Repetitive Rekursion - Beispiel
Repetitive Rekursion (II)
diesmal eine andere Version von Fakultät
int fak2(int n){
return fak3(n,1);
}
nach rekursiven Aufrufen keine weitere Operation
auswerten
kein zusätzlicher Platzbedarf zur Verwaltung der Rekursion
int fak3(int n, int a){
if(n == 0) return a;
else return fak3(n-1, a*n);
}
können unmittelbar durch Schleifen ersetzt werden
Platzverbrauch von O(n)
Katrin Giese
Backtracking
43
Katrin Giese
Backtracking
44
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Repetitive Rekursion - Beispiel
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Repetitive Rekursion - Beispiel
diesmal eine andere Version von Fakultät
diesmal eine andere Version von Fakultät
int fak2(int n){
return fak3(n,1);
}
int fak2(int n){
return fak3(n,1);
}
int fak3(int n, int a){
if(n == 0) return a;
else return fak3(n-1, a*n);
}
int fak3(int n, int a){
if(n == 0) return a;
else return fak3(n-1, a*n);
}
Platzverbrauch von O(n)
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Platzverbrauch von O(n)
Backtracking
45
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Kaskadenartige Rekursion
Backtracking
46
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Kaskadenatrige Rekursion - Beispiel (I)
Fibonacci-Zahlen mit
f0 = 0; f1 = 1; fn+1 = fn + fn−1
konkret: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 . . .
Definition
Eine kaskadenartige Rekursion ist jede rekursive Funktion oder
Funktionsdeklaration, die nicht linear rekursiv ist.
jedes Folgenglied ist Summe der beiden vorhergehenden
Glieder
int fib(int n){
if(n == 0) return 0;
if(n == 1) return 1;
else return fib(n-1)+fib(n-2);
}
Existenz von mindestens einem Selbstaufruf der Funktion
in einem Zweig
exponentieller Platzverbrauch
Katrin Giese
Backtracking
47
Katrin Giese
Backtracking
48
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Kaskadenatrige Rekursion - Beispiel (I)
Kaskadenatrige Rekursion - Beispiel (I)
Fibonacci-Zahlen mit
Fibonacci-Zahlen mit
f0 = 0; f1 = 1; fn+1 = fn + fn−1
konkret: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 . . .
f0 = 0; f1 = 1; fn+1 = fn + fn−1
konkret: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 . . .
jedes Folgenglied ist Summe der beiden vorhergehenden
Glieder
jedes Folgenglied ist Summe der beiden vorhergehenden
Glieder
int fib(int n){
if(n == 0) return 0;
if(n == 1) return 1;
else return fib(n-1)+fib(n-2);
}
int fib(int n){
if(n == 0) return 0;
if(n == 1) return 1;
else return fib(n-1)+fib(n-2);
}
exponentieller Platzverbrauch
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
exponentieller Platzverbrauch
49
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Verschachtelte Rekursion
Backtracking
50
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Verschachtelte Rekursion
Methodendeklaration f enthält Aufruf der Methode g, die
wiederum einen Aufruf von f enthält
allgemein: k Methodendeklarationen
Beispiel: Ackermann
Methodendeklaration f enthält Aufruf der Methode g, die
wiederum einen Aufruf von f enthält
allgemein: k Methodendeklarationen
Beispiel: Ackermann
ackermann(int n, int m) {
if (n == 0) return m+1;
else if (m == 0) return ackermann(n-1, 1);
else return ackermann(n-1, ackermann(n, m-1));
}
exponentieller Platzverbrauch
Katrin Giese
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Backtracking
ackermann(int n, int m) {
if (n == 0) return m+1;
else if (m == 0) return ackermann(n-1, 1);
else return ackermann(n-1, ackermann(n, m-1));
}
exponentieller Platzverbrauch
51
Katrin Giese
Backtracking
52
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Lineare Rekursion
Repetitive Rekursion
Kaskadenartige Rekursion
Verschachtelte Rekursion
Verschachtelte Rekursion
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Übersicht
Methodendeklaration f enthält Aufruf der Methode g, die
wiederum einen Aufruf von f enthält
allgemein: k Methodendeklarationen
Beispiel: Ackermann
ackermann(int n, int m) {
if (n == 0) return m+1;
else if (m == 0) return ackermann(n-1, 1);
else return ackermann(n-1, ackermann(n, m-1));
}
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning search und A*
4
Färbeproblem
5
Zusammenfassung
6
Literatur
exponentieller Platzverbrauch
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
53
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Backtracking
54
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Was ist das? (I)
Definition
Branch&Bound ist eine Methode zur Lösung von
Optimierungsproblemen. Diese Methode bewertet Teillösungen
und vergleicht sie mit der bisher besten Lösung v. Wenn die
bewertete Teillösung keine bessere Lösung als v besitzt, wird
sie nicht mehr betrachtet.
Branch&Bound
Branch and Bound gehört zu dem
Entscheidungsbaum-Verfahren.
Katrin Giese
Backtracking
55
Katrin Giese
Backtracking
56
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Was ist das? (II)
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verfahren
bestehend aus 2 Teilen:
Entscheidungsbaum:
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Branching („Verzweigen“)
Bounding („Beschränken“)
1
2
Veranschaulichung aufeinanderfolgender hierarchischer
Entscheidungen
Darstellung als Baum, wobei jeder Knoten abgefragt und
eine Entscheidung getroffen wird (bis Blatt erreicht ist)
Generierung im Top-Down-Prinzip
Backtracking
Ziel:
Lösungsraum möglichst klein halten durch Weglassen von
suboptimalen Zweigen im aufgespannten
Entscheidungsbaum → Baum wird nach und nach
aufgebaut
57
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Branching
Backtracking
58
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Tiefensuche
Aufteilung in Teilprobleme zur Vereinfachung des
Gesamtproblems
Auswahlregel: Bearbeitung des zuletzt eingefügten
unbearbeiteten Teilproblems
Entstehung einer Baumstruktur durch Rekursion
Prinzip von LIFO (Last In - First Out)
drei verschiedene Auswahlverfahren:
schnelle Abarbeitung in die Tiefe → schneller Erhalt einer
zulässigen Lösung (aber keine Aussage über Qualität)
Tiefensuche („depth first search “)
Breitensuche („breadth first search “)
Bestensuche („best first search “)
Katrin Giese
Backtracking
59
Katrin Giese
Backtracking
60
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Breitensuche
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Bestensuche
Auswahlregel: Bearbeitung des zuerst eingefügten
unbearbeiteten Teilproblems
Prinzip von FIFO (First In - First Out)
Auswahlregel: Bearbeitung des unbearbeiteten
Teilproblems mit bester unterer Schranke
Abarbeitung jedes Knotens pro Ebene → erst wenn alle
Knoten in der Ebene bearbeitet wurden geht es eine
Ebene tiefer
direkter Erhalt der ersten Lösung mit guter Qualität
zulässige Lösung erst relativ spät, aber bessere Qualität
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
61
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Bounding
Backtracking
62
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Wie? (I)
Berechnung und Vergleich zweier Schranken
Begrenzung des Rechenaufwandes durch
„abschneiden“bestimmter Zweige, die dann nicht mehr
betrachtet werden
untere Schranke („lower bound“):
Der Wert des aktuellen Teilproblems (von der Wurzel aus
berechnet)
problemspezifische Schrankenberechnung (abhängig von
Aufgabenstellung und verwendeter Heuristik)
obere Schranke („upper bound“):
Berechnung einer vorerst optimalen zulässigen Lösung
durch eine heuristische Funktion
oder die bisher beste gefundene Lösung
Wie?
Katrin Giese
Backtracking
63
Katrin Giese
Backtracking
64
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Komplexität
Wie? (II)
wenn untere Schranke > obere Schranke:
Komplexität ist abhängig von:
Abschneiden des aktuellen Teilbaums (kein Erreichen einer
besseren zulässigen Lösung)
der verwendeten heuristischen Funktion (Schätzfunktion)
der Reihenfolge, in der der Baum durchsucht wird
dem Aufbau des Baumes
wenn untere Schranke < obere Schranke:
Zweig wird weiter untersucht
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
65
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Backtracking
66
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Pruning Search
Definition
Pruning („Beschneiden “) ist ein Verfahren, dass bestimmte
Teil-Suchbäume „abschneidet “.
Pruning Search
abgeschnittene Teilbäume werden nicht mehr betrachtet,
da gesuchte Objekte nicht in diesen enthalten sind (das
Wissen bekommt man durch gesammelte Daten)
bei spekulativem Pruning:
Annahme, das in diesen Teilbäumen nicht das gesuchte
Objekt ist (ohne Vorwissen)
„überflüssiges “abschneiden, aber keine
Beeinträchtigungen des Ergebnisses
Katrin Giese
Backtracking
67
Katrin Giese
Backtracking
68
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Beispiel
Pruning Search
zuverlässig, wenn mindestens eine optimale Lösung nicht
abgeschnitten wird
1
2
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
8-Damen-Problem
keine zwei Damen dürfen in derselben Reihe, Spalte oder
Diagonale stehen
Algorithmus bleibt vollständig
mindestens ein Pfad führt zu einer optimalen Lösung
Speicherkomplexität im worst-case ist exponentiell
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
69
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Backtracking
70
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Lösungsmöglichkeiten
Was ist das? (I)
Erhalt von 12 Lösungen (ohne, dass sie durch Drehen
oder Spiegeln des Brettes entstanden sind)
Finden einer Stellung (oder mehrerer) für 8 Damen auf
dem Schachbrett, in der sich 2 Damen nach den Regeln
des Schachs nicht schlagen können
4 Spiegelungen (an Diagonalen, Horizontale und Vertikale
durch Brettmitte)
zusätzlich:
(4 + 4) ∗ 12 = 96 Möglichkeiten
Ignorieren der Figurenfarbe
Annahme: jede Figur kann jede andere Figur angreifen
Katrin Giese
Backtracking
da aber eine der Lösungen bei einer Drehung um 180
Grad dieselbe ist, kommt man auf 92 Möglichkeiten
71
Katrin Giese
Backtracking
72
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Lösungsmöglichkeiten - Spezialfall
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verfahren
http://de.wikipedia.org/wiki/Damenproblem
Wie geht man ran?
Verwendung von Backtracking:
gegeben sei ein zweidimensionales Feld und Anfangspunkt
a
von a aus Betrachtung der Diagonalen, Horizontalen und
Vertikalen
wenn keine andere Dame vorhanden, kann man die Dame
setzen
dann gehe zum nächsten freien Feld und versuche die
nächste Dame zu setzen
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
73
Beispiel - Damenproblem (I)
Backtracking
74
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Beispiel - Damenproblem (II)
bool dame(int n, int m){
int i;
if(d[n] >= 0) return false;
for(i=0;i<8;i++){
// Spalte
if(d[i] == m) return false;
}
for(i=n;i>=0;i--){
// Diagonale
if(n-i >= 0 und m-i >= 0)
if(field[n-i][m-i] == 1) return false;
if(n-i >= 0 && m+i < 8)
if(field[n-i][m+i] == 1) return false;
}
field[n][m] = 1;
d[n] = m;
if(n == 7) return true; <- fertig
//ausprobieren naechste Dame zu setzen
for(int i = 0; i < 8; i++) if(dame(n+1,i)) return true;
//wenn es fehlgeschlagen ist - zuruecksetzen
field[n][m] = 0;
d[n] = -1;
return false;
}
#include <iostream>
bool dame(int, int);
int field[8][8];
int d[8];
void init(){
int i,j;
for(i=0;i<8;i++){
d[i] = -1;
for(j=0;j<8;j++){
field[i][j] = 0;
}
}
}
int main(){
init();
// Startpunkt
std::cin>>x>>y;
dame(x,y);
}
Katrin Giese
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Backtracking
75
Katrin Giese
Backtracking
76
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verbesserung
A*-Algorithmus
Verbesserung durch bestimmte Heuristiken:
Zum Setzen einer neuen Dame bestimmte Felder nicht
besuchen → Felder, die direkt in der Umgebung sind
evtl. Verbesserung durch Ausnutzen von Symmetrie oder
Rotationen
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
77
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Was ist das? (I)
Backtracking
78
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Was ist das? (II)
Definition
Der A*-Algorithmus dient zur Berechnung eines kürzesten
Pfads zwischen zwei Knoten in einem Graphen mit positiven
Kantengewichten unter Verwendung einer heuristischen
Funktion.
zuerst Untersuchung der Knoten, die höchstwahrscheinlich
zum Ziel führen
ist nur zuverlässig, wenn Graph endlich ist
Effizienz des A*-Algorithmus ist abhängig von der Heuristik
A* ist ein deterministischer Suchalgorithmus
ist eine informative Suche → zurückgreifen auf Heuristiken
→ somit zielgerichtetes Suchen
Problem muss bekannt sein
Katrin Giese
Backtracking
79
Katrin Giese
Backtracking
80
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verfahren (I)
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Verfahren (II)
Anfang: Knoten k
Gleichung: f (n) = g(n) + h(n)
von k aus Berechnung aller erreichbaren Nachbarn
g(n) : Gesamtkosten vom Startknoten bis n
danach Anwendung der Heuristik → Abschätzung der
Kosten vom Nachbarn n zum Ziel
h(n) : wahrscheinliche Kosten von n bis zum Ziel (durch
Heuristik geschätzt)
Addieren der Kosten: die Kosten vom bereits gegangen
Weg (Wurzel bis n) und die geschätzten Kosten von n bis
zum Ziel
f (n) : wahrscheinliche Gesamtkosten vom Start bis zum
Ziel über k und n
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
A* hat exponentiellen Speicher- und Zeitaufwand
81
Katrin Giese
Backtracking
82
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Verfahren
Branching
Bounding
Pruning Search
A*-Algorithmus
Anwendungen
Übersicht
Routenplaner
Computerspiele (Einheiten zu einem bestimmten Punkt
bewegen → Weg muss berechnet werden)
Roboter (in vorgegebener Welt selbstständig Weg finden)
Katrin Giese
Backtracking
83
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning search und A*
4
Färbeproblem
5
Zusammenfassung
6
Literatur
Katrin Giese
Backtracking
84
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Anwendung
Was ist das?
Stundenplanprobleme:
Eine Färbung eines ungerichteten Graphen ordnet jedem
Knoten (bzw. jeder Kante) im Graphen eine Farbe zu
Knoten sind Veranstaltungen
Kanten zwischen Veranstaltungen, die nicht gleichzeitig
laufen dürfen
beide Veranstaltungen vom gleichen Lehrer
oder beide in einer Klasse
Register-Zuweisungs-Probleme in Prozessoren,
Bandbreiten-Zuweisung-Probleme, andere Probleme aus
der Mathematik
Katrin Giese
Backtracking
85
Katrin Giese
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Backtracking
86
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Fälle (I)
Fälle (II)
Spezialfall:
Allgemeiner Fall:
Vier-Farben-Satz
Bestimmung der Farbanzahl eines Graphen ist NP-schwer
aus Sicht der Komplexitätstheorie kein effizienter
Algorithmus vorhanden
Verbesserung durch Färbeheuristiken
ist ebenfalls NP-schwer
chromatische Zahl: 4 (Farben)
bipartite Graphen
liefern im Erfolgsfall obere Schranke für chromatische Zahl
(Farbanzahl)
Katrin Giese
Backtracking
ist Entscheidungsproblem und lösbar mit Tiefensuche
chromatische Zahl: 2
87
Katrin Giese
Backtracking
88
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Komplexität
Übersicht
Backtracking ist für große Graphen sehr ungeeignet
Exponentieller Aufwand
Katrin Giese
Backtracking
89
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning search und A*
4
Färbeproblem
5
Zusammenfassung
6
Literatur
Katrin Giese
Backtracking
90
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Zusammenfassung
Danke für eure Aufmerksamkeit
Backtracking: Baum mit Tiefensuche
Noch Fragen?
wird schnell ineffizient (exponentieller Aufwand)
Optimierung von Backtracking durch B&B, Pruning Search
und A*
Backtracking ist vielseitig anwendbar
Katrin Giese
Backtracking
91
Katrin Giese
Backtracking
92
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Literatur (I)
Übersicht
1
Motivation
2
Rekursion
3
Branch&Bound, Pruning search und A*
4
Färbeproblem
http://www.informatik.uniulm.de/ki/Edu/Vorlesungen/GdKI/WS0304/skript/04Infsuche.pdf
5
Zusammenfassung
www.stefan-baur.de
6
Literatur
http://de.wikipedia.org/wiki/Backtracking
www.tcs.informatik.uni-muenchen.de/lehre/WS0304/InfoI/Folien/F18.pdf
http://aima.eecs.berkeley.edu/slides-pdf/chapter04a.pdf
Katrin Giese
Backtracking
93
Motivation
Rekursion
Branch&Bound, Pruning search und A*
Färbeproblem
Zusammenfassung
Literatur
Literatur (II)
„Algorithmen und Datenstrukturen“von Gunter Saake/Kai
Uwe Sattler
Dpunkt-Verlag, 2002
„Algorithmik“von Uwe Schöning
Spektrum-Akademischer Verlag, 2001
Katrin Giese
Backtracking
95
Katrin Giese
Backtracking
94
Document
Kategorie
Technik
Seitenansichten
19
Dateigröße
628 KB
Tags
1/--Seiten
melden