Informatică Programare
Algoritmi backtracking C++
Algoritmii backtracking în C++ rezolvă probleme prin încercarea tuturor posibilităților și revenirea la decizii anterioare dacă o soluție parțială nu duce la rezultat. Sunt folosiți pentru probleme combinatorii ca permutările sau problema reginelor.
Pași generali
- 1 Alege o opțiune La fiecare pas, selectează o valoare posibilă dintr-un set (ex: un număr pentru o permutare).
- 2 Verifică validitatea Dacă opțiunea respectă constrângerile (ex: numărul nu a fost folosit), continuă; altfel, renunță.
- 3 Apelează recursiv Reapelează funcția pentru următorul pas, construind soluția parțială.
- 4 Revino (backtrack) După revenirea din apelul recursiv, anulează ultima alegere pentru a încerca altă opțiune.
Exemplu: generare permutări
- Cod de bază void backtrack(int k, int n, vector<int>& sol, vector<bool>& folosit) { if (k == n) afiseaza(sol); else for (int i = 1; i <= n; i++) if (!folosit[i]) { sol[k] = i; folosit[i] = true; backtrack(k+1, n, sol, folosit); folosit[i] = false; } }
- Parametri k = pasul curent, n = lungimea permutării, sol = vector cu soluția parțială, folosit = vector boolean pentru elemente utilizate.
- Complexitate O(n!) pentru permutări, deoarece generează toate aranjamentele.
Optimizează backtracking-ul prin tăieri (pruning) pentru a reduce numărul de încercări.