Metoda Backtracking

Exemplificam, în continuare, modul de lucru cu stiva: În stiva initial vida se introduce litera A, vârful stivei va fi la nivelul 1 (k-1);

introducem în 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 ramâne vida

În mod practic la scoaterea unei variabile din stiva, scade cu 1 valoarea variabilei ce indica vârful stivei, iar atunci când scriem ceva în stiva, o eventuala valoare reziduala se pierde: Pe un anumit nivel se retine, de regula, o singura informatie (litera sau cifra), însa este posibil; asa cum va rezulta din exemplele, prezentate în lucrare, sa avem mai multe informatii, caz în care avem de a face cu stive duble, triple, etc. Întreaga teorie a recursivitatii se bazeaza pe structura de tip stiva.

Prezentarea tehnicii Backtracking

Aceasta tehnica se foloseste în rezolvarea problemelor care îndeplinesc simultan urmatoarele conditii:

solutia lor poate fi pusa sub forma unui vector S=x1,x2, ...,xn, cu x1 ? A1,x2 ? A2 .,xn ? An

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

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

x1 x2 ., xn pot fi la rândul lor vectori;

A1, A2 ., An pot coincide.

La întâlnirea 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. Rezolvând problema în acest mod, timpul de executie este atât de mare, încât poate fi considerat infinit, algoritmul neavând 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, când 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 în care am ramas.