Metoda backtracking (generarea permutarilor, aranjamentelor, combinarilor)

Metoda backtracking este o tehnică fundamentală de căutare sistematică în spațiul soluțiilor, utilizată pentru a genera toate configurațiile posibile care satisfac anumite condiții. Ea se bazează pe construirea progresivă a soluțiilor, pas cu pas, și pe revenirea (backtracking) atunci când o ramură nu mai poate duce la o soluție validă. În contextul combinatoric, backtracking este perfect pentru generarea permutărilor, aranjamentelor și combinarilor.

Generarea permutărilor presupune aranjarea tuturor elementelor unei mulțimi într-o anumită ordine. De exemplu, pentru mulțimea {1,2,3}, permutările sunt: 123, 132, 213, 231, 312, 321. Algoritmul backtracking construiește un vector soluție în care fiecare poziție (de la 1 la n) primește un element diferit, iar la fiecare pas verificăm dacă elementul ales a mai fost folosit (prin vector de prezență).

Când ajungem la poziția n+1, soluția este completă și o afișăm, apoi reluăm căutarea pentru alte variante.

Generarea aranjamentelor (de n luate câte k) este similară, dar se oprește după k elemente (k ≤ n). Se generează toate submulțimile ordonate de k elemente din cele n. De exemplu, pentru n=3, k=2, aranjamentele sunt: 12, 13, 21, 23, 31, 32. Algoritmul construiește un vector de k elemente, cu aceleași restricții de unicitate, și afișează soluția când s-au completat k poziții.

Generarea combinarilor (de n luate câte k) generează submulțimi neordonate, adică nu contează ordinea elementelor. De exemplu, pentru n=3, k=2, combinarile sunt: 12, 13, 23. Pentru a evita generarea permutărilor aceleiași submulțimi, impunem ca elementele din vectorul soluție să fie strict crescătoare.

Astfel, la pasul i, alegem o valoare mai mare decât cea de pe poziția anterioară, iar intervalul de valori permise este [1, n] dar cu această restricție.

Algoritmul general backtracking are următoarea structură: se definește o funcție recursivă care primește ca parametru indicele curent (de regulă, pas). În cadrul funcției, se parcurg toate valorile posibile pentru poziția respectivă. Pentru fiecare valoare, se verifică dacă aceasta respectă condițiile de continuare (de exemplu, dacă nu a mai fost folosită, sau dacă este mai mare decât precedentul).

Dacă da, se adaugă valoarea în vector, se marchează (dacă e cazul) și se apelează recursiv pentru pasul următor. După revenirea din apel, se anulează marcarea (backtrack). Când s-a atins pasul final (n+1 pentru permutări, k+1 pentru aranjamente/combinații), se procesează soluția.

Complexitatea este factorială sau combinatorică, fiind utilizată în probleme de optimizare, generare sau căutare exhaustivă. Elevii trebuie să înțeleagă cum se implementează condițiile de validare (de exemplu, vector de frecvență pentru unicitate, sau ordine crescătoare pentru combinări). Exemplele clasice din manualele de BAC includ generarea permutărilor, a aranjamentelor și a combinarilor, dar și probleme precum 'reginele' sau 'parantezele'.

În concluzie, metoda backtracking este esențială pentru rezolvarea problemelor de tip 'generare' și apare frecvent la evaluări și concursuri.

Exemple

• Exemplul 1: Generarea permutărilor mulțimii {1,2,3}. Vom construi un vector sol[4] (indici de la 1 la 3) și un vector folosit[4] inițializat cu 0. Pașii: pentru poziția 1, încercăm valoarea 1 -> marcam folosit[1]=1, apel recursiv poziția 2. La poziția 2, încercăm valorile 1 (deja folosit), 2 (disponibil) -> adăugăm 2, marcăm, apel poziția 3. La poziția 3, încercăm 1,2 (folosite), 3 (disponibil) -> adăugăm 3, marcăm, apel poziția 4 -> soluție completă [1,2,3] -> afișăm. Apoi revenim, anulăm marcarea lui 3, încercăm alte valori inexistente, revenim, anulăm 2, încercăm 3 la poziția 2 etc. Se vor genera toate cele 6 permutări.
• Exemplul 2: Aranjamente de 4 luate câte 2. n=4, k=2. Vectorul sol va avea 2 poziții. Folosim același mecanism de marcare. Pentru poziția 1: încercăm 1 -> marcam, apel poziția 2. La poziția 2: încercăm 2,3,4 pe rând. Prima soluție: [1,2]. A doua: [1,3]. A treia: [1,4]. Apoi revenim la poziția 1, încercăm 2 etc. Se vor genera 4*3=12 aranjamente. Observație: ordinea contează, [1,2] și [2,1] sunt distincte.
• Exemplul 3: Combinări de 4 luate câte 2. n=4, k=2. Pentru a genera submulțimi neordonate, impunem ca sol[1] < sol[2]. La poziția 1, încercăm valori de la 1 la n-k+1 (deci 1,2,3). Pentru fiecare, la poziția 2, încercăm valori mai mari decât poziția anterioară. De exemplu, poziția 1 = 1, poziția 2 poate fi 2,3,4 -> soluțiile: [1,2], [1,3], [1,4]. Apoi poziția 1 = 2, poziția 2 = 3,4 -> [2,3], [2,4]; apoi poziția 1 = 3, poziția 2 = 4 -> [3,4]. Total 6 combinații.

Concepte cheie: Backtracking: construire treptată a soluțiilor cu revenire la eșec, Generarea permutărilor: n! soluții, vector de frecvență pentru unicitate, Generarea aranjamentelor: n!/(n-k)! soluții, similar permutărilor dar cu oprire la k elemente, Generarea combinarilor: C(n,k) soluții, restricție de ordine crescătoare, Condiții de validare specifice fiecărui tip de generare