Metoda backtracking

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? 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.

? 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 ...