Mic tutorial Backtracking - part 1: Blind bkt

Backtracking cred ca este unul din algoritmii mei preferati. E like the father of all algorythms. He pwns everything. Greedy? Dinamica? Le face. Mai incet, dar le face (bine, mult mai incet, are complexitatea O(2^n)). Daca mi se permite aceasta metafora, e like ai 2 tipe, una vine la tine si zice ca stie sa iti dea un blowjob rapid, si alta care vine si zice ca stie si blowjobul si toate pozitiile din Kama Sutra si le face incet dar bine, pe care ai alege? (raspuns irelevant: the one with the bigger boobs :P )

Anyways inapoi la treaba serioasa. Backtracking. Care e ideea? Ai un vector de valori posibile, sa ii zicem pos[], si o stiva st[] in care bagam toate permutarile intre o parte din elementele din pos (sau toate, dupa caz) si verificam daca solutia este corecta.

Varianta recursiva e cea mai scurta si dragalasa:

void bkt(int p)

{
for (int i=0;i < n_pos;i++)

{
st[p]=pos[i];
if(p==nr_cautat)
if (verif(p)) afis(p);
else bkt(p+1);

}
}

THE END. Astea sunt cele 5 randuri pt care trebuie sa intelegeti principiul.
Ca exemplu de rulare, sa zicem ca avem pos[]={1,2,3} si nr_cautat =2. Practic adauga in stiva 1, si apeleaza bkt pentru a 2a pozitie din stiva. Va baga in stiva {1, 1} si verifica daca solutia este corecta. Dupa, vom avea in stiva {1, 2} si verifica. Dupa, {1,3}. {2, 1} etc. Functia verif() depinde de problema, evident. O idee ar fi sa salvam in st[] doar indicii pentru pos[], adica st[p]=i; ca sa verificam mai usor in verif(p) daca elementele sunt distincte. Alteori, e mai eficient sa facem verificarea imediat cum adaugam un element nou, si dupa sa vedem daca am ajuns la numarul de elemente cautat.

Asta este principiul de baza. In rest, conteaza creativitatea programatorului pentru a-l optimiza. Dar, desigur, ppl like telling you how to think, asa ca avem un fel de grade de optimizare, AC1, AC2, blabla. Voi scrie intr-un post urmator cu ce se mananca fiecare.