Backtracking •we hadden
verbetering i
i 1
0:
Datastructuren college 10
1
1:
2
3
2:
1
2
3
1
2
3
1
2
3
P
r
r
r
r
r
b
r
b
r
2
3
0:
..
..
1:
..
..
2: P
1 2
1 1
2 r
3
3
1
2
3
1
2
3
r
r
b
r
b
r
2
3
..
..
..
..
• we hoeven vaak de kandidaat niet helemaal af te maken om hem te kunnen verwerpen
backtracking 2
hier verwerpen we een kandidaat permutatie zodra we 2 keer hetzelfde element tegenkomen.
• je verwerpt dan in een klap alle voortzettingen scheelt veel werk
1
2
backtracking: depth-first zoeken
algemeen backtrack algoritme
•niet alle kandidaten hoeven even lang te zijn.
r r r br
b
r
•begin met lege deeloplossing •voegtoe ( i ) { if (klaar) kan ook met meld_succes; extra functie else for ( alle_voortzettingen ) { voeg_toe_aan_deeloplossing; if ( past ) het eigenlijke voegtoe (i+1); backtracken haal_uit_deeloplossing; } kan ook } impliciet zijn
b r r br b r
•We hoeven de boom niet echt te bouwen: doorloop boom depth-first: •eerst kinderen, daarna broers en zussen •kinderen van links naar rechts
bijhouden van huidige pad + te onderzoek voortzettingen is voldoende 3
4
1
alternatief backtrack algoritme
kortste pad van muis naar kaas
•begin met lege deeloplossing •voegtoe ( i ) { if (klaar) meld_succes; else for ( alle_voortzettingen ) { deze staat nu if ( past ) binnen de conditie { voeg_toe_aan_deeloplossing; voegtoe (i+1); haal_uit_deeloplossing; } } }
•we willen niet alle oplossingen, maar de lengte van het kortste pad muis van niks, weet pas of er kaas is als hij er op staat zoek oplossingen met backtracken ommuur doolhof om testen op binnen doolhof blijven te voorkomen kortste pad kan geen cycle bevatten !
5
kortste pad representatie
plaats muizen op het pad om cycles te voorkomen
6
kortste pad algoritme
•normaal:
•maak met behulp van backtracking alle mogelijke paden (begin bij muis, geen cycles) •functieresultaat is afstand tot de kaas
pad =
met V0 is beginpunt (muis) Vk-1 is eindpunt (kaas) Voor alle i: Vi en Vi-1 grenzen aan elkaar we zoeken het kortste van die paden kortste pad ⇒ ieder veld hoogstens 1 keer voor
• hier bouwen we het pad in de doolhof vinden van buren is eenvoudig voorkomen van cycles door merken van velden geen extra geheugen nodig backtrack-functie levert afstand tot kaas op 7
int afstand ( veld ) { if ( op eindpunt ) return 0; else if ( veld is vrij ) // de test ! { bezet veld; // voorkomt cycles in pad bepaal minimum afstand vanaf alle buren; maak veld vrij; // backtrack stap return minimum + 1; } else return oneindig; }
8
2
kortste pad: C++ representatie
kortste pad algoritme in C++ int kortstePad ( int x, int y );
enum Veld { Vrij, Muis, Kaas, Muur };
// voor mutual recursion
int stuurMuizenVanaf ( int x, int y ) { int min_weg = kortstePad ( x+1, y ); min_weg = min (min_weg, kortstePad ( x , y+1 )); min_weg = min (min_weg, kortstePad ( x-1 , y )); return min (min_weg, kortstePad ( x , y-1 )); }
const int Lengte = 8, Breedte = 7; const int Oneindig = Lengte * Breedte; Veld doolhof [ Breedte ] [ Lengte ] = { {Muur, Muur, Muur, Muur, Muur, Muur, Muur}, {Muur, Vrij , Vrij , Vrij , Muur, Vrij , Muur}, {Muur, Vrij , Muur, Vrij , Muur, Vrij , Muur}, {Muur, Vrij , Vrij , Vrij , Vrij , Vrij , Muur}, {Muur, Vrij , Vrij , Vrij , Muur, Vrij , Muur}, {Muur, Kaas, Muur, Vrij , Vrij , Vrij , Muur}, {Muur, Vrij , Muur, Vrij , Vrij , Vrij , Muur}, {Muur, Muur, Muur, Muur, Muur, Muur, Muur} }; 9
kortste pad programma
int kortstePad ( int x, int y ) { switch ( doolhof [ x ] [ y ]) { case Kaas: return 0; case Vrij: // de test ! { doolhof [ x ] [ y ] = Muis; int min_weg = stuurMuizenVanaf ( x, y ); doolhof [ x ] [ y ] = Vrij; // backtrack stap return min_weg + 1; } default: return Oneindig; } }
i.p.v. for-loop
10
kortste pad afdrukken
int main ( ) { cout << kortstePad ( 6, 4 ) << endl; system("PAUSE"); return EXIT_SUCCESS; }
•resultaat is 6 correct, maar niet erg informatief we willen graag het pad zelf kennen probleem: op het moment dat we het kortste pad vinden weten we niet dat dit zo is.
•met normaal backtrack algoritme vinden we alle oplossingen •hoe vinden we het kortste ? •bewaar kortste tot nu toe ( ktnt ) •i.p.v. meldSucces nieuwe oplossing korter dan ktnt ? zo ja: ktnt = nieuwe oplossing
•als je alles geprobeerd hebt is ktnt de kortste!
•oplossingen: alle paden bewaren: duur en onnodig kortste pad tot nu toe bewaren
11
12
3
kortste pad afdrukken
kortste pad printen in C++
•globale object kortste pad •lengte kortste tot nu toe als reference argument •geef huidige lengte mee zodat je weet of je iets beters gevonden hebt. void kortstePad ( veld, lengte, int& kortste ) { if ( op eindpunt ) if ( lengte < kortste ) { kortste = lengte; // beter pad gevonden kopieerPad ( ); } else if ( veld is vrij ) // de test ! { bezet veld; // voorkomt cycles in pad kortstePad vanaf alle buren ( lengte+1 ); maak veld vrij; // backtrack stap } }
13
muizen vanaf de buren
void kortsteWeg ( int x ,int y, int lengte, int& kortste ) { switch ( doolhof [ x ][ y ]) { case Kaas: if ( lengte < kortste ) // koter pad ? { kortste = lengte; copyWeg ( ); } return; i.p.v. case Vrij: // de test ! for-loop doolhof [ x ][ y ] = Muis; muizenVanaf ( x, y, lengte+1, kortste ); doolhof [ x ][ y ] = Vrij; // backtrack stap return; default: return; } }
14
korste pad: oplossing
void muizenVanaf ( int x, int y, int lengte, int& kortste ) { kortsteWeg ( x+1, y , lengte, kortste ); kortsteWeg ( x , y+1, lengte, kortste ); kortsteWeg ( x-1 , y , lengte, kortste ); kortsteWeg ( x , y-1 , lengte, kortste ); by reference } argument: zelfde int main ( ) effect als { int kortste = Oneindig; globale variabele, kortsteWeg ( 4, 6, 0, kortste ); maar mooier if ( kortste < Oneindig ) { cout << "De lengte van de korste weg is " << kortste << endl; toonWeg ( weg ); } else { cout << "Geen weg gevonden\n"; toonWeg ( doolhof ); } system("PAUSE"); return EXIT_SUCCESS; }
##################### ### ### ### ### ### ### ### ### ### ### @ @ @ ### ### ### K ### @ @ ### ### ### @ ### #####################
•wat iedereen binnen 10 seconden al gezien had
15
16
4
op de zelfde manier
magische vierkanten
•in zo min mogelijk zetten met een paard op een schaakbord van een positie naar een andere •vind een rondgang van het paard op het schaakbord zodat alle posities bezocht worden •...
•vierkant van N bij N •bevat getallen van 0..N2-1, of 1..N2 •som van alle rijen en kolommen is gelijk soms ook de som van de diagonaal gelijk oplossing 1 0 5 7 4 6 2 8 1 3 oplossing 2 0 7 5 4 2 6 8 3 1 ...
17
magische vierkanten met backtracking
18
magische vierkanten in C++
•N bij N vierkant is matrix int[N][N] •met een beetje moeite kunnen we de som van de rijen en kolommen uitrekenen oritmen tere alg ! e b n a •1+2+..+(m-1)+m = m*(m+1)/2 er besta backtracking dan •hier m = N2-1 •dus totale som (N2-1)*(N2-1+1)/2 •voor iedere rij/kolom is de som dus (N2-1)*N/2 •vul kolom voor kolom
const int N = 3; const int NN = N*N; const int SOM = (NN-1)*N/2; int main ( ) { int m [ N ] [ N ]; bool vrij [ NN ]; for ( int i=0; i
kijk of som nog steeds kan passen gebruik bool vrij[NN] om te kijken of getallen vrij zijn
system("PAUSE"); return EXIT_SUCCESS; 19
}
20
5
vullen in C++
vullen in C++ 2
void vul( int i, int j, int m [N][N], bool vrij [NN], int s ) { som in if ( j==N ) // vierkant vol ? kolom print ( m ); else if ( i==N && s==SOM ) // kolom vol en som klopt ? vul ( 0, j+1, m, vrij, 0 ); else if ( i
void vul ( int i, int j, int m [N][N], bool vrij [NN], int s ) { if ( j==N ) print ( m ); bool klopt ( int m [N][N], int i ) else if ( i==N && s==SOM ) { vul ( 0, j+1, m, vrij, 0 ); int s=0; else if ( i
representatie deeloplossing
22
kortste pad analyse •Algemeen voor backtrack algoritmen: O(VL)
•globale rij waar we oplossing in bouwen permutaties, n-queens
V aantal mogelijkheden L langst mogelijke pad niet beter dan brute force;
•één globaal bord/wereld waar we oplossing in bouwen
•effect afsnijden sub-bomen is onzeker
muis in doolhof, kortste pad paard op schaakbord
•Voor muis in doolhof:
•soms rij van borden nodig schaakspel, 15 puzzel
23
V = Lengte * Breedte ≈ n2 L = Lengte * Breedte ≈ n2 complexiteit = O(VL) door slim te genereren: O(3L) = O(3Lengte*Breedte) dergelijke heuristieken helpen dus echt door afsnijden sub-bomen met predikaat valt hoeveelheid werk vaak nog wel mee
24
6
kanoën
backtrack kanoën
•waar gebeurd:
•oplossing is een rijtje van die situaties •klasse kant met:
2 soldaten moeten een brede rivier oversteken 2 kleine jongentjes willen wel helpen met hun kano maar, in de kano kunnen
aantal jongens hier aantal soldaten hier kant van de kano
•1 of 2 kinderen, of •1 soldaat •dus niet 2 soldaten, of soldaat + kind
•methoden voor: is klaar ? kan over varen ? vaar over constructor
•de oplossing is niet moeilijk, •maar we gaan met backtracking een oplossing zoeken
25
klasse kant
de methode kan
const int Begin = 2; enum InBoot { J, JJ, S }; enum Kano { Hier, Daar };
bool Kant :: kan ( InBoot i ) { if ( kano==Hier ) switch ( i ) { case J: return jongens >0; case JJ: return jongens >1; case S: return soldaten>0; } else // kano==Daar switch ( i ) { case J: return Begin-jongens >0; case JJ: return Begin-jongens >1; case S: return Begin-soldaten>0; } }
class Kant { public: int jongens; int soldaten; Kano kano; Kant ( ): jongens ( Begin ), soldaten ( Begin ), kano ( Hier ) {}; bool klaar ( ) { return soldaten==0 && jongens==Begin && kano==Hier; }; bool kan ( InBoot i ); void vaar ( Kant& naar, InBoot i ); };
26
27
28
7
methode vaar
uitvoer operator <<
void Kant :: vaar ( Kant& naar, InBoot i ) { if ( kano==Hier ) &! { naar.kano = Daar; switch ( i ) { case J: naar.jongens = jongens-1; naar.soldaten = soldaten ; return; case JJ:naar.jongens = jongens-2; naar.soldaten = soldaten ; return; case S: naar.jongens = jongens ; naar.soldaten = soldaten-1; return; } } else ...
ostream& operator << (ostream& os, Kant k) { return os << "Kant: Jongens " << k.jongens << " soldaten " << k.soldaten << ", daar: Jongens " << begin-k.jongens << " soldaten " << begin-k.soldaten << (k.kano==Hier?" kano is hier\n":" kano is daar\n"); }
29
backtracken voor kortste oplossing
toevoegen
•nodig: huidig pad en beste tot nu toe + lengte const int MaxPad = 10*Begin; Kant pad [ MaxPad ]; Kant kortste [ MaxPad ]; int lengte = MaxPad;
30
// kies iets dat zeker lang genoeg is // ktnt: pad // ktnt: lengte
• bewaren van huidige pad in beste tot nu toe: void bewaar ( int l ) { lengte = l; for ( int i=0; i<=l; i+=1 ) kortste [ i ] = pad [ i ]; } 31
void voegtoe ( int i ) { assert ( i<MaxPad-1 ); if ( pad [ i ] . klaar ( ) ) { if ( i < lengte ) bewaar ( i ); type conversie } else for ( InBoot ib=J; ib<=S; ib = InBoot ( ib+1 ) ) if ( pad [ i ] . kan ( ib ) ) { pad [ i ] . vaar ( pad [ i+1 ], ib ); voegtoe ( i+1 ); // backtrack stap is impliciet } }
32
8
programma uitvoeren
toevoegen 2e poging
•resultaat:
void voegtoe ( int i ) { assert ( i<MaxPad-1 ); if ( pad[i].klaar() ) { if ( i
•Assertion failed: i<MaxPad-1
•hoe kan dit ?? •cycle jongentje blijft heen en weer roeien
•wat doen we eraan ? •testen op nieuwe situatie kortste pad kan nooit 2 keer dezelfde toestand bevatten
•andere mogelijkeheid: bovengrens op lengte pad
} } 33
resultaat 0: 1: 2: 3: 4: 5: 6: 7: 8:
Kant: Kant: Kant: Kant: Kant: Kant: Kant: Kant: Kant:
Jongens Jongens Jongens Jongens Jongens Jongens Jongens Jongens Jongens
2 0 1 1 2 0 1 1 2
soldaten soldaten soldaten soldaten soldaten soldaten soldaten soldaten soldaten
2, 2, 2, 1, 1, 1, 1, 0, 0,
daar: daar: daar: daar: daar: daar: daar: daar: daar:
Jongens Jongens Jongens Jongens Jongens Jongens Jongens Jongens Jongens
34
resultaat Begin = 3 0 2 1 1 0 2 1 1 0
soldaten soldaten soldaten soldaten soldaten soldaten soldaten soldaten soldaten
0, 0, 0, 1, 1, 1, 1, 2, 2,
kano kano kano kano kano kano kano kano kano
is is is is is is is is is
hier daar hier daar hier daar hier daar hier
0: Kant: Jongens 3 soldaten 3, daar: Jongens 0 soldaten 0 kano is hier 1: Kant: Jongens 1 soldaten 3, daar: Jongens 2 soldaten 0 kano is daar 2: Kant: Jongens 2 soldaten 3, daar: Jongens 1 soldaten 0 kano is hier 3: Kant: Jongens 0 soldaten 3, daar: Jongens 3 soldaten 0 kano is daar 4: Kant: Jongens 1 soldaten 3, daar: Jongens 2 soldaten 0 kano is hier 5: Kant: Jongens 1 soldaten 2, daar: Jongens 2 soldaten 1 kano is daar 6: Kant: Jongens 2 soldaten 2, daar: Jongens 1 soldaten 1 kano is hier 7: Kant: Jongens 0 soldaten 2, daar: Jongens 3 soldaten 1 kano is daar 8: Kant: Jongens 1 soldaten 2, daar: Jongens 2 soldaten 1 kano is hier 9: Kant: Jongens 1 soldaten 1, daar: Jongens 2 soldaten 2 kano is daar 10: Kant: Jongens 2 soldaten 1, daar: Jongens 1 soldaten 2 kano is hier 11: Kant: Jongens 2 soldaten 0, daar: Jongens 1 soldaten 3 kano is daar 12: Kant: Jongens 3 soldaten 0, daar: Jongens 0 soldaten 3 kano is hier
•ga na dat dit een correcte oplossing is •programma werkt ook voor andere Begin waarden
•kan het net zo snel met 2 jongens en 3 soldaten ? 35
36
9
reflectie
zonder abort
void voegtoe ( int i ) { assert ( i<MaxPad-1 ); if ( pad[i].klaar() ) is het wel nodig om hier { if ( i
void voegtoe ( int i ) { if ( pad[i].klaar() ) { if ( i
}
Nee, maar we af te snijden om takken snel
}
}
} 37
op de zelfde manier
38
heuristieken
•Archimedes: Eureka ! •slimme vondsten
•boer, geit, kool en wolf •kannibalen en missionarissen •...
representatie van de toestand •n-queens: rij van kolomen i.p.v. heel bord
volgorde van nieuwe elementen in voegtoe •eerste koningin op eerste helft van de velden
afbreken van het zoeken •er zit een cycle in het pad
herkennen dat we hier al zijn geweest •we hebben de gespiegelde toestand al gezien
herkennen dat het niets meer zal worden •we hebben al een kortere oplossing gezien
... 39
•maken backtracking vaak net bruikbaar
40
10
moeten we backtracken?
muis in doolhof breadth-first
•alleen als je geen beter algoritme weet: O(nL) •breadth-first zoeken is vaak sneller, maar kan veel administratie vergen •breadth-first: doorzoek heel niveau voordat je naar kinderen kijkt.
•idee: merk alle velden met afstand tot de kaas op veld van de kaas is afstand 0 op alle buren is afstand 1 op buren van veld met n is afstand hoogstens n+1
•Analyse: buren van veld met afstand n vinden en merken: O(Lengte*Breedte) = O(n2) = O(V) Alle L velden merken: O(L * V) = O(n4)
•Onthouden wat te merken veld vinden in O(1) totaal L * O(1) = O(L) = O(n2) !! 41
breadth-first doolhof
breadth-first doolhof 2
const int Muur=-1, Kaas=0, Vrij=Oneindig; void merkVeld ( int i, int j, int n ) { if ( doolhof[i][j] > n ) doolhof[i][j] = n; }
42
void vulDoolhof ( ) { bool gevonden = true; // er is een veld met afstand n for ( int n=0; gevonden ;n++ ) { iets slimmer dan n
in het begin alles Oneindig (groot)
void merkVelden ( int i, int j, int n ) { merkVeld ( i+1, j, n ); merkVeld ( i-1, j, n ); merkVeld ( i, j+1, n ); merkVeld ( i, j-1, n ); } 43
44
11
breadth-first doolhof 3
breadth-first doolhof resultaat ##################### ### 4 5 6 ### 8 ### ### 3 ### 5 ### 7 ### ### 2 3 4 5 6 ### ### 1 2 3 ### 7 ### ### 0 ### 4 5 6 ### ### 1 ### 5 6 7 ### #####################
void toonWeg ( ) { for ( int i = 0; i < Lengte; i++ ) { for ( int j = 0; j < Breedte; j++ ) switch ( doolhof [i][j] ) { case Vrij: cout << " "; break; case Muur: cout << "###"; break; default: cout << setw(2) << doolhof[i][j] << ' ';break; } cout << endl; } }
•kortste weg van ieder punt direct af te lezen •door aanpassen doolhof is administratie klein •met bijhouden velden (queue) gaat het nog beter •denk twee keer na voor je gaat programmeren !! •reflectie is belangrijk !!! 45
46
Wat hebben we gedaan • •
dictaat: H 12 boek: backtracking komt niet voor
•
Zoeken van oplossingen: • •
brute force:
• •
bouw complete kandidaat-oplossing test of kandidaat-oplossing voldoet
backtrack:
•
•
in principe boom van oplossingen depth-first: bouw steeds één tak; rij i.p.v. boom
test bij iedere toevoeging of het nog wat kan worden
Opgave: weer backtracking 47
12
