I.1. Necesitate
Deseori in practica trebuie sa rezolvam probleme care au un numar foarte mare de solutii posibile. De cele mai multe ori insa, nu ne intereseaza toate solutiile, ci numai o parte dintre ele, care indeplinesc anumite conditii specifice problemei. Pentru astfel de probleme este indicata folosirea metodei backtracking care evita generarea solutilor inutile.
Desigur ca o persoana cu o gandire simplista ar putea spune : " generam toate solutiile, apoi le alegem pe cele care indeplinesc conditiile cerute". Foarte simplu, dar oare si eficient ? Ce rost ar avea sa se genereze niste solutii care oricum nu convin? Din punctul de vedere al timpului necesar calculatorului pentru a obtine toate solutiile, cat de realista este o astfel de abordare?
I.2. Descrierea metodei
Prima idee pe care trebuie sa o retinem ar fi: nu se genereaza toate solutiile posibile, ci numai acelea care indeplinesc anumite conditii specifice problemei, numite conditii de validare (in unele lucrarii de specialitate acestea mai sunt numite si conditii interne).
Solutiile problemei vor fi generate succesiv intr-o stiva implementata sub forma unui vector pe care il vom nota st.
☻REAMINTIM :
► In cadrul unui program, utilizatorul isi poate defini o structura numita stiva. Aceasta functioneaza dupa principiul LIFO ( " Last in First Out", in traducere " Ultimul intrat, primul iesit" ). Cel mai simplu mod de a implementa o stiva este cu ajutorul unui vector st. Pentru a simula caracterul de stiva, privim vectorul st ca si cum elementele sale ar fi asezate " pe verticala", unul peste altul. Daca la un moment dat stiva st contine elementele st[1], st[2], , st[p], atunci pozitia p a elementului cel mai de sus, se numeste varful stivei. In general, pozitia unui element in vectorul stiva este numita nivel al stivei. Adaugarea si extragerea de elemente in /din stiva, se poate face numai pe la capatul de sus al acesteia
In general , numarul de elemente care intra in componenta solutiilor poate sa difere de la o solutie la alta. Pentru inceput vom considera cazul in care toate solutiile au acelasi numar de elemente, intrucat acesta se intalneste cel mai frecvent. Vom nota cu "n" numarul de elemente ale solutiilor reprezentate pe stiva st. Astfel, o configuratie a vectorului-stiva st format din elementele (st[1], st[2], , [n]), se va numi solutie finala.
Tot pe caz general, fiecare componenta st[i] poate lua valori intr-o anumita multime Si , cu i=1,2, ,n. Ansamblul multimilor Si , adica produsul cartezian S1xS2xSn, se numeste spatiul solotiilor posibile. Din nou vom face o particularizare, considerand pentru inceput ca toate componentele st[i] ( i=1,2, ,n) iau valori in aceeasi multime S.
In continuare trebuie sa raspundem la intrebarea: cum putem sa evitam generarea tuturor solutiilor posibile si sa le obtinem numai pe acelea care indeplinesc conditiile de validare? Fiecare solutie va fi construita in stiva st pas cu pas, completand stiva nivel cu nivel. Astfel, pentru a obtine o solutie finala cu n nivele, de forma st=( st[1], st[2], , st[n] ), vom "trece" prin niste configuratii intermediare ale stivei numite solutii partiale. Cu alte cuvinte,o solutie partiala este o configuratie a stivei de forma (st[1], st[2], , st[p] ), unde p va lua succesiv toate valorile de la 1 la n. La randul sau, fiecare solutie partiala se obtine prin completarea cu inca un nivel a solutiei partiale anterioarei.
I.3. Implementarea metodei. Varianta recursiva.
Datorita faptului ca fiecare noua configuratie a stivei se obtine pornind de la precedenta, algoritmi backtracking se pot implementa foarte elegant intr-o maniera recursiva. Putem scrie si programe nerecursive, dar acestea sunt mai laborioase, de aceea vom incepe cu varianta recursiva a metodei backtracking.
In varianta recursiva, solutiile finale st=(st[1], st[2], , st[n] ) sunt generate in cadrul proceduri recursive {bktr(p:integer);}, unde p reprezinta nivelul pana la care s-a ajuns pe stiva. Cu alte cuvinte, la fiecare executie din lantul de auto-apeluri, procedura bktr "trateaza" nivelul p al stivei. De fapt, aceasta procedura implementeaza algoritmul recursiv de backtracking, pe care il descriem in continuare in pseudocod:
Pentu pval de la
la executa
inceput
st[p]← pval
daca valid(p) returneaza true atunci
daca atunci
apel tipar (p)
altfel
auto-apel bktr (p+1)
sfarsit.
Intr-un ciclu prin variabila pval vor trece pe rand toate valorile care ar putea fi incercate pe nivelul pe al stivei. Plecam de la presupunerea ca aceste valori sunt succesive intr-un interval delimitat de capetele v1 si vn, caz in care putem folosi un ciclu cu contor. La fiecare pas al ciclului, pentru fiecare dintre valorile variabilei pval:
▫ Memoram respectiva valuare pe nivel p, prin atribuirea st [p] ← pval. Obtinem astfel solutia (st[1],st[2], , st[p] ), care momentan nu are decat statutul de solutie partiala;
▫ Verificam daca aceasta solutie este valida, testand valuarea returnata de catre functia valid(p). In caz afirmativ (adica daca functia valid(p) ar returna true), atunci trebuie sa verificam daca respectiva solutie este si finala (de obicei conditia de solutie finala este una singura si poate fi testata intr-un if, dar putem folosi si o functie pentru aceasta);
√ In caz afirmativ afisam solutia, apeland procedura tipar(p);
√ In caz contrar, avem de-a face cu o solutie valida (ne aflam pe ramura "daca valid(p)" ), dar care nu este si finala. Fiid vorba de o solutie partiala, trecem la nivelul urmator pentru a o completa. Cum anume ? Trebuie incrementat p-ul, lucru care se realizeaza prin auto-apelul bktr(p+1). Astfel, se va relua de la capat algoritmul, dar cu p+1 in loc de p.
» Procedura recursiva {bktr (p:integer) ; } implementeaza algoritmul de breacktracking, "tratand" la fiecare executie un nivel p al stivei. Pe fiecare nivel vor fi incercate succesiv elementele u[1] si u[2] ale vectorului u (in speta literele ,A' si ,M').Cum anume ?
. in ciclul for controlul pval va parcurge pozitiile elementelor vectorului u, care sunt de la 1 la 2;
. la fiecare pas, pe nivelul p va fi pus elementul din vectorul u al carui indice este pval (prin atribuire st[p] : = u [pval] ).
Mai departe, algoritmul de bracktracking este cel mai standard, prezentat in artea de teorie:
. daca valoarea st[p] a generat o solutie (st[1], st[2], ,st[p] ) valid (daca functia valid[p] a returnat TRUE ), atunci:
- daca solutia respectiva e si finala (p=n, pentru ca se cer secventele de n litere ,A' si ,M' ) atunci o tiparim (apeland procedura tipar(p) );
- in caz contrar, trecem la nivelul urmator (pentru a completa solutia cu un nou nivel ), prin auto-apel bktr (p+1).
I.4. Varianta ne-recursiva a metodei backtracking.
Pentru a va putea permite o comparatie cu varianta recursiva (din punctul de vedere al accesibilitatii), folosim acelasi exemplu: generarea permutarilor de n elemente.
La fel ca si in varianta recursiva, solutiile se construiesc intr-un vector-stiva st, si notam cu p nivelul varfului stivei.
Varianta ne-recursiva foloseste aceleasi subprograme, initializari, tipar(p) si valid(p) pe care le-am prezentat pe larg in varianta recursiva. Acum vom aminti doar actiunea lor.
Procedura { initializari ; } citeste datele de intrare si initializeaza stiva.
Procedura { tipar (p:integer) ; } afiseaza o solutie cu p nivele reprezentata de configuratia (st[1], st[2], , st[p] ).
Functia {valid (p:integer) : boolean; } va returna true daca solutia (st[1], st[2], ,st[p] ) este valida, respectiv false in caz contrar.
Mai intai descriem acest algoritm in pseudocod.
p←1;
st[p] ← 0;
cat timp p>0 executa
inceput
daca atunci
inceput
st[p] ←
daca valid (p) returneaza true atunci
daca atunci
apel tipar (p)
altfel
inceput
p ← p+1;
st[p] ← 0;
sfarsit
sfarsit
altfel
p ←p-1;
sfarsit
Plecam de la primul nivel de pe stiva, initializand cu 1 indicele p al virfului stivei. De asemenea, punem pe acest prim nivel valoarea "de plecare" 0. Algoritmul evolueaza intr-un ciclu "dirijat" de p.
La fiacare pas al ciclului "se trateaza "nivelul" al stivei.
