Problema săriturii calului - Turbo Pascal

1 Metoda backtracking

Deseori în practica trebuie sa rezolvam probleme care au un numar foarte mare de solutii posibile. De cele mai multe ori însa, nu ne intereseaza toate solutiile, ci numai o parte dintre ele, care îndeplinesc anumite conditii specifice problemei. Pentru astfel de probleme este indicata folosirea metodei backtracking care evita generarea solutiilor inutile.

Desigur ca o persoana cu o gândire simplista ar putea spune: "generam toate solutiile, apoi le alegem pe cele care îndeplinesc 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, cât de realista este o astfel de abordare ? Raspunsul la aceste întrebari se va deduce foarte clar din exemplul care urmeaza.

Exemplu : Sa se genereze permutarile de n elemente.

Permutarile de n elemente sunt multimile ordonate ce contin elementele multimii

{1,2, , . . ,n} în care fiecare element apare o singura data.

Cum construim aceste permutari ? Exemplificam pentru cazul n=3, în speta permutarile pe multimea {1,2,3}.

- cu elementul l pe prima pozitie, putem alcatui permutarile (l , 2 , 3) si (l , 3 , 2), asezând elementele 2 si 3 pe a doua si a treia pozitie în cele doua ordini posibile;

- cu elementul 2 pe prima pozitie generam analog permutarile (2 , l , 3) si (2 , 3 , 1);

- cu elementul 3 pe prima pozitie obtinem (3 , l , 2) si (3 , 2 , l).

Prin urmare, permutarile cautate sunt (1,2,3), (1,3,2), (2,1,3), (2,3,1),

Cum putem genera efectiv aceste permutari ? Formam multimea tuturor numerelor de trei cifre alcatuite numai din cifrele l, 2 si 3 în care fiecare cifra apare o singura data. Aceste numere sunt 123, 132, 231. 312. 321. Observati ca ele genereaza tocmai permutarile cautate.

Asa cum am spus, judecând simplist putem proceda astfel:

- generam toate solutiile posibile adica toate numerele de trei cifre care se pot forma cu cifrele l, 2 si 3. Parcurgând multimea {1,2,3} prin enumerare în ordine crescatoare vom obtine pe rând numerele: 1ll, 112, 113, 121, 122, 123, 131,132, 133, 211, 212, 213, 221, 222, 223, 231, 232, etc.

- dintre aceste numere le alegem doar pe acelea care îndeplinesc conditiile problemei. În cazul nostru avem o singura conditie, aceea ca cifrele numarului sa fie distincte. Astfel, vor fi considerate solutii doar numerele 123, 132, 213, 231, 312 si 321.

Aplicarea acestui algoritm conduce la inspectarea a 27 de numere (adica 33) dintre care doar 6 (adica 3!) ne conduc la permutarile cautate. Pe caz general, pentru a obtine permutarile de n elemente suntem nevoiti sa "vizitam" nn numere. Ineficienta este si mai frapanta pentru n=5: parcurgem 3125 de numere pentru a retine efectiv ca solutii doar 120 ! Mai mult, pentru valori mari ale lui n, problema va fi rezolvata .,. într-o alta epoca ! S-a dovedit stiintific ca pentru a rezolva problema în cazul n=100 calculatorul are nevoie de 4*1013 ani! Nu credem ca aveti rabdare sa asteptati atât....

Concluzia e una singura: trebuie gasit un procedeu mai eficient. Pentru acest gen de probleme este utila metoda backtracking pe care o vom prezenta în continuare.

Descrierea metodei

Prima idee pe care trebuie sa o retineti am enuntat-o deja: nu se genereaza toate solutiile posibile, ci numai acelea care îndeplinesc anumite conditii specifice problemei, numite conditii de validare (în unele lucrari de specialitate acestea mai sunt numite si conditii interne).

Solutiile problemei vor fi generate succesiv într-o stiva implementata sub forma unui vector pe care îl vom nota st.

Reamintim:

- În cadrul unui program, utilizatorul îsi poate defini o structura numita stiva. Aceasta functioneaza dupa principiul LIFO ("Last In First Out ", în 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[l], st[2], ..., st [p], atunci pozitia p a elementului cel mai de sus, se numeste vârful stivei, în general, pozitia unui element în vectorul stiva este numita nivel al stivei. Adaugarea si extragerea de elemente în / din stiva, se poate face numai pe la capatul de sus al acesteia.

În general, numarul de elemente care intra în componenta solutiilor poate sa difere de la o solutie la alta. Pentru început vom considera cazul în care toate solutiile au acelasi numar de elemente, întrucât acesta se întâlneste cel mai frecvent. Vom nota cu n numarul de elemente ale solutiilor reprezentate pe stiva st. Astfel, o configuratie a vectorului-stiva st formata din elementele (st[l], st [2],. . ., s t [n]), se va numi solutie finala.

Tot pe caz general, fiecare componenta st[i] poate lua valori într-o anumita multime Si, cu i=l,2, . . . ,n. Ansamblul multimilor Si, adica produsul cartezian S1 x S2 x Sn , se numeste spatiul solutiilor posibile. Din nou vom face o particularizare, considerând pentru început ca toate componentele st[i] (i=l,2,. . . ,n) iau valori în aceeasi multime S.