Metoda backtracking

Metoda backtracking se utilizeaza pentru rezolvarea unor probleme in care:

- se obtin mai multe solutii;

-solutia este formata din unul sau mai multe elemente, fiind reprezentata printr-un tablou X=(x1,x2,…,xn) unde x1 M1,x2 M2,…,xn Mn;

-tabloul X este o structura finala de stiva;

-multimile M1,M2,…,Mn sunt multimi finite avand c1,c2,…,cn elemante;

-elementele depuse in tablou indeplinesc anumite conditii impuse de enuntul fiecarei problem.

Generarea tuturor tablourilor X cu elementele produsului cartezian M1*M2*…*Mn-numit spatial solutiilor posibile- conduce la un timp de executie foarte mare.

Metoda Backtracking are la baza o strategie prin care se genereaza doar solutiile care indeplinesc conditiile specific problemei, denumite conditii interne.

Solutiile posibile care respecta conditiile interne se numesc solutii rezultat.

Daca un element xj primeste o valoare din multimea Mj care este admisa in solutia rezultat, aceasta valoare se numeste valoare valida.Conditiile de validare sunt deduse din conditiile interne.

EXEMPLU:

Sa se determine toate modalitatile de colorare a tarilor de pe o harta,folosind un numar minim de culori precizat,spre exemplu, 4 culori.Conditia interna rezulta din asezarea tarilor pe harta;pentru a fi vizibile,zonele geografice invecinate –tarile-trebuie colorate distinct.Conditiile de validare se obtin prin compunerea urmatoarelor conditii simple:daca tara i este vecina cu tara j (in matricea de vecinatati M[i][j]=1) atunci culoarea folosita pentru tara i trebuie sa difere de culoarea folosita pentru tara j(in tabloul solutie,X[i]<>X[j]).

Problemele care se rezolva cu aceasta metoda pot avea anumite particularitati:

-numarul n de elemente care pot participa la construirea unei solutii nu este o valoare constanta(fixa) ;

-se poate obtine si o singura solutie,denumita solutie optima;

-elementele x1,x2,x3,…,xn ale unei solutii pot fi si ele tablouri;

-multimile M1,M2,M3,…,Mn pot avea aceleasi elemente.

Exemplu:

Sa se genereze toate numerele naturale cu trei cifre distinct din multimea {1,2,4}

Solutie:

Spatiul solutiilor posibile S=({1,2,4}x{1,2,4}x{1,2,4}={1,1,1},{1,1,2},{1,1,4},{1,2,1},{1,2,2},…,{4,4,4})

Rezolvarea problemei prin generarea tuturor solutiilor conduce la 27 de solutii posibile,dintre care doar 6 sunt solutii rezultat.In tabel s-au generat toate solutiile posibile fiind marcate solutiile rezultat.