METODA BACKTRACKING

METODA BACKTRACKING

Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile de introducere si scoatere a datelor se fac in varful ei.­

Stivele se pot simula utilizand vectori.

Fie ST(i) un vector. ST(1), ST(2), , ST(n) pot retine numai litere sau numai cifre. O variabila K indica in permanenta varful stivei.

Exemplificam, in continuare, modul de lucru cu stiva:

In stiva initial vida se introduce litera A, varful stivei va fi la nivelul 1 (k-1);

introducem in 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 ramane vida

In mod practic la scoaterea unei variabile din stiva, scade cu 1 valoarea variabilei ce indica varful stivei, iar atunci cand scriem ceva in stiva, o eventuala valoare reziduala se pierde:

Pe un anumit nivel se retine, de regula, o singura informatie (litera sau cifra), insa este posibil; asa cum va rezulta din exemplele, prezentate in lucrare, sa avem mai multe informatii, caz in care avem de a face cu stive duble, triple, etc.

Intreaga teorie a recursivitatii se bazeaza pe structura de tip stiva.

Prezentarea tehnicii Backtracking

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:

- solutia lor poate fi pusa sub forma unui vector S=x₁,x₂, ,x_n, cu x₁ € A₁,

x₂ € A₂ …,x_n € A_n

- multimile A₁, A₂ , …., A_n sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

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

- x₁ x₂ …, x_n pot fi la randul lor vectori;

- A₁, A₂ …, A_n pot coincide.

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A₁,A₂ …,A_n si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare, incat poate fi considerat infinit, algoritmul neavand 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, cand 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: x₁, x₂ …,x_n

- 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 in care am ramas.

Concret:

- se alege primul element x, ce apartine lui A;

- presupunand generate elementele x₁,x₂ …,x_k , apartinand multimilor A₁,

A₂ …,A_k , se alege (daca exista) x_k+1 , primul element disponibil din multimea A_k+1 , apar doua posibilitati :

1) Nu s-a gasit un astfel de element, caz in care caz in care se reia cautarea considerand generate elementele  x₁,x₂ …,x_k+1 , iar aceasta se reia de la urmatorul element al multimii A_k ramas netestat;

2) A fost gasit, caz in care se testeaza daca acesta indeplineste anumite conditii de continuare aparand astfel doua posibilitati:

- indeplineste, caz in care se testeaza daca s-a ajuns la solutie si apar din nou doua posibilitati

- s-a ajuns la solutie, se tipareste solutia si se reia algoritmul considerand generate elementele x₁,x₂ …,x_k , (se cauta in continuare, un alt element al multimii A_k , ramas netestat);

- nu s-a ajuns la solutie, caz in care se reia algoritmul considerand generate elementele x₁,x₂ …,x_k , si se cauta un prim element x_k+2 € A_k.

- nu le indeplineste caz in care se reia algoritmul considerand generate elementele x₁,x₂ …,x_k , iar elementul x_k-1 se cauta intre elementele multimii A, ramase netestate.

Algoritmii se termina atunci cand nu exista nici un element x₁ € A₁ netestat.

Observatie: tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei. In cazul in care se cere o sigura solutie se poate forta oprirea, atunci cand a fost gasita.

Am aratat ca orice solutie se genereaza sub forma de vector. Vom considera ca generarea solutiilor se face intr-o stiva. Astfel, x₁ € A₁, se va gasi pe primul nivel al stivei, x₂ € A₂ se va gasi pe al doilea nivel al stivei, x_k € A_k se va gasi pe nivelul k al stivei. In acest fel, stiva (notata ST) va arata astfel:

ST

Nivelul k+1 al stivei trebuie initializat (pentru a alege, in ordine, elementele multimii k+1 ). Initializarea trebuie facuta cu o valoare aflata (in relatia de ordine considerata, pentru multimea A_k+1 ) inaintea tuturor valorilor posibile din multime. De exemplu, pentru generarea permutarilor multimii , orice nivel al stivei va lua valori de la 1 la n. Initializarea unui nivel (oarecare) se face cu valoarea 0. Procedura de initializare o vom numi INIT si va avea doi parametri: k (nivelul care trebuie initializat si ST (stiva)).

Gasirea urmatorului element al multimii A_k (element care a fost netestat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) este o variabila booleana. In situatia in care am gasit elementul, acesta este pus in stiva si AS ia valoarea TRUE, contrar (nu a ramas un element netestat) AS ia valoarea FALSE..

Odata ales un element, trebuie vazut daca acesta indeplineste conditiile de continuare (altfel spus, daca elementul este valid). Acest test se face cu ajutorul procedurii VALID (EV,ST,K).

