Pe scurt
Metoda backtracking este o tehnică recursivă de explorare a tuturor soluțiilor posibile, construind treptat un vector soluție și renunțând la căile nepromițătoare. În contextul bacalaureatului, se aplică pentru generarea permutărilor, aranjamentelor și combinarilor unor elemente, utilizând condiții specifice de validare (vector boolean pentru permutări/aranjamente, ordine crescătoare pentru combinări). Algoritmii au complexitate exponențială, fiind acceptați pentru valori mici ale lui n (de obicei n ≤ 10-12).
Principiul de bază al metodei backtracking
- Se construiește un vector soluție (notat 'st' pentru „stivă”) pas cu pas
- La fiecare pas se verifică dacă valoarea curentă respectă condițiile problemei
- Dacă condițiile sunt îndeplinite, se avansează la pasul următor
- Dacă nu, se încearcă următoarea valoare
- Când se ajunge la nivelul final (k = n pentru permutări, sau lungimea specificată pentru aranjamente/combinări), se afișează soluția
- Se revine la nivelul anterior pentru a încerca următoarea valoare, până la epuizarea tuturor posibilităților
Generarea permutărilor
- Se generează ordonări distincte ale tuturor elementelor mulțimii
- Se folosește un vector boolean „vizitat” care marchează elementele deja folosite pentru a evita repetițiile
- Exemplu: Generarea permutărilor mulțimii {1,2,3}
- Se implementează funcția recursivă 'back(k)' care construiește vectorul st[1..n]
- Se inițiază cu k=1
- La fiecare pas, se încearcă valori de la 1 la n
- Dacă valoarea nu a fost deja folosită (se verifică vectorul boolean 'viz'), se adaugă în st[k], se marchează ca folosită, se apelează back(k+1), iar după revenire se demarchează
- Când k = n+1, se afișează st[1..n]
- Rezultat: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
Generarea aranjamentelor
- Se generează ordonări distincte a k elemente din n
- Similar cu permutările, dar se oprește când s-au selectat k elemente
- Se menține vectorul boolean „viz” pentru a evita repetițiile
- Exemplu: Generarea aranjamentelor de 3 luate câte 2 (n=3, k=2)
- Se oprește când k = 3 (s-au selectat 2 elemente)
- Rezultat: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)
Generarea combinarilor
- Se generează submulțimi de k elemente, fără ordine
- Se evită repetițiile impunând ca valorile să fie strict crescătoare (sau descrescătoare) în vectorul soluție
- Nu este nevoie de vector boolean „viz” deoarece condiția de creștere previne repetițiile
- Se încearcă valori de la ultima valoare + 1 (sau de la 1 pentru primul pas)
- Exemplu: Generarea combinarilor de 4 luate câte 2 (n=4, k=2)
- Vectorul soluție se construiește cu valori strict crescătoare
- Rezultat: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
Complexitatea algoritmilor
- Permutări: O(n!)
- Aranjamente: O(n!/(n-k)!)
- Combinări: O(C(n,k))
- Este acceptată în probleme cu n relativ mic (de obicei n ≤ 10-12)
Concepte cheie
- Recursivitate și stivă (vector soluție)
- Condiții de continuare (validare) și de oprire (soluție completă)
- Marcarea elementelor folosite (vector boolean) pentru permutări/aranjamente
- Ordinea crescătoare pentru combinări (evitarea repetițiilor)
- Backtracking = renunțarea la soluții parțiale nepromițătoare
Verifică-te!
- Ce diferență esențială există între generarea aranjamentelor și generarea combinarilor în ceea ce privește condițiile de validare?
- De ce nu este necesar un vector boolean „vizitat” la generarea combinarilor, dar este obligatoriu la permutări?
- Când se oprește procesul recursiv și se afișează o soluție în cazul generării permutărilor?