Backtracking recursiv

În backtracking recursiv, un apel reprezintă un nivel al construcției. Bucla încearcă fiecare candidat, iar un apel nou continuă soluția parțială. Când apelul revine, următorul candidat este încercat. Condiția de oprire apare când soluția are lungimea cerută.

În varianta recursivă, un apel bt(k) corespunde nivelului $k$ al construcției. Dacă soluția parțială este completă ($k$ a depășit numărul de niveluri), se prelucrează soluția (de obicei se afișează) și apelul se încheie. Altfel, un ciclu parcurge candidații nivelului $k$; pentru fiecare candidat acceptat se memorează în $x_k$ și se apelează bt(k + 1). Când apelul interior revine, ciclul continuă cu următorul candidat. Instrucțiunea return din cazul complet încheie doar acel apel, nu și apelurile deja active: explorarea reia buclele lor. Dacă soluția parțială folosește o stare modificabilă, de pildă un vector de marcaje „valoare folosită”, modificările făcute înainte de apel se anulează după revenire, ca starea să fie corectă pentru candidatul următor. Adâncimea recursiei este numărul de niveluri, deci stiva ocupă spațiu proporțional cu el.

Exemplul 1 — perechi din $\{1,2\}$ fără repetiție.

#include <iostream>
using namespace std;
int x[2];
void gen(int k) {
    if (k == 2) {
        cout << x[0] << x[1] << " ";
        return;
    }
    for (int c = 1; c <= 2; ++c) {
        if (k == 1 && c == x[0]) continue;
        x[k] = c;
        gen(k + 1);
    }
}
int main() {
    gen(0);
    return 0;
}

Apelul gen(0) încearcă 1 pe primul nivel; gen(1) încearcă 1 (respins, pentru că este egal cu x[0]) și apoi 2, deci se afișează 12. Apoi gen(0) încearcă 2, iar gen(1) acceptă doar 1: se afișează 21. Programul afișează 12 21.

Exemplul 2 — arborele apelurilor. Pentru permutările mulțimii $\{1,2,3\}$, cu un vector folosit care marchează valorile deja puse, apelul bt(1) produce 3 apeluri pe nivelul 2, 6 pe nivelul 3 și 6 pe nivelul 4 (frunzele, câte unul pentru fiecare permutare). Cu apelul inițial, numărul total de apeluri este $1+3+6+6=16$. Pentru permutările lui $\{1,2,3,4\}$ sunt 24 de frunze și 65 de apeluri în total. Desenarea arborelui apelurilor ajută la urmărirea ordinii în care sunt încercați candidații.

void bt(int k) {
    if (k > n) { /* soluție completă */ return; }
    for (int c = 1; c <= n; ++c)
        if (!folosit[c]) {
            folosit[c] = true;
            x[k] = c;
            bt(k + 1);
            folosit[c] = false;
        }
}

Marcajul folosit[c] = false după revenire este esențial: fără el, valoarea ar rămâne blocată pentru toate ramurile următoare și programul ar genera prea puține soluții.

Condiții de continuare în apel. Verificarea candidatului se face înainte de apelul următor, nu după el: dacă un candidat este respins, nu se mai creează niciun apel pentru el. Aceasta reduce spațiul explorat și numărul de apeluri. Pentru perechi fără repetiție din $\{1,2\}$ există 1 apel inițial, 2 apeluri pe nivelul 1 și 2 apeluri pe nivelul 2: în total 5 apeluri, dar numai 2 soluții.

Exemplul 3 — oprire anticipată. Dacă se cere o singură soluție, apelurile se pot opri după prima: bt întoarce o valoare logică, iar ciclul se încheie imediat ce un apel interior raportează succes. Pentru toate soluțiile, execuția continuă până la epuizarea ciclurilor tuturor nivelurilor.

Urmărirea apelurilor pentru $n=3$. bt(1) încearcă $c=1$ și marchează folosit[1]. bt(2) încearcă $c=1$ (respins, marcat), apoi $c=2$, iar bt(3) ajunge la $c=3$. bt(4) are $k>n$, deci se afișează 123 și apelul se încheie. La revenire se șterg marcajele lui 3 și 2, iar bt(2) încearcă $c=3$; urmează bt(3) cu $c=2$ și se afișează 132. Ordinea completă este 123 132 213 231 312 321.

Costul. Arborele are $n!$ frunze, iar afișarea unei soluții costă $n$ operații, deci timpul este de ordinul $n\cdot n!$, iar memoria stivei este de ordinul $n$.

Desenează arborele apelurilor și notează ordinea candidaților. La fiecare nod, condiția de validitate poate tăia o ramură. return în cazul complet încheie acel apel, nu toate apelurile deja active; explorarea reia buclele lor. Când subiectul cere numărul de apeluri, include apelul inițial și apelurile care ajung în cazul complet, dar nu și candidații respinși de condiție, pentru că aceștia nu produc apel.

Exemplu în formatul examenului. Câte apeluri ale funcției bt se execută în total (inclusiv apelul bt(1) din main) în programul de mai jos?

#include <iostream>
using namespace std;
int n = 3, x[5];
bool folosit[5];
void bt(int k) {
    if (k > n) return;
    for (int c = 1; c <= n; ++c)
        if (!folosit[c]) {
            folosit[c] = true;
            x[k] = c;
            bt(k + 1);
            folosit[c] = false;
        }
}
int main() {
    bt(1);
    return 0;
}

• a) 6
• b) 10
• c) 15
• d) 16

Răspunsul corect este d). Pe nivelul 1 există un apel. Fiecare apel de pe nivelul 1 generează 3 apeluri pe nivelul 2, fiecare dintre acestea generează 2 apeluri pe nivelul 3 (rămân 2 valori nefolosite), iar fiecare apel de pe nivelul 3 generează 1 apel pe nivelul 4, unde $k>n$ și funcția se încheie imediat. Numărul de apeluri pe niveluri este $1$, $3$, $6$ și $6$, în total $1+3+6+6=16$. Varianta a) numără doar frunzele, adică permutările.

Al doilea exemplu: condiția taie ramuri. Ce se afișează și câte apeluri se fac dacă în funcția bt de mai sus, cu $n=3$, se înlocuiește condiția !folosit[c] cu c != x[k - 1] pentru $k>1$, iar valorile $c$ merg doar de la 1 la 2?

Pe nivelul 1 se încearcă 1 și 2, fără restricție. Pe nivelurile 2 și 3 rămâne un singur candidat, cel diferit de valoarea anterioară. Se afișează 121 212, adică 2 soluții. Apelurile sunt $1+2+2+2=7$: unul pe nivelul 1, două pe nivelul 2, două pe nivelul 3 și două pe nivelul 4.

Greșeli frecvente

• Greșit: după revenirea dintr-un apel, valoarea marcată ca folosită rămâne marcată.
  Corect: marcajul se anulează, ca valoarea să poată fi folosită în alte ramuri.
• Greșit: return din cazul complet oprește tot backtracking-ul.
  Corect: încheie numai apelul curent; apelurile active continuă.
• Greșit: numărul de apeluri este egal cu numărul de soluții.
  Corect: apelurile includ și nivelurile intermediare.

Înainte și după