Informatică Programare
Backtracking algoritmi C++
Backtracking-ul în C++ este o tehnică algoritmică care explorează toate soluțiile posibile ale unei probleme prin încercare și revenire. Funcționează pe principiul că construiește soluția pas cu pas și revine la pasul anterior când o opțiune nu duce la rezultat valid. Este folosit pentru probleme combinatorii precum permutări, regine sau labirinturi.
Cum funcționează backtracking-ul
- 1 Pasul 1: Inițializare Definești o funcție recursivă care primește parametrii pentru starea curentă, cum ar fi poziția în soluție sau un vector pentru elemente selectate.
- 2 Pasul 2: Verificare condiție de oprire În funcție, verifici dacă ai ajuns la o soluție completă; dacă da, o afișezi sau o procesezi.
- 3 Pasul 3: Generare opțiuni Pentru starea curentă, generezi toate opțiunile posibile (de exemplu, numerele 1 la n pentru permutări).
- 4 Pasul 4: Testare și revenire Pentru fiecare opțiune, verifici dacă este validă; dacă da, o adaugi la soluție și apelezi recursiv funcția, apoi o elimini pentru a încerca alte variante.
Exemplu practic în C++: Generarea permutărilor
- Codul de bază #include <iostream> #include <vector> using namespace std; void backtrack(vector<int>& perm, vector<bool>& used, int n) { if (perm.size() == n) { for (int num : perm) cout << num << ' '; cout << endl; return; } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; perm.push_back(i); backtrack(perm, used, n); perm.pop_back(); used[i] = false; } } }
- Cum rulează pentru n=3 Pentru n=3, algoritmul generează toate cele 6 permutări: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.
- Complexitate Complexitatea timp este O(n!), deoarece explorează toate permutările; spațial, folosește O(n) pentru stocarea soluției și vectorul de vizitare.
Exersează backtracking-ul pe probleme simple ca permutări sau combinări înainte de a trece la cele mai complexe.