PREZENTARE

Backtrackingul este o tehnica de programare prin care o problema se rezolva prin generarea tuturor solutiilor acesteia. Structura de memorare a datelor folosita de backtracking se numeste STIVA.

Introducerea si citirea datelor dintr-o stiva se face numai in varful ei (s-ar putea sa va ajute daca va imaginati stiva ca o gamada de farfurii din care se poate lua sau pune o farfurie numai in varf).

In PASCAL, putem simula o stiva prin folosirea unui array; memorand numarul de elemente din stiva intr-o varibila de tip intreg. In continuare, eu voi nota aceasta variabila cu litera K. Backtrackingul se preteaza problemelor la care fiecare element al stivei apartine unei multimi cunoscute pe care o voi nota cu litera A. Algoritmul este destul de simplu: Pentru fiecare nivel al stivei se incearca toate elementele din A pana cand unul se potriveste; dupa care se trece pe nivelul urmator al stivei si se face acelasi lucru. Daca se ajunge la o solutie, aceasta se tipareste. Daca s-au epuizat toate elementele din A, fara ca vreunul sa se fi potrivit, se trece pe nivelul anterior al stivei. Se repeta procedeul de mai sus pana cand va fi mai putin de un element in stiva. De obicei, pentru a testa validitatea unui element al stivei, se foloseste o functie boleana pe care eu am numit-o VALID. Tot o functie boleana am folosit si pentru a verifica daca s-a ajuns la o solutie sau nu; si am numit-o SOLUTIE. TIPAR am numit procedura care tipareste o solutie gasita si ST array-ul stiva.

Sa incercam sa rezolvam urmatoarea problema:

Din fisierul suma.in se citeste numarul N. Acesta trebuie descompus in toate modurile posibile ca suma de numere strict pozitive distincte. Solutiile se scriu in fisierul suma.out.

Trebuie sa ne punem cateva intrebari inainte de a ne apuca sa implementam un backtracking:

1. Ce va face functia de validare?
2. Ce va face functia ce verifica daca s-a ajuns la o solutie?
3. Ce va reprezenta un nivel al stivei?
4. Care este lungimea maxima a stivei?

Raspunsurile la aceste intrebari sunt simple. un nivel al stivei va reprezenta unul din elementele sumei; deoarece numerele trebuie sa fie distincte, in validare verific daca numarul este mai mare sau egal decat precedentul si daca suma elementelor stivei pana la nivelul K este mai mica sau egala decat N; am ajuns la o solutie atunci cand suma este agala cu N. Am notat suma cu S. Pentru simplitate, voi considera lungimea maxima a stivei ca fiind egala cu N. Programul implementat de mine este unul iterativ. Se poate implementa si un backtracking recursiv dar acesta ar fi mai lent decat varianta iterativa.

var st:arraya1..1000i of word;

k,n,t1,s:word;

fis:text;

procedure citire; Aciteste n din fisierul de intrare dupa care deschide

fisierul de iesire, inchizand fisierul de intrareS

begin

assign(fis,'suma.in');

reset(fis);

read(fis,n);

close(fis);

assign(fis,'suma.out');

rewrite(fis);

end;

function valid:boolean; Averifica validitatea stivei pana la nivelul

kS

begin

valid:=true; Apresupun nivelul ca fiind validS

if k>1 then if staki<=stak-1i then valid:=false;

s:=0; Ainitializez sumaS

for t1:=1 to k do s:=s+stat1i; Acalculez sumaS

if s>n then valid:=false; Adaca suma e mai mare ca N atunci.S

end;

function solutie:boolean; Averifica daca o solutie a fost obtinutaS

begin

solutie:=(s=n); Adaca suma calculata in VALID e egala cu N.S

end;

procedure tipar; Ascriu solutia gasita in fisierul de iesireS

begin

for t1:=1 to k do write(fis,' + ',stat1i);

writeln(fis,''); Atrec pe linia urmatoareS

end;

procedure backtr; Aalgoritmul backtracking, in forma sa clasicaS

begin

fillchar(st,1000,0); Azerorizez stivaS

k:=1; Anivelul initial este 1S

while k>0 do begin Atotul se repeta pana cand K este mai mare decat 1S

repeat Aincerc toate elemtele din AS

inc(staki);

until ((staki>n) or ((staki<=n) and valid)); Apana se potrivesteS

if staki>n then begin Adaca nu a mers, merg pe nivelul anteriorS

staki:=0;

dec(k);

end else begin

if solutie then tipar; Adaca am gasit solutie o tiparescS

if k<n then inc(k); Asi merg pe nivelul urmator, daca se poateS

end;

end;

end;

begin

citire; Acitesc datele de intrare...S

backtr; Arulez un backtracking...S

close(fis); Asi inchid fisierul de iesireS

end.

Daca se cere doar o solutie la problema atunci putem forta oprirea programului dupa prima tiparire folosind comanda HALT. In cazul problemei de mai sus, procedura TIPAR ar deveni urmatoarea:

procedure tipar; Ascriu solutia gasita in fisierul de iesireS

begin

for t1:=1 to k do write(fis,' + ',stat1i);

close(fis); Adaca nu inchid fisierul, datele nu sunt salvateS

halt

end;

Daca se cere solutia optima, pur si simplu se retine intr-un array solutia cea mai buna gasita iar procedura TIPAR verifica daca solutia gasita este mai buna decat cea din array-ul cu solutia optima, caz in care vechea solutie este inlocuita de cea noua. Dupa rularea backtrackingului, acel array va contine solutia optima care se va tipari.

