Pe scurt
Backtracking este o metodă sistematică de căutare a soluțiilor pentru probleme de combinatorică, bazată pe construirea progresivă a candidatului și revenirea atunci când o ramură nu poate duce la o soluție validă. Algoritmul folosește un vector stivă și o funcție recursivă care încearcă plasarea elementelor cu respectarea condițiilor specifice fiecărui tip de problemă (permutări, combinări, aranjamente). Eficiența metodei constă în tăierea devreme a ramurilor imposibile, reducând astfel spațiul de căutare.
Generarea permutărilor
Permutările reprezintă aranjamente ordonate ale unor elemente distincte, fără repetiții. Pentru o mulțime de n elemente, se generează toate permutările posibile, în număr de n!.
- Se folosește un vector de frecvență pentru a marca elementele deja utilizate
- La fiecare pas se verifică dacă elementul candidat nu a mai fost folosit
- Algoritmul se oprește când vectorul soluție atinge lungimea n
- Exemplu: Pentru mulțimea {1,2,3} se obțin 6 permutări: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
Generarea combinarilor
Combinațiile sunt submulțimi de k elemente dintr-o mulțime de n, fără a ține cont de ordinea elementelor. Numărul acestora este C(n,k).
- Se impune o ordine crescătoare a indicilor – elementul curent trebuie să fie mai mare decât ultimul element din soluție
- Vectorul soluție are lungimea k
- Exemplu: Pentru combinări de 3 elemente din {1,2,3,4} se obțin 4 combinații: (1,2,3), (1,2,4), (1,3,4), (2,3,4)
Generarea aranjamentelor
Aranjamentele sunt grupări ordonate de k elemente din n, cu n!/(n-k)! posibilități.
- Se verifică atât unicitatea elementelor, cât și eventuale criterii suplimentare
- Se folosește vectorul de frecvență pentru a evita repetițiile
- Exemplu: Pentru aranjamente de 2 elemente din {1,2,3} se obțin 6 aranjamente: (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)
Mecanismul algoritmului backtracking
Algoritmul backtracking pentru aceste probleme folosește
- Un vector stivă (soluție) care stochează elementele alese
- O funcție recursivă care, la fiecare pas, încearcă să plaseze un element candidat
- Condiții specifice de validare pentru fiecare tip de problemă
- Mecanismul de revenire (backtrack) atunci când o ramură nu poate duce la o soluție validă
- Afișarea configurației când lungimea vectorului soluție atinge dimensiunea dorită
Verifică-te!
- Care este diferența principală între condițiile de validare pentru generarea permutărilor și cea pentru generarea combinarilor?
- Câte aranjamente de 3 elemente se pot genera dintr-o mulțime de 5 elemente?
- Ce rol joacă vectorul de frecvență în algoritmul de generare a permutărilor?