Metoda backtracking explicată: stivă, validare, soluție

Metoda backtracking este tehnica prin care generezi, una câte una, toate soluțiile unei probleme: toate permutările unei mulțimi, toate submulțimile cu o anumită proprietate, toate numerele care respectă niște condiții. La BAC Informatică apare de regulă ca item cu alegere multiplă la Subiectul I, unde trebuie să știi exact în ce ordine sunt generate soluțiile. Ca să răspunzi sigur, trebuie să înțelegi schema din spatele ei, nu doar să o memorezi.

Ideea: construiești soluția element cu element

O soluție are forma unui șir st[1], st[2], …, st[n]. Vectorul st se numește stivă, pentru că îl completezi de la stânga la dreapta și, când te blochezi, te întorci un pas înapoi și schimbi ultima valoare pusă, exact ca la o stivă: ultimul element adăugat este primul modificat.

Pe fiecare poziție k procedezi la fel:

1. Încerci pe rând valorile posibile pentru st[k], în ordine crescătoare.
2. Pentru fiecare valoare verifici dacă este validă, adică dacă nu încalcă nicio condiție față de elementele deja puse (st[1] … st[k-1]).
3. Dacă este validă și ai completat toate pozițiile, ai o soluție: o afișezi.
4. Dacă este validă, dar soluția nu e completă, treci la poziția k+1.
5. Când ai epuizat toate valorile pentru poziția k, revii la poziția k-1 și încerci acolo următoarea valoare. Acesta este pasul de „întoarcere” care dă numele metodei.

Schema generală în C++ (varianta recursivă)

Cel mai simplu mod de a scrie backtracking este cu o funcție recursivă back(k), care completează poziția k. Exemplul de mai jos generează permutările mulțimii {1, 2, …, n}:

#include <iostream>
using namespace std;

int n, st[20];

bool valid(int k)
{
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return false;
    return true;
}

void afisare()
{
    for (int i = 1; i <= n; i++)
        cout << st[i] << ' ';
    cout << '\n';
}

void back(int k)
{
    for (int v = 1; v <= n; v++)
    {
        st[k] = v;
        if (valid(k))
        {
            if (k == n)
                afisare();
            else
                back(k + 1);
        }
    }
}

int main()
{
    cin >> n;
    back(1);
    return 0;
}

Oricare problemă de backtracking se obține din această schemă modificând doar patru lucruri:

Urmărirea pas cu pas pentru n = 3

Merită să parcurgi măcar o dată execuția de mână. Notăm conținutul stivei după fiecare atribuire:

• st = 1 valid → trecem la k=2.
• st = 1 1 invalid; st = 1 2 valid → k=3.
• st = 1 2 1, 1 2 2 invalide; 1 2 3 valid și k=3 → soluția 1 2 3.
• La k=3 nu mai sunt valori, revenim la k=2: st = 1 3 valid → k=3.
• 1 3 1 invalid; 1 3 2 valid → soluția 1 3 2; 1 3 3 invalid.
• La k=2 valorile s-au terminat, revenim la k=1: st = 2, și procesul continuă.

Programul afișează, în ordine: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. Sunt 3! = 6 soluții.

De ce soluțiile apar într-o anumită ordine

Aceasta este întrebarea care contează la BAC. Pentru că pe fiecare poziție valorile se încearcă în ordine crescătoare, iar poziția din stânga se schimbă abia după ce toate combinațiile din dreapta ei au fost epuizate, soluțiile sunt generate în ordine lexicografică, adică exact ca într-un dicționar sau ca numerele la un contor: ultima cifră se schimbă cel mai des, prima cel mai rar.

Consecințe practice:

• Toate soluțiile care încep cu 1 apar înaintea celor care încep cu 2.
• Prima soluție este cea mai „mică” lexicografic, ultima este cea mai „mare”.
• Dacă bucla ar merge descrescător (de la n la 1), ordinea s-ar inversa. Enunțul îți spune mereu ordinea; citește primele soluții date ca exemplu ca să o confirmi.

Cum adaugi o condiție suplimentară

Să zicem că vrei permutările lui {1, 2, 3, 4} în care oricare două elemente vecine au parități diferite. Nu schimbi nimic altceva decât funcția valid:

bool valid(int k)
{
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return false;
    if (k > 1 && st[k] % 2 == st[k - 1] % 2)
        return false;
    return true;
}

Programul generează 8 soluții, în această ordine: 1 2 3 4, 1 4 3 2, 2 1 4 3, 2 3 4 1, 3 2 1 4, 3 4 1 2, 4 1 2 3, 4 3 2 1.

Observă un lucru important: condiția se verifică imediat, la fiecare poziție, nu abia la final. Așa, o ramură greșită (de exemplu 1 3 …) este abandonată din prima, fără să mai fie completate restul pozițiilor. Aceasta este diferența dintre backtracking și „generează tot și filtrează la sfârșit”.

Cât de rapid este backtracking-ul?

Nu foarte. Numărul de soluții crește exponențial sau factorial: 10! înseamnă peste 3,6 milioane de permutări. De aceea backtracking-ul se folosește doar pentru valori mici ale lui n sau atunci când chiar ai nevoie de toate soluțiile. Dacă problema cere doar numărul de soluții și există o formulă (de exemplu n! sau combinări), formula este întotdeauna mai bună.