"OMORAREA" PROGRAMELOR

De multe ori (mai ales in cadrul concursurilor si olimpiadelor de informatica) exista un timp maxim de rulare a programelor (de ordinul secundelor). Backtrackingul este ceea ce se numeste o tehnica exponentiala de rezolvare a problemelor, avand o complexitate O(n!), care este asimilata uneia exponentiale (asta daca luam ca operatie de baza chiar generarea unei permutari).

Putem sacrifica din optimalitatea solutiei fortand oprirea programului dupa expirarea timpului regulamentar de executie. Acest lucru il putem realiza si prin folosirea unit-ului DOS al pachetului Borland Pascal dar acesta este lent asa ca mai bine lucram cu adrese de memorie (modalitate FOARTE rapida). La adresa de memorie $000:$046C este un numar care se incrementeaza automat la fiecare 55 de milisecunde, adica de 1000/55=18,(18) ori pe secunda. Deja este evident ce trebuie facut; la inceputul programului salvam numarul de la adresa $000:$046C iar cand numarul de la acea adresa va fi macar cu 18*SEC mai mare decat numarul salvat, blocam executia programului folosind procedura HALT. Am notat cu SEC timpul maxim de executie in secunde si am folosit 18*SEC si nu 18,18*SEC pentru a lasa putin timp pentru tiparirea rezultatului.

Pentru a utiliza mai usor adresa-timer de mai sus putem folosi o variabila de tip longint care sa fie egala cu numarul de la acea adresa astfel:

Var timp:longint absolute $000:$046C;

Mai folosim si o variabila longint "timpinitial".

La inceputul programului putem scrie

Timpinitial:=timp;

Si in procedura de validare ceva de genul

If timp-timpinitial>=(18*SEC) then begin

Tiparesterezultatul;

Close(fis)

Halt;

End;;

Trebuie doar sa adaptati metoda la problema pe care o rezolvati; oricum, cred ca ati prins ideea. (sau. oare?)

AVANTAJELE SI DEZAVANTAJELE BACKTRACKINGULUI

Am facut aici o mica lista cu avantajele si dezavantajele backtrackingului (dupa parerea mea, desigur).

AVANTAJE:

1. Este usor de gandit

2. Este usor de implementat

3. Nu necesita prea mult studiu

4. Se obtine mereu solutia optima (daca asta este cerinta)

5. Nu foloseste decat foarte putina memorie (fata de programarea dinamica)

DEZAVANTAJE:

Timpul foarte mare de rulare

Eu nu recomand backtrackingul atunci cand se cere solutia optima datorita acestui singur dezavantaj al sau dar il puteti folosi, daca nu aveti o idee mai buna. (backtrackingul "omorat este deja o prezenta obisnuita in cadrul olimpiadelor de informatica). La faza judeteana de informatica, in multe cazuri, se poate merge la faza urmatoare DOAR cu backtracking, datorita testelor de mici dimensiuni. (din nou, dupa parerea mea.).

Un elev care nu are nici o treaba cu concursurile de informatica si nu vrea decat o nota buna la scoala poate invata o rutina backtracking "pe de rost" pentru ca mai apoi sa implementeze programele mecanic, doar modificand procedurile de validare, gasire a solutiei si de tiparire. Din motive evidente, nu cred ca este un lucru bun. cu toate ca peste 90% din elevi fac lucrul asta.

 

 

COMPETITIA IMPLEMENTARILOR

Fiecare lucrare scrisa ce incearca sa explice aceasta tehnica de programare are si un exemplu de implementare. De departe cea mai cunoscuta este cea prezentata de domnul Tudor Sorin in cartile sale (cu toate ca mie mi se pare ca e destul de greoaie). Desigur ca toate aceste implementari nu fac decat sa aplice algoritmul pe care l-am prezentat la inceputul articolului. Am realizat o "competitie" intre 3 implementari: cea prezentata de mine la inceputul articolului; faimoasa implementare Tudor Sorin si o varianta propusa de domnul Alin Burta. Am folosit aceste 3 implementari pentru a rezolva problema propusa la inceputul articolului; pentru N=60.

Implementarea mea si cea a domnului Burta au generat toate permutarile intr-un timp identic: 1,69 secunde in timp ce implementarea "Tudor Sorin" a terminat in 1,83 secunde. Am folosit aceleasi conditii de validare si gasire a solutiei. Implementarea cea mai lenta a fost si cea mai dificil de implementat deci.. concluziile sunt usor de tras.

PROBLEME PROPUSE

1. Din fisierul ANAG.IN se citeste un cuvant de maxim 10 litere. Sa se scrie in fisierul ANAG.OUT toate anagramele posibile ale cuvantului. (prin anagramare se intelege amestecarea literelor unui cuvant).

2. Din fisierul PROD.IN se citeste numarul intreg N; 0<N<1'000. Sa se scrie in fisierul PROD.OUT toate descompunerile lui N ca produs de numere naturale.

3. Din fisierul BANI.IN se citeste numarul intreg N; 0<N<100'000. Sa se scrie in fisierul BANI.OUT toate modurile de a plati suma de bani N daca aveti la dispozitie bancnote de 100'000, 50'000, 10'000, 5'000 si 1000.

4. O scara are N trepte. 0<N<50. N se citeste din fisierul SCARA.IN. In cate moduri poate fi urcata scara daca se pot face doar pasi de cate 1 sau 2 trepte. Rezultatul se scrie in fisierul SCARA.OUT. (poate va vine o idee mai buna decat un backtracking.)