Invatare Atomica

Backtracking: Schema generala, conditii de continuare si validare

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege metoda backtracking: cum se construieste sistematic spatiul solutiilor, ce inseamna conditia de continuare (pruning), ce inseamna conditia de validare a solutiei complete, si vei implementa schema generala in Python (si C++ la nivel intensiv).

Dupa aceasta lectie vei putea:

  • Sa explici principiul backtracking: explorare + revenire
  • Sa distingi intre conditia de continuare si conditia de solutie completa
  • Sa implementezi schema generala de backtracking in Python
  • Sa urmaresti executia pas cu pas a unui algoritm backtracking
  • Sa estimezi corect complexitatea timp O(n * n!) in cazul permutarilor
  • EXCLUSIV INTENSIV Sa implementezi schema in C++ cu tablouri globale

Incearca singur!

Provocare:

Ai cifrele 1, 2, 3. In cate moduri le poti aranja intr-o coloana de 3 pozitii, astfel incat fiecare cifra sa apara exact o data? Enumera toate variantele inainte sa continui lectia.

💡 Ai nevoie de un indiciu?

Pe prima pozitie poti pune 3 cifre diferite. Dupa ce o alegi, pe a doua pozitie raman 2 optiuni. Pe a treia pozitie ramane exact o optiune. Total: 3 x 2 x 1 = 6 variante.

Backtracking le genereaza sistematic pe toate, fara sa repete niciuna.

1

1. Ce este backtracking?

Backtracking (revenire / explorare sistematica) este o strategie algoritmca de rezolvare a problemelor prin enumerarea sistematica a tuturor solutiilor posibile, cu abandonarea timpurie (pruning) a ramurilor care nu pot duce la o solutie valida.
Intuitie: parcurgerea unui labirint cu ramificatii

Mergeti pe un culoar. Ajungeti la un zid. Va intoarceti la ultima intersectie si luati alt culoar. Repetati pana gasiti iesirea sau epuizati toate drumurile. Aceasta intoarcere controlata este esenta backtracking-ului.

Important: nu intrati niciodata de doua ori pe acelasi culoar din acelasi punct — acesta este rolul marcajului (used[]).

Aplicatii clasice: generarea permutarilor, aranjamentelor, combinarilor, submultimilor; problema celor n dame; colorarea grafurilor; rezolvarea Sudoku.
2

2. Spatiul solutiilor si arborele de cautare

Spatiul solutiilor = multimea tuturor solutiilor candidate (complete sau partiale). Backtracking il exploreaza ca un arbore de cautare parcurs in adancime (DFS — Depth First Search).
Arborele de cautare pentru permutarile lui {1, 2}
                    ( )          <-- radacina: solutie vida
                   /                      [1]       [2]    <-- nivel 1: prima pozitie
                  |         |
               [1,2]     [2,1]   <-- nivel 2: solutii complete
               SOLUTIE   SOLUTIE

Pentru n=3: 3 ramuri la radacina, 2 la nivelul 1, 1 la nivelul 2. Total frunze = 3! = 6 solutii.

Pruning (taiere): cand o conditie esueaza la nivelul k, intregul subarbore de la nodul curent este abandonat. Aceasta reduce dramatic numarul de noduri explorati in problemele cu restrictii.
3

3. Schema generala in Python

Schema generala are 3 componente esentiale: (a) verificarea solutiei complete, (b) iterarea valorilor posibile pentru pozitia curenta, (c) conditia de continuare + pasul de revenire. 
# Schema generala backtracking in Python
# k = pozitia curenta (0..n-1); n = lungimea solutiei
# sol = lista solutiei partial construite
# used = marcaj: used[v]=True daca v a fost deja folosit

