BackTracking - nivelele arborelui (rasturnat pe orizontala)

Pentru a preciza mai exact in ce consta aceasta metoda, vom relua pe un exemplu concret cele spuse deja. Avem urmatoarea problema: se cere generarea tuturor permutarilor unei multimi de n elemente ce nu contin elementul x (dat dinainte) pe primele doua pozitii. Conform celor afirmate, este suficient sa “construim” modelul abstract - graful - (mai precis arborele) tuturor permutarilor celor n elemente. Apoi, printr-o parcurgere exhaustiva a nodurilor sale, prin una din metodele BFS sau DFS, sa pastram numai acele noduri ce verifica in momentul “vizitarii” conditia impusa (lipsa lui x de pe primele doua pozitii).

Observam ca aceasta metoda necesita folosirea in scopul memorarii dinamice a drumului parcurs (in timpul cautarii solutiei) a mecanismului de stiva, fapt sugerat chiar de numele ei: tracking, adica inregistrarea pistei parcurse. Acest mecanism de stiva, care permite atit memorarea pistei cit si revenirea – back-tracking-ul, este unul din mecanismele de baza ce este folosit pe scara larga in procedurile de gestiune dinamica a datelor in memorie. In plus, exista unele cazuri particulare de probleme in care solutia cautata se obtine in final prin “varsarea” intregului continut al stivei si nu doar prin “nodul” ultim vizitat, aflat in virful stivei.

Exemplul cel mai potrivit de problema ce necesita o strategie de rezolvare backtracking este Problema Labirintului: se cere sa se indice, pentru o configuratie labirintica data, traseul ce conduce catre iesirea din labirint. Iata un exemplu sugestiv:

Observati cum, dupa 15 pasi, este necesara o revenire (backtracking) pina la casuta 6, de unde se continua pe o alta pista. “Pista falsa” a fost memorata in stiva, element cu element, iar revenirea se va realiza prin eliminarea din stiva tot element cu element. Cind in virful stivei reapare casuta cu numarul 6, stiva incepe din nou sa creasca memorind elementele noului drum. In final stiva contine in intregime solutia: drumul corect catre iesirea din labirint.

In consecinta, indiferent de forma particulara ce o poate lua sau de modul in care este “citita” in final solutia, esentialul consta in faptul ca backtracking-ul este o metoda de programare ce contine obligatoriu gestiune de stiva. Lipsa instructiunilor, explicite sau “transparente”, de gestionare a stivei intr-un program (de exemplu, lipsa apelului recursiv), este un indiciu sigur de recunoastere a faptului ca acel algoritm nu foloseste metoda sau strategia de rezolvare BackTracking.

Tot o metoda back-tracking este si metoda de programare cunoscuta sub numele programare recursiva. Ea este mai utilizata decit metoda clasica BackTracking, fiind mai economicoasa din punctul de vedere al minimizarii efortului de programare. Aceasta metoda se reduce la construirea, in mod transparent pentru programator, a arborelui apelurilor recursive, traversarea acestuia prin apelarea recursiva (repetata) si efectuarea actiunilor corespunzatoare in momentul “vizitarii” fiecarui nod al arborelui. Apelarea recursiva constituie “motorul vehiculului” de traversare si are doar rolul de a permite traversarea arborelui. Gestionarea stivei apelurilor recursive si revenirea - back-tracking-ul ramine in sarcina mediului de programare folosit si se efectueaza intr-un mod mascat pentru programator. Din acest punct de vedere, programatorului ii revine sarcina scrierii corecte a instructiunii de apel recursiv si a instructiunii ce “scurt-circuiteaza” bucla infinita a apelurilor recursive. Singurele instructiuni care “fac treaba”, in sensul rezolvarii propriuzise a problemei respective, sint cele cuprinse in corpul procedurii.

De exemplu, iata cum arata in limbajul de programare Pascal procedura generala de generare a permutarilor in varianta recursiva si arborele de generare a permutarilor multimii (n=3), pe nivele:

Procedure Permut(k:byte;s:string);                           

Var i:byte;tmp:char;

Begin

If k=n then begin

For i:=1 to n do Write(s[i]);

Write(';');

end else

For i:=k to n do begin

tmp:=s[i];s[i]:=s[k];s[k]:=tmp;

Permut(k+1,s);

end;

End;

Nivelele arborelui (rasturnat pe orizontala)

1 2 3

2 ---- 3 Fiecare nivel al arborelui corespunde unei pozitii in sirul

permutarilor. Astfel, pe prima

1 <

3 ---- 2 pozitie (nivelul 1) pot fi oricare din cele trei elemente:

1, 2, 3. Pe pozitia urmatoare pot

/

