Metoda backtracking

Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile de introducere si scoatere a datelor se fac in varful ei.?

Stivele se pot simula utilizand vectori.

Fie ST(i) un vector. ST(1), ST(2), ..., ST(n) pot retine numai litere sau numai cifre. O variabila K indica in permanenta varful stivei.

Exemplificam, in continuare, modul de lucru cu stiva:

In stiva initial vida se introduce litera A, varful stivei va fi la nivelul 1 (k-1);

introducem in stiva litera B, deci k va lua valoarea 2;

scoatem din stiva pe B (A nu poate fi scos);

scoatem din stiva pe A; stiva ramane vida

In mod practic la scoaterea unei variabile din stiva, scade cu 1 valoarea variabilei ce indica varful stivei, iar atunci cand scriem ceva in stiva, o eventuala valoare reziduala se pierde:

Pe un anumit nivel se retine, de regula, o singura informatie (litera sau cifra), insa este posibil; asa cum va rezulta din exemplele, prezentate in lucrare, sa avem mai multe informatii, caz in care avem de a face cu stive duble, triple, etc.

Intreaga teorie a recursivitatii se bazeaza pe structura de tip stiva.

Prezentarea tehnicii Backtracking

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:

- solutia lor poate fi pusa sub forma unui vector S=x1,x2, ...,xn, cu x1 EUR A1,

x2 EUR A2 ...,xn EUR An

- multimile A1, A2 , ...., An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

- nu se dispune de o alta metoda de rezolvare, mai rapida

- x1 x2 ..., xn pot fi la randul lor vectori;

- A1, A2 ..., An pot coincide.

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A1,A2 ...,An si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

De exemplu, daca dorim sa generam toate permutarile unei multimi finite A, nu are rost sa generam produsul cartezian AxAx.....xA, pentru ca apoi, sa testam, pentru fiecare element al acestuia, daca este sau nu permutare (nu are rost sa generam 1.1,1.......1, pentru ca apoi sa constatam ca nu am obtinut o permutare, cand de la a doua cifra 1 ne puteam da seama ca cifrele nu sunt distincte).

Tehnica Backtracking are la baza un principiu extrem de simplu:

- se construieste solutia pas cu pas: x1, x2 ...,xn

- daca se constata ca, pentru o valoare aleasa, nu avem cum sa ajungem la solutie, se renunta la acea valoare si se reia cautarea din punctul in care am ramas.

Concret:

- se alege primul element x, ce apartine lui A;

- presupunand generate elementele x1,x2 ...,xk , apartinand multimilor A1,

A2 ...,Ak , se alege (daca exista) xk+1 , primul element disponibil din multimea Ak+1 , apar doua posibilitati :

1) Nu s-a gasit un astfel de element, caz in care caz in care se reia cautarea considerand generate elementele x1,x2 ...,xk+1 , iar aceasta se reia de la urmatorul element al multimii Ak ramas netestat;

2) A fost gasit, caz in care se testeaza daca acesta indeplineste anumite conditii de continuare aparand astfel doua posibilitati:

- indeplineste, caz in care se testeaza daca s-a ajuns la solutie si apar din nou doua posibilitati

- s-a ajuns la solutie, se tipareste solutia si se reia algoritmul considerand generate elementele x1,x2 ...,xk , (se cauta in continuare, un alt element al multimii Ak , ramas netestat);

- nu s-a ajuns la solutie, caz in care se reia algoritmul considerand generate elementele x1,x2 ...,xk , si se cauta un prim element xk+2 EUR Ak.

- nu le indeplineste caz in care se reia algoritmul considerand generate elementele x1,x2 ...,xk , iar elementul xk-1 se cauta intre elementele multimii A, ramase netestate.