Tăierea ramurilor inutile — oprește-te din timp

Ce e tăierea (pruning) și de ce economisește

Știi deja schema generală: alege o opțiune, coboară recursiv, apoi dezalege (revii și încerci altceva). Problema e că arborele de variante crește exponențial. Dacă explorezi orice ramură până la capăt, plătești pentru fiecare frunză.

Tăierea ramurilor înseamnă să oprești o ramură de îndată ce ai certitudinea că nu poate produce nicio soluție validă. Nu cobori pe ea, te întorci direct.

De ce economisește atât de mult? Pentru că o ramură tăiată sus în arbore nu elimină un singur nod, ci tot sub-arborele care ar fi crescut din ea. Dacă o ramură tăiată ar fi avut sub ea încă 10 niveluri, ai scăpat dintr-o singură decizie de mii de apeluri recursive.

Cum recunoști o ramură moartă

O ramură e moartă când o constrângere a problemei este deja încălcată de alegerile parțiale făcute până acum — și nicio alegere viitoare nu o mai poate repara. Întrebarea cheie e:

„Starea de acum mai poate, măcar teoretic, să devină o soluție validă?”

Dacă răspunsul e „nu, cu siguranță”, atunci tai. Câteva exemple tipice:

• Suma de submulțimi: dacă valorile sunt pozitive și suma curentă a trecut deja de țintă, niciun element în plus nu o va micșora — ramură moartă.
• N dame: dacă o damă atacă deja una plasată, configurația e invalidă; verifici atacul inainte de a plasa, nu după.
• Sumă cu restul prea mic: dacă suma a tot ce ți-a mai rămas de adăugat nu ajunge până la țintă, nu mai ai cum s-o atingi — tai.

Regula de aur a capitolului rămâne: verifici constrângerea ÎNAINTE de a coborî recursiv.

Exemplu pas cu pas: suma de submulțimi

Avem valorile v = [3, 7, 4, 2] și ținta T = 6. Vrem o submulțime cu suma exact 6. La fiecare element decidem: îl iau sau nu. Tăiem când suma > T (valori pozitive).

Pornim de la suma = 0, index 0:

• Iau 3 → suma = 3 (≤ 6, continui)
  • Iau 7 → suma = 10 → 10 > 6 → TAI (nu mai cobor deloc sub această ramură)
  • Nu iau 7 → suma = 3
    • Iau 4 → suma = 7 → 7 > 6 → TAI
    • Nu iau 4 → suma = 3
      • Iau 2 → suma = 5 ≠ 6, gata elementele
      • Nu iau 2 → suma = 3 ≠ 6
• Nu iau 3 → suma = 0
  • Iau 7 → 7 > 6 → TAI
  • Nu iau 7 → ... iau 4 → 4, apoi iau 2 → suma = 6 → SOLUȚIE {4, 2}

Fără tăiere, fiecare „iau 7” ar fi coborât în tot sub-arborele de sub el degeaba. Cele două tăieri de mai sus au șters ramuri întregi imediat ce suma a sărit peste 6.

Implementare C++

Adăugăm o a doua tăiere puternică: dacă suma curentă plus tot ce a mai rămas nu ajunge la țintă, nu are rost să continuăm. O calculăm o dată ca sumă a sufixului.

#include <iostream>
using namespace std;

const int N = 4;
int v[N] = {3, 7, 4, 2};
int tinta = 6;
int suf[N + 1]; // suf[i] = suma elementelor de la i pana la final
int sol[N];     // 1 daca elementul e ales, 0 altfel
bool gasit = false;

void afiseaza() {
    cout << "Submultime gasita: ";
    for (int i = 0; i < N; i++) {
        if (sol[i] == 1) cout << v[i] << " ";
    }
    cout << "(suma = " << tinta << ")" << endl;
}

void cauta(int i, int suma) {
    if (suma == tinta) { // solutie completa valida
        gasit = true;
        afiseaza();
        return;
    }
    if (i == N) return;           // nu mai sunt elemente
    if (suma > tinta) return;     // TAIERE: am depasit tinta
    if (suma + suf[i] < tinta) return; // TAIERE: restul nu mai ajunge

    // alege: iau elementul i (verific constrangerea inainte de recursie)
    if (suma + v[i] <= tinta) {
        sol[i] = 1;
        cauta(i + 1, suma + v[i]);
        sol[i] = 0; // dezalege
    }

    // ramura: nu iau elementul i
    cauta(i + 1, suma);
}

int main() {
    suf[N] = 0;
    for (int i = N - 1; i >= 0; i--) suf[i] = suf[i + 1] + v[i];

    cauta(0, 0);
    if (!gasit) cout << "Nu exista submultime cu suma " << tinta << endl;
    return 0;
}
// Iesire: Submultime gasita: 4 2 (suma = 6)

Cele trei return-uri din cauta sunt tăierile. Observă că verificarea suma + v[i] <= tinta e făcută inainte de apelul recursiv pe ramura „iau” — exact convenția capitolului.

Complexitate

În cel mai rău caz rămâne exponențială: O(2^n), fiindcă teoretic poți fi nevoit să încerci toate cele 2^n submulțimi (de exemplu când toate valorile sunt foarte mici și nicio tăiere nu se declanșează). Tăierea nu schimbă complexitatea în cel mai rău caz.

Ce schimbă, și enorm, e comportamentul în practică: pe datele reale, tăierile retează sub-arbori întregi și numărul de apeluri scade dramatic — adesea de la milioane la mii. De aceea pruning-ul e o optimizare „de constantă mare”: același ordin teoretic, dar un algoritm care termină în loc să atârne. Cu cât constrângerile sunt mai strânse, cu atât tai mai des.

Vizual, momentul tăierii la „iau 7” (suma sare la 10 > 6) arată așa pe vectorul de valori:

Recapitulare

• Tăierea ramurilor abandonează o ramură de îndată ce o constrângere e deja încălcată, ștergând tot sub-arborele de sub ea.
• Recunoști o ramură moartă întrebând „mai poate deveni asta o soluție validă?” și verifici ÎNAINTE de a coborî recursiv — tai cât mai sus, cât mai devreme.
• Pruning-ul nu schimbă complexitatea în cel mai rău caz (tot exponențial), dar în practică poate transforma un algoritm care atârnă într-unul instantaneu.