---- 3 fi oricare din celelalte doua elemente ramase:2,3;1,3;1,2.

Start   -- 2 < Pe al treilea nivel si ultimul

3 ---- 1 vor fi numai elementele ramase (cite unul).

Generarea permutarilor consta in construirea

1 ---- 2 si parcurgerea arborelui permutarilor: odata ajunsi cu

parcurgerea la un capat din dreapta

3 <

2 ---- 1 vom afisa de fiecare data “drumul” de la

“radacina” la “frunza” terminala.

Observam ca arborele permutarilor este identic cu arborele apelurilor recursive si ca controlul si gestiunea stivei se face automat, transparent fata de programator. Instructiunilor de control (din background) le revine sarcina de a pastra si de a memora, de la un apel recursiv la altul, string-ul s ce contine permutarile. Desi aceasta procedura recursiv de generare a permutarilor pare o varianta de procedura simpla din punctul de vedere al programatorului, in realitate, ea contine intr-un mod ascuns efortul de gestionare a stivei: incarcarea-descarcarea stringului s si a intregului k. Acest efort este preluat in intregime de instructiunile incluse automat de mediul de programare pentru realizarea recursivitatii.

Avantajul metodei back-tracking este faptul ca efortul programatorului se reduce la doar trei sarcini:

“construirea” grafului particular de cautare a solutiilor

adaptarea corespunzatoare a uneia din metodele generale de traversare-vizitare a grafului in situatia respectiva (de exemplu, prin apel recursiv)

adaugarea instructiunilor “ce fac treaba” care, fiind apelate in mod repetat in timpul vizitarii nodurilor (grafului solutiilor posibile), rezolva gradat problema, gasind sau construind solutia.

Actiunea de revenire ce da numele metodei, backtracking - revenire pe “pista lasata”, este inclusa si este efectuata de subalgoritmul de traversare a grafului solutiilor posibile. Acest subalgoritm are un caracter general si face parte din “zestrea” oricarui programator. In cazul particular in care graful solutiilor este arbore, atunci se poate aplica intotdeauna cu succes metoda programarii recursive care conduce la un cod-program redus si compact.

Prezentam din nou procedura generala DepthFirstSearch (DFS) de traversare a unui graf in varianta recursiva (ce “construieste” de fapt arborele de traversare a grafului avind ca radacina nodul de pornire) pentru a pune in evidenta cele spuse.

Procedura DFS(v:nod);

Viziteaza v;

Marcheaza v; // v devine un nod vizitat //

Cit timp (exista w nemarcat nod adiacent lui v) executa DFS(w);

Exista situatii in care, la unele probleme, putem intilni solutii tip-backtracking fara insa a se putea sesiza la prima vedere prezenta grafului de cautare asociat si actiunea de traversare a acestuia, ci doar prezenta stivei. O privire mai atenta insa va conduce obligatoriu la descoperirea arborelui de cautare pe graful solutiilor, chiar daca el exista doar intr-o forma mascata. Acest fapt este inevitabil si constituie esenta metodei – cautare (generare) cu revenire pe pista lasata.

Back-tracking-ul, metoda generala si cu o larga aplicabilitate, fiind reductibila in ultima instanta la traversarea spatiului -grafului de cautare- a solutiilor, are marele avantaj ca determina cu certitudine toate solutiile posibile, cu conditia ca graful asociat de cautare a solutiilor sa fie corect. Dar ea are marele dezavantaj ca necesita un timp de executie direct proportional cu numarul nodurilor grafului de cautare asociat (sau numarul cazurilor posibile). In cele mai multe cazuri acest numar este exponential (eⁿ) sau chiar mai mare, factorial (n!), unde n este dimensiunea vectorului datelor de intrare. Acest fapt conduce la o durata de executie de marime astronomica facind intr-un astfel de caz algoritmul complet inutilizabil, chiar daca el este corect teoretic. (De exemplu, daca solutionarea problemei ar necesita generarea tuturor celor 100! permutari (n=100), timpul de executie al algoritmului depaseste orice imaginatie.) In astfel de situatii, in care dimensiunea spatiului de cautare-generare a solutiilor are o astfel de dependenta in functie de n (fiind o functie de ordin mai mare decit functia polinomiala), este absolut necesara imbunatatirea acestei metode sau inlocuirea ei. Nu este insa necesara (si de multe ori nici nu este posibila!) abandonarea modelului abstract asociat - graful solutiilor posibile, cu calitatile si proprietatile sale certe - ci este necesara doar obtinerea unei durate de executie de un ordin de marime inferior printr-o alta strategie de parcurgere a spatiului de cautare.

Greedy.