Testul daca s-a ajuns sau nu la solutia finala se face cu ajutorul functiei SOLUTIE(k) iar o solutie se tipareste cu ajutorul procedurii TIPAR. Prezentam in continuare rutina Backtracking:

k:=1; init(1,st);

while k>0 do begin

repeat succesor (as, st, k) ; .

if as then valid(ev,st,k)

until (not as) or (as and ev) ;

if as then

if solutie(k) then tipar

else begin

k:=k+l;

init ( k, st );

end;

else k: k-1

end;

Observatie: Problemele rezolvate prin aceasta metoda necesita un timp indelungat. Din acest motiv, este bine sa utilizam metoda numai atunci cand nu avem la dispozitie un alt algoritm mai eficient. Cu toate ca exista probleme pentru care nu se pot elabora alti algoritmi mai eficienti, tehnica backtracking trebuie aplicata numai in ultima instanta.

Fiind data o tabla de sah, de dimensiune n, x_n, se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (dame sa nu se atace reciproc).

Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4x4, o solutie ar fi urmatoarea:

Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1, coloana 1.

A doua dama nu poate fi asezata decat in coloana 3.

Observam ca a treia dama nu poate fi plasata in linia 3. Incercam atunci plasarea celei de-a doua dame in coloana 4.

A treia dama nu poate fi plasata decat in coloana 2.

In aceasta situatie dama a patra nu mai poate fi asezata.

Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana 3, nici in coloana 4, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana 2.

A doua dama nu poate fi asezata decat in coloana 4.

Dama a treia se aseaza in prima coloana.

Acum este posibil sa plasam a patra dama in coloana 3 si astfel am obtinut o solutie a problemei.

Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

Pentru reprezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama).

Exemplu pentru solutia gasita avem vectorul ST ce poate fi asimilat unei stive.

Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita conditia: |st(i)-st(j)|=|i-j| ( diferenta, in modul, intre linii si coloane este aceeasi).

ST(4)

ST(3) In general ST(i)=k semnifica faptul ca pe linia i dama ocupa pozitia k.                       ST(2)

ST(1)

Exemplu: in tabla 4 x4 avem situatia:

st(1) i = 1

st(3)= 3 j = 3

|st(1) - st(3)| = |1 – 3| = 2

|i – j| = |1 – 3| = 2

sau situatia

st(1) = 3 i = 1

st(3) = 1 j = 3

|st(i) - st(j)| = |3 – 1| = 2

|i – j| = |1 – 3| = 2

Intrucat doua dame nu se pot gasi in aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema ca doua dame sa nu fie plasate in aceeasi diagonala. A proceda astfel, inseamna ca lucram conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea.

lata algoritmul, conform strategiei generate de backtracking:

- In prima pozitie a stivei se incarca valoarea 1, cu semnificatia ca in linia unu se aseaza prima dama in coloana.

- Linia 2 se incearca asezarea damei in coloana 1, acest lucru nefiind posibil intrucat avem doua dame pe aceeasi coloana.

- In linia 2 se incearca asezarea damei in coloana 2 , insa acest lucru nu este posibil, pentru ca damele se gasesc pe aceiasi diagonala (|st(1)-st(2)|=|1-2|);

- Asezarea damei 2 in coloana 3 este posibila.

- Nu se poate plasa dama 3 in coloana 1, intrucat in liniile 1-3 damele ocupa acelasi coloana.

- Si aceasta incercare esueaza intrucat damele de pe 2 si 3 sunt pe aceeasi diagonala.

- Damele de pe 2-3 se gasesc pe aceeasi coloana.

­- Damele de pe 2-3 se gasesc pe aceeasi diagonala.

­- Am coborat in stiva mutand dama de pe linia 2 si coloana 3 in coloana 4.

Algoritmul se incheie atunci cand stiva este vida. Semnificatia procedurilor utilizate este urmatoarea:

INIT - nivelul k al stivei este initializat cu 0;

SUCCESOR - mareste cu 1 valoarea aflata pe nivelul k al stivei in situatia in care aceasta este mai mica decat n si atribuie variabilei EV valoarea TRUE, in caz contrar, atribuie variabilei EV valoarea FALSE;

VALID - valideaza valoarea pusa pe nivelul k al stivei, verificand daca nu avem doua dame pe aceeasi linie (st(k)=st(i)), sau daca nu avem doua dame pe aceeasi diagonala (st(k)-st(i)=|k-i|)caz in care variabilei EV i se atribuie FALSE; in caz contrar, variabilei EV i se atribuie TRUE;

SOLUTIE - verifica daca stiva a fost completata pana la nivelul n inclusiv;

TIPAR - tipareste o solutie.