Backtracking

Folosim backtracking atunci când o soluție este o succesiune de alegeri (de exemplu o submulțime sau o aranjare a unor elemente) și trebuie să generăm toate variantele care respectă anumite condiții. De aceea, metoda este înrudită cu noțiunile de combinatorică din matematică: generarea permutărilor, a combinărilor sau a aranjamentelor.

Ideea centrală este simplă și o putem rezuma în trei mișcări, repetate pentru fiecare poziție a soluției:

1. încercăm prima valoare disponibilă care respectă condițiile problemei;
2. dacă valoarea este validă, avansăm la poziția următoare și reluăm procesul;
3. dacă nu mai există nicio valoare validă pe poziția curentă, ne întoarcem („backtrack") la poziția anterioară și încercăm acolo următoarea valoare.

Procesul continuă până când am explorat toate combinațiile posibile. Putem privi această căutare ca pe explorarea unui arbore: fiecare nivel reprezintă o poziție a soluției, iar fiecare ramură, o alegere posibilă.

Enunț. Să se genereze toate numerele de 4 cifre formate doar din cifre impare distincte.

Avem la dispoziție mulțimea cifrelor impare {1, 3, 5, 7, 9} și construim numărul cifră cu cifră, de la stânga la dreapta. Pe fiecare poziție alegem cea mai mică cifră încă nefolosită.

• pornim cu cele mai mici alegeri posibile și obținem prima soluție: 1357;
• pe ultima poziție mai putem pune o cifră mai mare, 9, deci urmează 1359;
• pe ultima poziție nu mai avem ce încerca, așa că ne întoarcem la poziția a treia: după 5 urmează 7, iar ultima poziție repornește de la cea mai mică cifră liberă, dând 1375, apoi 1379;
• continuăm la fel: 1395, 1397, apoi se schimbă cifra sutelor și obținem 1537, și tot așa.

Ultima soluție generată, când nu mai există nicio altă combinație, este 9753.

Observă tiparul: modificăm mereu cifra cea mai din dreapta care încă mai are valori de încercat, iar pozițiile din dreapta ei repornesc de la cele mai mici cifre disponibile. Exact acest „pas înapoi" dă numele metodei.

În total, pentru acest exemplu există $A_5^4 = 5 \cdot 4 \cdot 3 \cdot 2 = 120$ de soluții, adică numărul de aranjamente a 4 cifre alese din cele 5 disponibile.

Backtracking explorează, în cel mai nefavorabil caz, toate combinațiile posibile, iar numărul lor crește foarte repede (exponențial) cu dimensiunea datelor. De aceea metoda este potrivită pentru probleme mici sau medii ori atunci când chiar trebuie să generăm toate soluțiile. Pentru a o face mai eficientă, trebuie să renunțăm devreme la ramurile care sigur nu pot duce la o soluție validă.

Backtracking este o tehnică de generare sistematică: construiește soluția pas cu pas și se întoarce atunci când rămâne fără opțiuni, asigurându-se că nicio variantă nu este omisă. Este una dintre tehnicile fundamentale de programare, alături de Divide et Impera. Pentru cei care vor să vadă cum se scrie efectiv în cod, am pregătit, ca material suplimentar, algoritmul general de backtracking.