Bun venit la una dintre cele mai elegante și puternice metode din informatică! Dacă recursivitatea este “păpușile matrioșka”, backtracking-ul este ca un explorator într-un labirint care își notează drumul și se întoarce când ajunge într-un fundătura.
1. Ce este Backtracking-ul? “Exploratorul Înțelept”
Imaginează-ți această analogie:
Ești în labirint cu o bobina de ață. Mergi înainte, desfășurând ața. Când ajungi la o bifurcație, alegi un drum. Dacă ajungi într-un fund de sac, te întorci pe același drum (înfășurând ața), până când ajungi înapoi la ultima bifurcație, unde încerci alt drum.
Asta este backtracking-ul în esență!
Definiție formală:
Backtracking este o tehnică de căutare sistematică a tuturor (sau a unora dintre) soluțiile unei probleme, prin construirea treptată a soluțiilor și renunțarea la ele când se constată că nu pot duce la o soluție validă.
De ce “back” + “tracking”?
- Back = înapoi
- Tracking = urmărirea traseului
- Backtracking = a te întoarce pe urmele tale
2. Filozofia din spatele Backtracking-ului
Principiul fundamental: “Încerc, și dacă nu merge, mă întorc”
| Pas | Acțiune | Analogie |
|---|---|---|
| 1 | Aleg o opțiune | Alege un drum în labirint |
| 2 | Verific dacă e bună | Văd dacă drumul duce undeva |
| 3 | Dacă e bună, continuu | Merg mai departe pe drum |
| 4 | Dacă nu e bună, mă întorc | Mă întorc și încerc alt drum |
| 5 | Repet până găsesc ieșirea | Continui până găsesc soluția |
Cum gândește calculatorul:
Început
│
├── Încercă opțiunea A
│ ├── Dacă merge → continuă
│ └── Dacă NU merge → întoarce-te
│
├── Încercă opțiunea B
│ ├── Dacă merge → continuă
│ └── Dacă NU merge → întoarce-te
│
└── ... și tot așa ...3. Componentele Esențiale ale unui Algoritm Backtracking
Orice algoritm backtracking are patru părți cruciale:
void backtracking(int pas) {
// 1. VERIFICARE SOLUȚIE FINALĂ
if(am_gasit_solutie(pas)) {
afiseaza_solutie();
return;
}
// 2. GENERARE CANDIDAȚI pentru următorul pas
for(fiecare candidat_posibil) {
// 3. VERIFICARE VALIDITATE
if(este_valid(candidat)) {
// 4a. ADAUGARE la soluția parțială
adauga_la_solutie(candidat);
// 4b. APEL RECURSIV pentru pasul următor
backtracking(pas + 1);
// 4c. ELIMINARE din soluția parțială (BACKTRACK!)
elimina_din_solutie(candidat);
}
}
}De ce este important pasul 4c (eliminarea)?
Pentru că după ce am explorat TOATE posibilitățile care pornesc de la alegerea curentă, trebuie să “ștergem urma” pentru a putea încerca alte alegeri anterioare!
4. Problema Regilor pe Tabla de Șah
Enunț: Plasează N regine pe o tablă de șah N×N, astfel încât nicio regină să nu se atace reciproc.
Analogie: Imaginează-ți că ești director la un festival și trebuie să așezi N cântăreți pe o scenă N×N, astfel încât:
- Niciunul să nu fie în același rând cu altul
- Niciunul să nu fie în aceeași coloană cu altul
- Niciunul să nu fie pe aceeași diagonală cu altul
#include <iostream>
#include <vector>
using namespace std;
void afisareTabla(vector<int>& solutie) {
int n = solutie.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(solutie[i] == j) {
cout << "Q ";
} else {
cout << ". ";
}
}
cout << endl;
}
cout << endl;
}
bool esteSigur(vector<int>& solutie, int rand, int coloana) {
// Verifică coloana și diagonalele
for(int i = 0; i < rand; i++) {
if(solutie[i] == coloana ||
abs(solutie[i] - coloana) == abs(i - rand)) {
return false;
}
}
return true;
}
void regineBacktracking(vector<int>& solutie, int rand, int n, int& count) {
if(rand == n) {
// Am plasat toate reginele
count++;
cout << "Solutia #" << count << ":\n";
afisareTabla(solutie);
return;
}
for(int col = 0; col < n; col++) {
if(esteSigur(solutie, rand, col)) {
// ADAUGĂ regina
solutie[rand] = col;
// CONTINUĂ cu următorul rând
regineBacktracking(solutie, rand + 1, n, count);
// BACKTRACK! (nu e nevoie să ștergi explicit pentru că suprascriem)
}
}
}
int main() {
int n = 4;
vector<int> solutie(n, -1);
int count = 0;
regineBacktracking(solutie, 0, n, count);
cout << "Total solutii pentru " << n << " regine: " << count << endl;
return 0;
}5. Tabel Comparativ: Backtracking vs Alte Metode
| Aspect | Backtracking | Forță Brută | Algoritmi Greedy |
|---|---|---|---|
| Strategie | Construiește progresiv, se întoarce la nevoie | Încearcă TOATE combinațiile | Alege mereu ce pare mai bun acum |
| Eficiență | Mai bun decât forța brută, dar încă exponential | Foarte ineficient | Foarte rapid, dar nu întotdeauna optimal |
| Spațiu | Folosește memoria pentru starea curentă | Folosește multă memorie | Folosește puțină memorie |
| Garantie | Găsește TOATE soluțiile (dacă e complet) | Găsește TOATE soluțiile | Nu garantează soluția optimală |
| Utilizare | Probleme combinatorii, restricții complexe | Probleme mici, teste exhaustive | Probleme de optimizare cu proprietatea greedy |
6. Problema Sumei Submultimilor (Subset Sum)
Enunț: Dintr-o mulțime de numere, găsește toate submultimile a căror sumă este egală cu o valoare dată.
Analogie: Ai un portofel cu bancnote de valori diferite. Vrei să plătești exact suma X. Începi să iei bancnote:
- Dacă suma depășește X, lași ultima bancnotă și încerci alta
- Dacă suma este exact X, ai găsit o soluție
- Dacă suma este mai mică, continui să adaugi
#include <iostream>
#include <vector>
using namespace std;
void sumaSubmultimi(vector<int>& numere, int target,
vector<int>& solutieCurenta,
int index, int sumaCurenta) {
// Caz de bază: am găsit soluție
if(sumaCurenta == target) {
cout << "Solutie: { ";
for(int num : solutieCurenta) {
cout << num << " ";
}
cout << "}" << endl;
return;
}
// Caz de oprire: am depășit sau nu mai am numere
if(sumaCurenta > target || index >= numere.size()) {
return;
}
// Opțiunea 1: INCLUD numărul curent
solutieCurenta.push_back(numere[index]);
sumaSubmultimi(numere, target, solutieCurenta,
index + 1, sumaCurenta + numere[index]);
// BACKTRACK: scot numărul curent
solutieCurenta.pop_back();
// Opțiunea 2: EXCLUD numărul curent
sumaSubmultimi(numere, target, solutieCurenta,
index + 1, sumaCurenta);
}
int main() {
vector<int> numere = {1, 2, 3, 4, 5};
int target = 7;
vector<int> solutieCurenta;
cout << "Submultimile cu suma " << target << " sunt:\n";
sumaSubmultimi(numere, target, solutieCurenta, 0, 0);
return 0;
}7. Arborii de Căutare în Backtracking
Imagine: Fiecare decizie creează o ramură în arbore. Backtracking-ul parcurge acest arbore.
Început
/ \
Include 1 Exclude 1
/ \ / \
Include 2 Exclude 2 Include 2 Exclude 2
/ \ ... ... ...Proprietăți ale arborelui de căutare:
- Adâncimea = numărul de decizii luate
- Factorul de ramificare = numărul de opțiuni la fiecare pas
- Frunzele = soluții complete sau fundături
Complexitate: O(b^d) unde:
- b = factorul de ramificare mediu
- d = adâncimea maximă
8. Tehnică: “Forward Checking” și “Constraint Propagation”
Pentru a îmbunătăți backtracking-ul, folosim tehnici de reducere a spațiului de căutare:
Forward Checking:
După ce alegi o valoare pentru o variabilă, elimini imediat valorile inconsistente din domeniile variabilelor nealocate.
Exemplu – Sudoku:
Început: toate celulele au domeniul {1..9}
Aleg celula (1,1)=3
→ Elimin 3 din toate celulele de pe rândul 1
→ Elimin 3 din toate celulele de pe coloana 1
→ Elimin 3 din toate celulele din căsuța 3x3
Dacă vreo celulă rămâne fără opțiuni → BACKTRACK!Tabel de comparare:
| Tehnică | Descriere | Avantaj | Dezavantaj |
|---|---|---|---|
| Backtracking simplu | Verifică restricții doar când soluția e completă | Simplu de implementat | Ineficient |
| Forward Checking | Verifică consecințele imediate ale alegerilor | Reduce spațiul de căutare | Nu vede consecințe îndepărtate |
| Constraint Propagation | Propaga restricțiile până la stabilire | Foarte eficient | Complex de implementat |
9. Problema Comis-voiajorului (Traveling Salesman Problem)
Enunț: Un comis voiajor trebuie să viziteze N orașe și să se întoarcă la punctul de plecare, folosind cel mai scurt drum posibil, fără a vizita un oraș de două ori.
Complexitate: (N-1)! posibilități (crescător factorial)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void comisVoiajorBacktracking(vector<vector<int>>& distante,
vector<bool>& vizitat,
int orașCurent, int count,
int costCurent, int& costMinim,
vector<int>& drumCurent,
vector<int>& drumOptim) {
int n = distante.size();
// Dacă am vizitat toate orașele
if(count == n) {
// Adaug distanța de întoarcere la start
costCurent += distante[orașCurent][0];
if(costCurent < costMinim) {
costMinim = costCurent;
drumOptim = drumCurent;
}
return;
}
// Încerc să merg la fiecare oraș nevizitat
for(int următor = 0; următor < n; următor++) {
if(!vizitat[următor] && distante[orașCurent][următor] > 0) {
// ADAUGĂ orașul la drum
vizitat[următor] = true;
drumCurent[count] = următor;
int noulCost = costCurent + distante[orașCurent][următor];
// Dacă deja depășim minimul, nu continuăm (prunare)
if(noulCost < costMinim) {
comisVoiajorBacktracking(distante, vizitat, următor,
count + 1, noulCost, costMinim,
drumCurent, drumOptim);
}
// BACKTRACK
vizitat[următor] = false;
}
}
}10. Optimizări și Tehnică Avansată: “Prunarea Arborelui”
Backtracking-ul simplu poate fi foarte lent. Iată cum îl optimizăm:
A. Bounding Functions (Funcții de Mărginit)
Estimează o limită inferioară pentru costul soluției complete. Dacă deja depășim cea mai bună soluție cunoscută, nu mai explorăm această ramură.
Exemplu în comis-voiajor:
Cost curent: 50
Cea mai bună soluție găsită: 100
Estimat minim rămas: 60 (prin MST)
Total estimat: 50 + 60 = 110 > 100
→ PRUNĂ această ramură!B. Variable Ordering (Ordonarea Variabilelor)
Alege mai întâi variabilele cu cele mai puține opțiuni valide (principiul “cel mai constrâns”).
Exemplu în Sudoku:
Celula A: poate fi {3,5,7,9} (4 opțiuni)
Celula B: poate fi {7} (1 opțiune)
→ Alege MAI ÎNTÂI celula B!C. Value Ordering (Ordonarea Valorilor)
Încearcă mai întâi valorile care au cele mai mari șanse de succes.
Exemplu în problema culorilor hărții:
Poți colora regiunea cu:
- Albastru (folosit de 1 vecin)
- Roșu (folosit de 3 vecini)
→ Încearcă MAI ÎNTÂI albastru!11. Tabel: Probleme Clasice Rezolvabile cu Backtracking
| Problema | Descriere | Dimensiune Tipică | Observații |
|---|---|---|---|
| N Regine | Plasare regine pe tabla de șah | N ≤ 30 | Exemplu clasic educațional |
| Sudoku | Completare puzzle numeric | 9×9 | Folosește forward checking |
| Suma Submultimilor | Găsire submulțimi cu sumă dată | N ≤ 20-30 | Poate fi optimizat cu DP |
| Comis-voiajor | Drum minim prin orașe | N ≤ 15-20 | NP-hard, backtracking doar pentru N mic |
| Colorarea hărții | Colorare regiuni cu culori | N ≤ 50 | 4 culori suficiente (teorema) |
| Permutări | Generare toate permutările | N ≤ 10 | Exemplu simplu |
| Combinări | Generare toate combinațiile | N ≤ 20, K ≤ 10 | C(N,K) crește rapid |
| Labirint | Găsire drum din start la finish | M,N ≤ 50 | Poate fi rezolvat și cu BFS |
12. Aplicații Practice din Viața Reală
1. Planificarea Orarului (School Timetabling)
Trebuie să aloci: profesori, săli, clase, ore
Restricții: Profesorul X nu poate fi în două locuri simultan, sala Y are anumite echipamente, etc.
2. Optimizarea Rutelor de Livrare
Asemănătoare cu comis-voiajor, dar cu restricții suplimentare: capacități vehicule, time windows, etc.
3. Design Circuit Integrat
Placing components on a chip to minimize wire length and avoid overlaps.
4. Jocuri Puzzle
Sudoku, Crossword, Kakuro, etc.
5. Planificarea Proiectelor
Alocarea resurselor (oameni, echipamente) pe task-uri cu dependințe și deadline-uri.
13. Limitări și Alternative la Backtracking
Când NU folosi backtracking:
- Probleme foarte mari (N > 30 pentru multe probleme)
- Când există algoritmi specializați mai rapizi
- Când ai nevoie doar de o singură soluție (poate exista algoritmi greedy)
Alternative:
| Metodă | Când să folosești |
|---|---|
| Programare Dinamică | Când subproblemele se suprapun |
| Algoritmi Greedy | Când alegerea greedy e garantat optimă |
| Algoritmi Genetici | Pentru probleme foarte mari, soluții aproximative |
| Simulated Annealing | Optimizare continuă, evitarea minimelor locale |
14. Concluzie: Filosofia Backtracking-ului
Backtracking-ul este mai mult decât o tehnică de programare – este o filozofie de rezolvare a problemelor:
Lecții de viață din backtracking:
- Încearcă, dar fii pregătit să te întorci – Nu te încăpățâna pe un drum care nu duce nicăieri
- Șterge-ți urmele – Ca să poți încerca alte căi
- Construiește treptat – Marele drum e făcut din pași mici
- Verifică-ți progresul – Nu aștepta până la sfârșit să vezi dacă ești pe drumul bun
- Folosește-ți experiența – Dacă știi că o cale nu duce nicăieri, nu o mai parcurgi
În programare:
Backtracking-ul este ultima armă atunci când:
- Problema are multe restricții complexe
- Nu există algoritmi eficienți cunoscuți
- Spațiul de căutare este prea mare pentru forță brută, dar suficient de mic pentru backtracking optimizat
Cuvinte finale:
Backtracking-ul este arta de a căuta sistematic în spațiul soluțiilor, cu înțelepciunea de a te întoarce la timp și de a evita căile fără ieșire. Este o dans între explorare și prudență, între curajul de a încerca și înțelepciunea de a renunța.
Remember: Cel mai bun algoritm de backtracking este acela care știe când să se oprească din căutare în direcții inutile! 🧩🔍🔄
Leave a Reply