Backtracking Recursiv

1. METODA BACKTRACKING

1. 1. Stiva

Stiva este acea formã de organizare a datelor ( structurã de date ) cu proprietatea cã operatiile de introducere si extragere a datelor se fac în vârful ei.

Pentru a întelege modul de lucru cu stiva, sã ne imaginãm un numãr n de farfurii identice, asezate una peste alta ( o „stivã” de farfurii ). Adãugarea sau scoaterea unei farfurii se face, cu usurintã, numai în vârful stivei. Dacã toate cele n farfurii sunt asezate una peste alta, spunem cã stiva este plinã. Dupã ce am scos toate farfuriile din stivã, spunem cã aceasta este vidã.

Stivele se pot simula utilizând vectori.

Fie ST(i) un vector. ST(1), ST(2), ....., ST(n) pot retine numai litere sau numai cifre. O variabilã k indicã în permanentã vârful stivei.

În continuare, se prezintã modul de lucru cu stiva :

- în stiva initial vidã se introduce litera A, vârful stivei va fi la nivelul 1 ( k = 1 );

- introducem în stivã litera B, deci k va lua valoarea 2;

- scoatem din stivã pe B ( A nu poate fi scos );

- scoatem din stivã pe A; stiva rãmâne vidã.

Observatii :

- în mod practic, la scoaterea unei variabile din stivã, scade cu 1 valoarea variabilei ce indicã vârful stivei, iar atunci când scriem ceva în stivã, creste cu 1 valoarea variabilei ce indicã vârful stivei;

- stivele pot fi simulate si altfel decât cu vectori;

- pe un anumit nivel se retine, de regulã, o singurã informatie ( literã sau cifrã ), însã este posibil, sã avem mai multe informatii, caz în care avem de a face cu stive duble, triple, etc;

- întreaga teorie a recursivitãtii se bazeazã pe structura de tip stivã.

1. 2. Prezentarea tehnicii Backtracking

Aceastã tehnicã se foloseste în rezolvarea problemelor care îndeplinesc simultan urmãtoarele conditii:

- solutia lor poate fi pusã 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 considerã cã se aflã într – o relatie de ordine bine stabilitã;

- nu se dispune de o altã metodã de rezolvare, mai rapidã.

Observatii :

- nu pentru toate problemele n este cunoscut de la început;

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

- în multe probleme, multimile A1, A2, ... , An coincid.

La întâlnirea unei astfel de probleme, dacã nu cunoastem aceastã tehnicã, suntem tentati sã generãm toate elementele produsului cartezian A1 x A2 x ... x An si fiecare element sã fie testat dacã este solutie. Rezolvând problema în acest mod, timpul de executie este foarte mare, algoritmul neavând nici o valoare practicã.