Backtracking iterativ

Varianta iterativă păstrează explicit nivelul curent și candidații încercați la fiecare nivel. Când nu mai există candidat valid, scade nivelul și încearcă următoarea alegere acolo. Pentru perechi din $\{1,2\}$ fără repetiție, nivelul 1 alege 1, nivelul 2 alege 2 și afișează 12; apoi revine, alege 2 la nivelul 1 și 1 la nivelul 2, afișând 21.

În varianta iterativă a backtracking-ului, nivelul curent $k$ și soluția parțială $x_1,\dots ,x_n$ sunt variabile explicite, iar un singur ciclu înlocuiește apelurile recursive. Valoarea $x_k=0$ înseamnă că pe nivelul $k$ nu a fost încă încercat niciun candidat. Cât timp $k\ge 1$: dacă pe nivelul $k$ mai există candidați netestați ($x_k<n$), se trece la următorul, $x_k=x_k+1$, și se verifică dacă soluția parțială este validă; dacă este validă și $k=n$, se afișează soluția, iar dacă $k<n$, se avansează la nivelul $k+1$ cu $x_{k+1}=0$. Dacă pe nivelul $k$ candidații s-au epuizat, se revine la nivelul $k-1$, adică $k$ scade cu 1. Condiția de validitate este separată de mecanismul de avans și revenire, ca să poată fi schimbată de la o problemă la alta.

Exemplul 1 — permutările lui $\{1,2,3\}$.

#include <iostream>
using namespace std;
int n = 3, x[10];
bool valid(int k) {
    for (int i = 1; i < k; ++i)
        if (x[i] == x[k]) return false;
    return true;
}
int main() {
    int k = 1;
    x[1] = 0;
    while (k > 0) {
        if (x[k] < n) {
            ++x[k];
            if (valid(k)) {
                if (k == n) {
                    for (int i = 1; i <= n; ++i) cout << x[i];
                    cout << " ";
                } else {
                    ++k;
                    x[k] = 0;
                }
            }
        } else
            --k;
    }
    return 0;
}

Programul afișează 123 132 213 231 312 321 . Urmărirea începutului: $k=1$, $x_1$ devine 1 și este valid, deci $k=2$ cu $x_2=0$; $x_2$ devine 1, dar $x_2=x_1$, deci nu este valid și se încearcă următorul candidat; $x_2=2$ este valid, deci $k=3$; $x_3$ ia valorile 1 și 2, ambele invalide, apoi 3, valid: se afișează 123. Cum $x_3=n$, nu mai există candidați pe nivelul 3 și $k$ scade la 2; acolo $x_2$ ia valoarea 3, valid, iar nivelul 3 produce 132. În total, $x_k$ este incrementat de 30 de ori până la epuizarea spațiului pentru $n=3$.

Exemplul 2 — generarea în ordine. Fiindcă pe fiecare nivel candidații cresc de la 1, soluțiile apar în ordine lexicografică crescătoare. Pentru $n=4$ primele patru permutări sunt 1234, 1243, 1324 și 1342. Resetarea $x_{k+1}=0$ la intrarea pe un nivel este obligatorie: dacă ar lipsi, nivelul ar relua de la valoarea rămasă de la ultima vizită și ar rata candidați.

Cum se citește scheletul. Variabila k joacă rolul vârfului unei stive: ++k este intrarea într-un nivel nou, iar --k este ieșirea din nivelul epuizat. Ciclul se termină când $k$ ajunge la 0, adică atunci când nivelul 1 și-a epuizat candidații. Fiecare soluție completă se obține dintr-un drum de lungime $n$ de la rădăcina arborelui de căutare.

Exemplul 3 — alt tip de problemă cu același schelet. Pentru produsul cartezian, în care orice valoare este permisă pe orice nivel, funcția valid întoarce mereu true; scheletul rămâne neschimbat. Pentru aranjamente de $p$ elemente, condiția de afișare devine $k=p$ (cu $p$ lungimea cerută), nu $k=n$.

Exemplul 4 — aranjamente de 3 luate câte 2. Se pornește de la scheletul permutărilor și se schimbă un singur test: soluția este completă la nivelul $p=2$, deci if (k == p) înlocuiește if (k == n). Pentru $n=3$ și $p=2$ se afișează 12 13 21 23 31 32, adică $3\cdot 2=6$ soluții. Pentru $x_1=1$, valoarea $x_2=1$ este respinsă (egală cu $x_1$), iar $x_2=2$ și $x_2=3$ dau 12 și 13; apoi $x_2=n$, nivelul 2 este epuizat, $k$ scade la 1 și $x_1$ devine 2.

Urmărește perechea $(k,x_k)$ și motivul fiecărei reveniri. Dacă după epuizarea candidaților nu resetezi poziția, la o nouă intrare pe nivel căutarea ar porni dintr-o valoare greșită. Numărul soluțiilor depinde de restricții, nu de faptul că implementarea este iterativă. Testul x[k] < n decide dacă mai există candidați; un test x[k] <= n ar produce valoarea $n+1$, în afara domeniului. Când subiectul cere a $m$-a soluție, numără soluțiile afișate, nu avansările. Dacă pe un nivel candidații sunt încercați descrescător (de la $n$ la 1), soluțiile apar în ordine lexicografică descrescătoare, iar prima este 4321 pentru $n=4$. Dacă funcția de validitate lipsește, algoritmul generează toate șirurile din $\{1,\dots ,n{\}}^n$, adică $n^n$ șiruri: 27 pentru $n=3$ în loc de 6. Pentru $n=1$ există o singură soluție, 1: nivelul 1 alege 1, soluția se afișează, apoi $x_1=n$ epuizează nivelul și $k$ devine 0.

Exemplu în formatul examenului. Un algoritm iterativ de tip backtracking generează în ordine crescătoare lexicografică toate permutările mulțimii $\{1,2,3,4\}$. Care este a patra permutare generată?

• a) 1324
• b) 1342
• c) 1423
• d) 2134

Răspunsul corect este b). Permutările apar în ordinea 1234, 1243, 1324, 1342, 1423, 1432, 2134 și așa mai departe. Prima valoare este 1 pentru primele șase permutări, iar în cadrul lor a doua valoare crește de la 2 la 4. A patra permutare este deci 1342. Varianta a) este a treia, varianta c) este a cincea, iar varianta d) este a șaptea.

Greșeli frecvente

• Greșit: la revenirea pe un nivel, candidatul rămâne cel de la ultima vizită.
  Corect: la intrarea pe un nivel valoarea se resetează la 0, ca să se încerce toți candidații.
• Greșit: varianta iterativă nu are nevoie de verificarea validității.
  Corect: condiția de validitate este aceeași ca în varianta recursivă.
• Greșit: soluțiile apar în ordine aleatoare.
  Corect: ordinea este dată de ordinea în care sunt încercați candidații pe fiecare nivel.

Înainte și după