In strategia backtracking cautarea solutiei, adica vizitarea secventiala a nodurilor grafului solutiilor cu revenire pe urma lasata, se face oarecum “orbeste” sau rigid, dupa o regula simpla care sa poata fi rapid aplicata in momentul “parasirii” unui nod vizitat. In cazul metodei (strategiei) greedy apare suplimentar ideea de a efectua in acel moment o alegere. Dintre toate nodurile urmatoare posibile de a fi vizitate sau dintre toti pasii urmatori posibili, se alege acel nod sau pas care asigura un maximum de “cistig”, de unde si numele metodei: greedy = lacom. Evident ca in acest fel poate sa scada viteza de vizitare a nodurilor – adica a solutiilor ipotetice sau a solutiilor partiale – prin adaugarea duratei de executie a subalgoritmului de alegere a urmatorului nod dupa fiecare vizitare a unui nod. Exista insa numerosi algoritmi de tip greedy veritabili care nu contin subalgoritmi de alegere. Asta nu inseamna ca au renuntat la alegerea greedy ci, datorita “scurtaturii” descoperite in timpul etapei de analiza a problemei, acei algoritmi efectueaza la fiecare pas o alegere fara efort si in mod optim a pasului (nodului) urmator. Aceasta alegere, dedusa in etapa de analiza, conduce la maximum de “profit” pentru fiecare pas si scurteaza la maximum drumul catre solutia cautata.

Aparent aceasta metoda de cautare a solutiei este cea mai eficienta, din moment ce la fiecare pas se trece dintr-un optim (partial) intr-altul. Totusi, ea nu poate fi aplicata in general ci doar in cazul in care exista certitudinea alegerii optime la fiecare pas, certitudine rezultata in urma etapei anterioare de analiza a problemei. Ori, dezavantajul este ca, la majoritatea problemelor dificile, etapa de analiza nu poate oferi o astfel de “pista optima“ catre solutie. Un alt dezavantaj al acestei strategii este ca nu poate sa conduca catre toate solutiile posibile ci doar catre solutia optima (din punct de vedere a alegerii efectuate in timpul cautarii solutiei), dar poate oferi toate solutiile optime echivalente.

Programarea dinamica.

Este o metoda sau strategie ce isi propune sa elimine dezavantajele metodei recursive care, in ultima instanta, am vazut ca se reduce la parcurgerea in adincime a arborelui apelurilor recursive (adica backtracking). Aceasta metoda se apropie ca idee strategica de metoda Greedy, avind insa unele particularitati.

Pentru a o intelege este necesara evidentierea dezavantajului major al recursivitatii. El consta din cresterea exagerata si nerentabila a efortului de executie prin repetarea ineficienta a unor pasi. Urmarind arborele apelurilor recursive se observa repetarea inutila a unor cazuri rezolvate anterior, calculate deja inainte pe alta ramura a arborelui. Metoda eminamente iterativa, programarea dinamica elimina acest dezavantaj prin “rasturnarea” procedeului de obtinere a solutiei si implicit a arborelui apelurilor recursive. Printr-o abordare bottom-up (de la baza spre virf) ea reuseste sa elimine operatiile repetate inutil in cazul abordarii top-down (de la virf spre baza).

Cu totii am invatat ca, daca vrem sa calculam “cu mina” o combinare sau un tabel al combinarilor, in loc sa calculam de fiecare data combinari de n luate cite k pe baza definitiei recursive: C(n,k)=C(n-1,k-1)+C(n-1,k) cind n,k>0, sau, C(n,k)=1 cind k=0 sau n=k, este mult mai eficient sa construim Triunghiul lui Pascal, pornind de la aceeasi definitie a combinarilor.

C(4,2)

C(3,1)           + C(3,2)

C(2,0) + C(2,1) C(2,1) + C(2,2)

C(1,0) + C(1,1) C(1,0) + C(1,1) 1

1 1 1

Observati cum in arborele apelurilor recursive apar apeluri in mod repetat pentru calculul aceleasi combinari. Acest efort repetat este evitat prin calcularea triunghiului lui Pascal in care fiecare combinare va fi calculata o singura data.

In mod asemanator, aceeasi diferenta de abordare va exista intre doi algoritmi de solutionare a aceleasi probleme, unul recursiv – backtracking - si altul iterativ - proiectat prin metoda programarii dinamice.

Dezavantajele acestei metode provin din faptul ca, pentru a tine minte pasii gata calculati si a evita repetarea calcularii lor (in termeni de grafuri, pentru a evita calcularea repetata a unor noduri pe ramuri diferite ale arborelui apelurilor recursive), este nevoie de punerea la dispozitie a extra-spatiului de memorare necesar si de un efort suplimentar dat de gestiunea de memorie suplimentara.