Algoritmi → Rekurzija i bektreking → Bektreking (pretraga sa vraćanjem)

Bektreking (pretraga sa vraćanjem)

Ideja: izaberi – istraži – poništi

Rešenje se gradi korak po korak. U svakom koraku:

1. izaberi jednu od mogućnosti (stavi broj, damu, slovo…);
2. istraži – rekurzivno nastavi gradnju sa tim izborom;
3. poništi izbor (vrati stanje kakvo je bilo) i probaj sledeću mogućnost.

Svi izbori zajedno čine stablo pretrage. Bektreking ga obilazi u dubinu, a odsecanje (pruning) preskače grane za koje se unapred zna da ne vode rešenju.

Opšti oblik:

void pretraga(int korak) {
    if (rešenje je kompletno) {
        obradi rešenje (ispiši, prebroji…);
        return;
    }
    for (svaka mogućnost m za ovaj korak) {
        if (m je dozvoljena) {          // odsecanje
            primeni m;                  // izaberi
            pretraga(korak + 1);        // istraži
            poništi m;                  // vrati stanje
        }
    }
}

Primer: podskupovi sa datim zbirom

Dato je n prirodnih brojeva i broj S. Koliko podskupova ima zbir tačno S? Za svaki broj biramo: uzimamo ga ili ne. Ako je trenutni zbir već veći od S, dalje nema smisla tražiti (brojevi su pozitivni) – to je odsecanje.

#include <iostream>
#include <vector>
using namespace std;

int n, S;
vector<int> a;
int brojResenja = 0;

void pretraga(int i, int zbir) {
    if (zbir > S) return;                 // odsecanje: već smo premašili S
    if (i == n) {                         // odlučili smo za sve brojeve
        if (zbir == S) brojResenja++;
        return;
    }
    pretraga(i + 1, zbir + a[i]);         // uzimamo a[i]
    pretraga(i + 1, zbir);                // ne uzimamo a[i]
}

int main() {
    cin >> n >> S;
    a.resize(n);
    for (int &x : a) cin >> x;
    pretraga(0, 0);
    cout << brojResenja << endl;
    return 0;
}

Za 2 3 5 7 8 i S = 10 rešenja su {2, 3, 5}, {2, 8} i {3, 7}. Ovde se stanje ne mora eksplicitno poništavati jer se zbir prenosi kao parametar.

Primer: N dama

Na tablu N × N treba postaviti N dama tako da se nijedne dve ne napadaju. Dame postavljamo red po red; za svaku kolonu proveravamo da li je ona slobodna i da li su slobodne obe dijagonale. Za zauzetost koristimo tri niza logičkih vrednosti, pa je provera trenutna.

#include <iostream>
using namespace std;

int n, brojRasporeda = 0;
bool kolona[20], diag1[40], diag2[40];   // diag1: r + k, diag2: r - k + n

void postavi(int r) {
    if (r == n) {                        // sve dame su postavljene
        brojRasporeda++;
        return;
    }
    for (int k = 0; k < n; k++) {
        if (kolona[k] || diag1[r + k] || diag2[r - k + n]) continue;   // napadnuto polje
        kolona[k] = diag1[r + k] = diag2[r - k + n] = true;             // izaberi
        postavi(r + 1);                                                  // istraži
        kolona[k] = diag1[r + k] = diag2[r - k + n] = false;            // poništi
    }
}

int main() {
    cin >> n;
    postavi(0);
    cout << brojRasporeda << endl;
    return 0;
}

Za N = 8 postoji 92 rasporeda. Zadatak sa ispisom rasporeda i detaljnim objašnjenjem: N kraljica – rešenje.

Koliko je bektreking brz?

U najgorem slučaju bektreking obilazi celo stablo pretrage, a ono je eksponencijalno veliko (2ⁿ podskupova, n! permutacija). Zato se koristi kada je n malo (obično do 20–25 za podskupove, do 10–12 za permutacije) ili kada odsecanje odbacuje veliki deo stabla. Ako se u pretrazi ista stanja ponavljaju, umesto bektrekinga često pomaže dinamičko programiranje.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje