Backtracking
Schema generală, ce înseamnă fiecare parte din ea, și cum o adaptezi de la o problemă la alta.
Ce fel de probleme rezolvă
Backtracking-ul generează toate soluțiile unei probleme, când o soluție este o succesiune de alegeri.
Exemple tipice: toate permutările a n obiecte, toate submulțimile, toate modurile de a așeza dame pe o tablă fără să se atace, toate drumurile într-un labirint.
Ideea în cuvinte: construiesc soluția pas cu pas. La fiecare pas încerc, pe rând, toate valorile posibile. Dacă valoarea aleasă mai poate duce la o soluție, merg mai departe. Dacă nu, o abandonez și o încerc pe următoarea. Când nu mai am ce încerca la pasul curent, mă întorc la pasul anterior și continui de acolo. De aici vine și numele metodei.
Schema
int st[20], n;
void back(int k) {
for (int i = 1; i <= n; i++) { // valorile posibile pe poziția k
st[k] = i;
if (valid(k)) { // se poate?
if (solutie(k))
afisare(k);
else
back(k + 1); // merg mai departe
}
}
}apelată cu back(1).
Schema are patru piese:
st este stiva, adică soluția în construcție. st[k] este alegerea făcută la pasul k.
valid(k) conține condițiile de continuare. Verifică dacă alegerea de pe poziția k este compatibilă cu cele dinainte. Aici stă toată diferența dintre probleme.
solutie(k) răspunde la întrebarea „am terminat?”. De obicei este k == n.
afisare(k) spune ce faci cu o soluție găsită: o afișezi, o numeri sau o compari cu cea mai bună de până acum.
De la o problemă la alta se schimbă aproape numai valid. Restul schemei rămâne la fel.
De ce funcționează întoarcerea
Nu trebuie să „ștergi" nimic când te întorci. Când bucla for trece la valoarea următoare, st[k] = i suprascrie oricum vechea alegere, iar pozițiile de după k nu mai contează, pentru că vor fi rescrise la următoarea coborâre.
De aceea schema este atât de scurtă: recursivitatea ține minte singură unde ai rămas la fiecare nivel.
Primul exemplu: permutările
Toate modurile de a aranja numerele de la 1 la n, fiecare o singură dată.
Condiția de validitate: valoarea de pe poziția k nu trebuie să apară mai devreme.
#include <iostream>
using namespace std;
int st[20], n;
bool valid(int k) {
for (int i = 1; i < k; i++)
if (st[i] == st[k])
return false;
return true;
}
void afisare() {
for (int i = 1; i <= n; i++)
cout << st[i] << " ";
cout << "\n";
}
void back(int k) {
for (int i = 1; i <= n; i++) {
st[k] = i;
if (valid(k)) {
if (k == n) afisare();
else back(k + 1);
}
}
}
int main() {
cin >> n;
back(1);
return 0;
}Pentru n = 3 afișează, în această ordine: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.
Ordinea nu este întâmplătoare. Bucla încearcă valorile crescător, deci soluțiile ies în ordine lexicografică. Enunțurile cer des exact această ordine, iar schema o produce fără niciun efort în plus.
Cum urmărești pe hârtie
La Subiectul I apar itemi de tipul „care este a k-a soluție generată" sau „câte soluții încep cu 2".
Desenează arborele. Nivelul 1 are câte o ramură pentru fiecare valoare posibilă pe prima poziție. Sub fiecare dintre ele desenezi ramurile pentru a doua poziție, și așa mai departe. Ramurile respinse de valid se taie.
Parcurgi arborele în adâncime, de la stânga la dreapta. Aceasta este exact ordinea în care apar soluțiile.
Marcarea, ca alternativă la valid
Verificarea „a mai apărut valoarea?" costă k pași de fiecare dată. O poți face instantaneu, cu un vector care reține ce valori sunt deja folosite:
bool folosit[20];
void back(int k) {
for (int i = 1; i <= n; i++)
if (!folosit[i]) {
st[k] = i;
folosit[i] = true;
if (k == n) afisare();
else back(k + 1);
folosit[i] = false; // esențial
}
}Atenție la ultima linie: la întoarcere, marcajul se șterge. Altfel valoarea rămâne blocată pentru toate ramurile următoare și pierzi majoritatea soluțiilor.
Regula generală: orice modificare făcută înainte de apelul recursiv trebuie desfăcută după el.
Costul
Backtracking-ul este scump prin natura lui. Un șir de n elemente are n! permutări. Pentru n = 10 sunt 3,6 milioane, ceea ce e acceptabil. Pentru n = 15 sunt peste o mie de miliarde, ceea ce e imposibil.
Implementarea nu are nicio vină: problema chiar are atâtea soluții. De aceea enunțurile de backtracking au întotdeauna n mic.
Poți în schimb să tai devreme. Cu cât valid respinge mai repede o ramură fără viitor, cu atât explorezi mai puțin. Esența metodei este verificarea la fiecare pas, nu doar la final.
De reținut
- Backtracking = construiesc pas cu pas, verific, merg mai departe sau mă întorc.
- Schema este mereu aceeași. Se schimbă doar
valid. - Verifică la fiecare pas, nu la final. Altfel generezi totul degeaba.
- Cu marcaje, ține minte să le ștergi la întoarcere.
- Soluțiile ies în ordine lexicografică dacă încerci valorile crescător.
- Costul este exponențial, de aceea enunțurile dau
nmic.