def backtracking(k, n, sol, used):
    # (a) Conditia de solutie completa
    if k == n:
        print(sol[:])
        return

    # (b) Iterare valori candidate pentru pozitia k
    for v in range(1, n + 1):
        # (c) Conditia de continuare: v este valid pe pozitia k?
        if not used[v]:
            # Alegere: plaseaza v pe pozitia k
            sol[k] = v
            used[v] = True
            # Recursie: rezolva pozitia k+1
            backtracking(k + 1, n, sol, used)
            # REVENIRE (backtrack): anuleaza alegerea
            sol[k] = 0
            used[v] = False
Exemplu complet: Permutarile lui {1, 2, 3}
n = 3
sol = [0] * n
used = [False] * (n + 1)
print("Permutarile lui {1, 2, 3}:")
backtracking(0, n, sol, used)
Output real (rulat cu python bt_schema2.py):
Permutarile lui {1, 2, 3}:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
4

4. Conditia de continuare vs. conditia de solutie completa

Exista doua tipuri distincte de verificari in backtracking:
  • Conditia de solutie completa (k == n): toate pozitiile au primit valori; solutia este gata de procesat.
  • Conditia de continuare / validare partiala (conditie(k, v)): valoarea v poate fi plasata pe pozitia k fara a viola restrictiile problemei. Daca esueaza, nu exploram acel subarbore (pruning).
Exemplu: siruri din {0,1} fara doua cifre consecutive identice

Conditia de continuare: k == 0 or sol[k-1] != v (nu repetam valoarea precedenta).

def backtracking(k, n, sol):
    if k == n:
        print(sol[:])
        return
    for v in [0, 1]:
        # conditie continuare: diferit de precedentul
        if k == 0 or sol[k-1] != v:
            sol[k] = v
            backtracking(k + 1, n, sol)
            sol[k] = -1

n = 3
sol = [-1] * n
print("Siruri din {0,1} fara cifre consecutive identice, lungime 3:")
backtracking(0, n, sol)
Output real (rulat cu python bt_conditie.py):
Siruri din {0,1} fara cifre consecutive identice, lungime 3:
[0, 1, 0]
[1, 0, 1]

Fara conditia de continuare: 2^3 = 8 siruri de explorat. Cu conditia: arborele este taiat precoce si sunt gasite direct cele 2 siruri valide.

5

5. Urmarirea executiei pas cu pas

La urmarirea executiei (BAC / olimpiada), completam un tabel cu starea variabilelor la fiecare apel recursiv: nivelul k, valoarea v incercata, si solutia partiala curenta.
Trace real pentru permutarile lui {1, 2} (rulat cu python bt_trace.py):
Traseul backtracking pentru permutarile lui {1,2}:
bt(k=0) sol=[]
  bt(k=1) sol=[1]
    bt(k=2) sol=[1, 2]
    -> SOLUTIE: [1, 2]
  bt(k=1) sol=[2]
    bt(k=2) sol=[2, 1]
    -> SOLUTIE: [2, 1]

Total apeluri recursive: 5
Tabel de urmarire (forma BAC):
Apel nr.kv incercatsol partialActiune
101[ ]alege v=1, apel recursiv
212[1]alege v=2, apel recursiv
32-[1, 2]SOLUTIE, return, revenire
41-[1]v=2 epuizat, return, revenire la k=0
502[ ]alege v=2, apel recursiv
611[2]alege v=1, apel recursiv
72-[2, 1]SOLUTIE, return, revenire
Complexitate timp: pentru generarea tuturor permutarilor lui {1, ..., n}: O(n · n!). Sunt n! solutii, iar afisarea fiecareia costa O(n). Complexitate spatiu (stiva de recursie): O(n).
6

6. Schema in C++ EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

La profilul intensiv informatica, implementam aceeasi schema in C++ cu tablouri globale (conventie standard la concursuri). Diferente fata de Python: tipuri declarate explicit, tablouri cu dimensiune maxima constanta, functia main() obligatorie.

#include <iostream>
using namespace std;

const int NMAX = 10;
int  n = 3;
int  sol[NMAX];
bool used[NMAX];

