...vedere al timpului necesar calculatorului pentru a obtine toate solutiile, cat de realista este o astfel de abordare I.2. Descrierea metodei 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. REAMINTIM 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 sti1s, sti2s, ..., stips, 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 sti1s, sti2s, ..., ins, se va numi solutie finala. Tot pe caz general, fiecare componenta stiis poate lua valori intr-o anumita multime Si , cu i1,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 stiis i1,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 nivele, de forma st sti1s, sti2s, ..., stins , vom trece prin niste configuratii intermediare ale stivei numite solutii partiale. Cu alte cuvinte,o solutie partiala este o configuratie a stivei de forma sti1s, sti2s, ..., stips , unde p va lua succesiv toate valorile de la 1 la n. La randul sau, fiecare solutie partiala se obtine prin completarea cu inca un nivel a solutiei partiale anterioarei.I.3. Implementarea metodei. Varianta recursiva. Datorita faptului ca fiecare noua configuratie a stivei se obtine pornind de la precedenta, algoritmi backtracking se pot implementa foarte elegant intr-o maniera recursiva. Putem scrie si programe nerecursive, dar acestea sunt mai laborioase, de aceea vom incepe cu varianta recursiva a metodei backtracking. In varianta recursiva, solutiile finale ststi1s, sti2s, ... , stins sunt generate in cadrul proceduri recursive IbktrpintegerS, unde p reprezinta nivelul pana la care s-a ajuns pe stiva. Cu alte cuvinte, la fiecare executie din lantul de auto-apeluri, procedura bktr trateaza nivelul p al stivei. De fapt, aceasta procedura implementeaza algoritmul recursiv de backtracking, pe care il descriem in continuare in pseudocod Pentu pval de la v1 la vn executa inceput stips! pval daca validp returneaza true atunci ...
Download