Backtracking în C++

Ce este Backtracking?

O tehnică de rezolvare a problemelor prin explorarea sistematică a tuturor soluțiilor posibile, cu revenire (backtrack) când o cale nu duce la soluție.

Șablonul General

Copiază
1void backtrack(int pas) {
2    if (pas == n + 1) {
3        // Soluție completă - afișare
4        afisare();
5        return;
6    }
7    
8    for (fiecare valoare posibilă v) {
9        if (valid(v)) {
10            solutie[pas] = v;
11            backtrack(pas + 1);
12            // Revenire (implicit)
13        }
14    }
15}

Permutări

Copiază
1#include <iostream>
2using namespace std;
3
4int n;
5int sol[100];
6bool folosit[100];
7
8void afisare() {
9    for (int i = 1; i <= n; i++)
10        cout << sol[i] << " ";
11    cout << endl;
12}
13
14void permutari(int pas) {
15    if (pas == n + 1) {
16        afisare();
17        return;
18    }
19    
20    for (int i = 1; i <= n; i++) {
21        if (!folosit[i]) {
22            sol[pas] = i;
23            folosit[i] = true;
24            permutari(pas + 1);
25            folosit[i] = false;
26        }
27    }
28}
29
30int main() {
31    cin >> n;
32    permutari(1);
33    return 0;
34}

Combinări C(n,k)

Copiază
1void combinari(int pas, int ultimul) {
2    if (pas == k + 1) {
3        afisare();
4        return;
5    }
6    
7    for (int i = ultimul + 1; i <= n - k + pas; i++) {
8        sol[pas] = i;
9        combinari(pas + 1, i);
10    }
11}

Problema Reginelor

Copiază
1int n;
2int col[100];    // col[i] = coloana reginei de pe linia i
3bool ocupatCol[100], ocupatDiag1[200], ocupatDiag2[200];
4
5bool valid(int linie, int coloana) {
6    return !ocupatCol[coloana] && 
7           !ocupatDiag1[linie - coloana + n] && 
8           !ocupatDiag2[linie + coloana];
9}
10
11void regine(int linie) {
12    if (linie == n + 1) {
13        afisare();
14        return;
15    }
16    
17    for (int j = 1; j <= n; j++) {
18        if (valid(linie, j)) {
19            col[linie] = j;
20            ocupatCol[j] = true;
21            ocupatDiag1[linie - j + n] = true;
22            ocupatDiag2[linie + j] = true;
23            
24            regine(linie + 1);
25            
26            ocupatCol[j] = false;
27            ocupatDiag1[linie - j + n] = false;
28            ocupatDiag2[linie + j] = false;
29        }
30    }
31}

Complexitate

Backtracking are complexitate exponențială în cel mai rău caz, dar poate fi optimizat prin:

• •Tăierea ramurilor (pruning)
• •Alegerea inteligentă a ordinii variabilelor