bool conditie(int k, int v) {
    return !used[v];     // v nu a mai fost folosit
}

bool esteSolutieCompleta(int k) {
    return k == n;
}

void afiseazaSolutia() {
    for (int i = 0; i < n; i++)
        cout << sol[i] << (i < n - 1 ? " " : "
");
}

void backtracking(int k) {
    if (esteSolutieCompleta(k)) {
        afiseazaSolutia();
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (conditie(k, v)) {
            sol[k] = v;
            used[v] = true;
            backtracking(k + 1);
            sol[k] = 0;
            used[v] = false;
        }
    }
}

int main() {
    cout << "Permutarile lui {1, 2, 3}:" << endl;
    backtracking(0);
    return 0;
}
Output real (compilat: g++ -std=c++17 bt_cpp2.cpp -o bt_cpp2, rulat: ./bt_cpp2):
Permutarile lui {1, 2, 3}:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Diferente cheie Python vs C++:
  • C++: bool used[NMAX] cu dimensiune maxima; Python: used = [False] * (n+1) alocat dinamic.
  • C++: conditie() si esteSolutieCompleta() ca functii separate — claritate arhitecturala, recomandat la olimpiada.
  • C++: variabilele n, sol, used sunt globale — conventie uzuala la concursuri.
  • Ambele variante produc acelasi rezultat; structura algoritmului este identica.

Exercitii practice

Exercitiul 1 (Nivel minim) - Identificare componente schema

In schema generala de backtracking de mai jos, identifica si denumeste: (a) conditia de solutie completa, (b) conditia de continuare, (c) pasul de alegere, (d) pasul de revenire.

def bt(k, n, sol, used):
    if k == n:
        print(sol)
        return
    for v in range(1, n+1):
        if not used[v]:
            sol[k] = v; used[v] = True
            bt(k+1, n, sol, used)
            sol[k] = 0; used[v] = False

Exercitiul 2 (Nivel standard) - Modificare conditie de continuare

Modifica schema generala (Python) pentru a genera toate sirurile de lungime 4 formate din cifrele {1, 2, 3}, in care suma oricaror doua elemente consecutive este cel mult 4. Scrie conditia de continuare corespunzatoare si ruleaza codul pentru a afisa toate solutiile valide.

Indiciu: conditie: k == 0 or sol[k-1] + v <= 4. Cate siruri valide exista?

Exercitiul 3 (Nivel performanta) - Complexitate si analiza

Analizeaza algoritmul de generare a permutarilor lui {1, ..., n}:

  • (a) Demonstreaza ca numarul de solutii este exact n! (prin rationament combinatorial).
  • (b) Numarul total de noduri in arborele de cautare este suma de la k=0 la n a lui n!/(n-k)!. Calculeaza valoarea pentru n=3.
  • (c) De ce complexitatea timp este O(n * n!) si nu O(n!)? Ce pas costa O(n) per solutie?
  • (d) EXCLUSIV INTENSIV Implementeaza in C++ o versiune care numara apelurile recursive si afiseaza totalul. Verifica pentru n=3 (total apeluri asteptat: 16).

Ce ai invatat astazi

  • Backtracking = explorare sistematica + revenire controlata la primul punct de decizie anterior
  • Arborele de cautare: noduri = solutii partiale, frunze = solutii complete sau ramuri taiate
  • Schema generala: (a) conditia solutie completa, (b) iterare valori, (c) conditie de continuare + revenire
  • Conditia de continuare filtreaza valorile INAINTE de recursie — pruning = eficienta sporita
  • Urmarirea executiei: tabel cu k, v, sol la fiecare apel (cerinta frecventa BAC)
  • Complexitate permutari: O(n * n!) timp, O(n) spatiu pe stiva de recursie

Urmatoarea lectie

Continua cu Lectia 3: Generarea permutarilor — vei implementa variante complete cu conditii, permutari cu repetitie si optimizari specifice.

Continua →