Referat Metoda Backtracking

Mai jos puteti citi fragmente din Referat Metoda Backtracking si de asemenea puteti face Download Referat Metoda Backtracking

Citeste fragmente din Referat Metoda Backtracking

Metoda Backtracking I.1. Necesitate Deseori în practică trebuie să rezolvăm probleme care au un număr foarte mare de soluţii posibile. De cele mai multe ori însă, nu ne interesează toate soluţiile, ci numai o parte dintre ele, care îndeplinesc anumite condiţii specifice problemei. Pentru astfel de probleme este indicată folosirea metodei backtracking care evită generarea soluţilor inutile. Desigur că o persoană cu o gândire simplistă ar putea spune : „ generăm toate soluţiile, apoi le alegem pe cele care îndeplinesc condiţiile cerute”. Foarte simplu, dar... oare şi eficient ? Ce rost ar avea să se genereze nişte soluţii care oricum nu convin? Din punctul de vedere al timpului necesar calculatorului pentru a obţine toate soluţiile, cât de realistă este o astfel de abordare? I.2. Descrierea metodei Prima idee pe care trebuie să o reţinem ar fi: nu se generează toate soluţiile posibile, ci numai acelea care îndeplinesc anumite condiţii specifice problemei, numite condiţii de validare (în unele lucrării de specialitate acestea mai sunt numite şi condiţii interne). Soluţiile problemei vor fi generate succesiv într-o stivă implementată sub forma unui vector pe care îl vom nota st. ☻REAMINTIM : ► În cadrul unui program, utilizatorul îşi poate defini o structură numită stivă. Aceasta funcţionează după principiul LIFO ( „ Last in First Out”, în traducere „ Ultimul intrat, primul ieşit” ). Cel mai simplu mod de a implementa o stivă este cu ajutorul unui vector st. Pentru a simula caracterul de stivă, privim vectorul st ca şi cum elementele sale ar fi aşezate „ pe verticală”, unul peste altul. Dacă la un moment dat stiva st conţine elementele st[1], st[2], ..., st[p], atunci poziţia p a elementului cel mai de sus, se numeşte vârful stivei. În general, poziţia unui element în vectorul stivă este numită nivel al stivei. Adăugarea şi extragerea de elemente în /din stivă, se poate face numai pe la capatul de sus al acesteia În general , numarul de elemente care intră în componenţa soluţiilor poate să difere de la o soluţie la alta. Pentru început vom considera cazul în care toate soluţiile au acelaşi număr de elemente, întrucât acesta se întâlneşte cel mai frecvent. Vom nota cu „n” numărul de elemente ale soluţiilor reprezentate pe stiva st. Astfel, o configuraţie a vectorului-stivă st format din elementele (st[1], st[2], ..., [n]), se va numi soluţie finală. Tot pe caz general, fiecare componentă st[i] poate lua valori într-o anumită mulţime Si , cu i=1,2,...,n. Ansamblul mulţimilor Si , adică produsul cartezian S1xS2xSn, se numeşte spaţiul soloţiilor posibile. Din nou vom face o particularizare, considerând pentru început că toate componentele st[i] ( i=1,2,...,n) iau valori în aceeaşi mulţime S. În continuare trebuie să raspundem la întrebarea: cum putem să evităm generarea tuturor soluţiilor posibile şi să le obţinem numai pe acelea care îndeplinesc condiţiile de validare? Fiecare soluţie va fi construită în stiva st pas cu pas, completând stiva nivel cu nivel. Astfel, pentru a obţine o soluţie finală cu n nivele, de forma st=( st[1], st[2], ..., st[n] ), vom „trece” prin nişte configuraţii intermediare ale stivei numite soluţii parţiale. Cu alte cuvinte,o soluţie parţială este o configuraţie a stivei de forma (st[1], st[2], ..., st[p] ), unde p va lua succesiv toate valorile de la 1 la n. La rândul său, fiecare soluţie parţială se obţine prin completarea cu încă un nivel a soluţiei parţiale anterioarei. I.3. Implementarea metodei. Varianta recursivă. Datorită faptului că fiecare nouă configuraţie a stivei se obţine pornind de la precedenta, algoritmi backtracking se pot implementa foarte elegant într-o manieră recursivă. Putem scrie şi programe nerecursive, dar acestea sunt mai laborioase, de aceea vom începe cu varianta recursivă a metodei backtracking. În varianta recursivă, soluţiile finale st=(st[1], st[2], ... , st[n] ) sunt generate în cadrul proceduri recursive {bktr(p:integer);}, unde p reprezintă nivelul până la care s-a ajuns pe stivă. Cu alte cuvinte, la fiecare execuţie din lanţul de auto-apeluri, procedura bktr „tratează” nivelul p al stivei. De fapt, această procedură implementează algoritmul recursiv de backtracking, pe care îl descriem în continuare în pseudocod: Pentu pval de la la execută început st[p]← pval dacă valid(p) returnează true atunci dacă atunci apel tipar (p) altfel auto-apel bktr (p+1) sfârşit. Într-un ciclu prin variabila pval vor trece pe rând toate valorile care ar putea fi încercate pe nivelul pe al stivei. Plecăm de la presupunerea că aceste valori sunt succesive într-un interval delimitat de capetele v1 şi vn, caz în care putem folosi un ciclu cu contor. La fiecare pas al ciclului, pentru fiecare dintre valorile variabilei pval: ▫ Memorăm respectiva valuare pe nivel p, prin atribuirea st [p] ← pval. Obţinem astfel soluţia (st[1],st[2], ..., st[p] ), care momentan nu are decât statutul de soluţie parţială; ▫ Verificăm dacă această soluţie este validă, testând valuarea returnată de către funcţia valid(p). În caz afirmativ (adică dacă funcţia valid(p) ar returna true), atunci trebuie să verificăm dacă respectiva soluţie este şi finală (de obicei condiţia de soluţie finală este una singură şi poate fi testată într-un if, dar putem folosi şi o funcţie pentru aceasta); √ În caz afirmativ afişăm soluţia, apelând procedura tipar(p); √ În caz contrar, avem de-a face cu o soluţie validă (ne aflăm pe ramura „dacă valid(p)” ), dar care nu este şi finală. Fiid vorba de o soluţie parţială, trecem la nivelul următor pentru a o completa. Cum anume ? Trebuie incrementat p-ul, lucru care se realizează prin auto-apelul bktr(p+1). Astfel, se va relua de la capăt algoritmul, dar cu p+1 în loc de p. » Procedura recursivă {bktr (p:integer) ; } implementează algoritmul de breacktracking, „tratând” la fiecare execuţie un nivel p al stivei. Pe fiecare nivel vor fi încercate succesiv elementele u[1] şi u[2] ale vectorului u (în speţă literele ‚A’ şi ‚M’).Cum anume ? în ciclul for controlul pval va parcurge poziţiile elementelor vectorului u, care sunt de la 1 la 2; la fiecare pas, pe nivelul p va fi pus elementul din vectorul u al cărui indice este pval (prin atribuire st[p] : = u [pval] ). Mai departe, algoritmul de bracktracking este cel mai standard, prezentat în artea de teorie: dacă valoarea st[p] a generat o soluţie (st[1], st[2], ...,st[p] ) valid (dacă funcţia valid[p] a returnat TRUE ), atunci: dacă soluţia respectivă e şi finală (p=n, pentru că se cer secvenţele de n litere ‚A’ şi ‚M’ ) atunci o tipărim (apelând procedura tipar(p) ); în caz contrar, trecem la nivelul următor (pentru a completa soluţia cu un nou nivel ), prin auto-apel bktr (p+1). I.4. Varianta ne-recursivă a metodei backtracking. 2 „ ᨀtăţii), folosim acelaşi exemplu: generarea permutărilor de n elemente. La fel ca şi în varianta recursivă, soluţiile se construiesc intr-un vector-stivă st, şi notăm cu p nivelul vârfului stivei. Varianta ne-recursivă foloseşte aceleaşi subprograme, iniţializări, tipar(p) şi valid(p) pe care le-am prezentat pe larg în varianta recursivă. Acum vom aminti doar acţiunea lor. Procedura { iniţializări ; } citeşte datele de intrare şi iniţializează stiva. Procedura { tipar (p:integer) ; } afişează o soluţie cu p nivele reprezentată de configuraţia (st[1], st[2], ... , st[p] ). Funcţia {valid (p:integer) : boolean; } va returna true dacă soluţia (st[1], st[2], ... ,st[p] ) este validă, respectiv false în caz contrar. Mai întâi descriem acest algoritm în pseudocod. p←1; st[p] ← 0; cât timp p>0 execută început dacă atunci început st[p] ← dacă valid (p) returnează true atunci dacă atunci apel tipar (p) altfel început p ← p+1; st[p] ← 0; sfârşit sfârşit altfel p ←p-1; sfârşit Plecăm de la primul nivel de pe stivă, iniţializând cu 1 indicele p al vîrfului stivei. De asemenea, punem pe acest prim nivel valoarea „de plecare” 0. Algoritmul evoluează într-un ciclu „dirijat” de p. La fiacare pas al ciclului „se tratează „nivelul” al stivei. Mai întâi trebuie să testăm dacă pe nivelul p mai putem încerca vreo valuare. Altfel spus, dacă mai există valori din mulţimea soluţiilor posibile care nu au fost încercate pe nivel p. ► În caz afirmativ: » Atribuim elementului st[p] o nouă valuare din mulţimea soluţiilor posibile (cu alte cuvinte încercăm o nouă valuare pe nivel p); » Dacă soluţia (st[1], st[2], ... , st[p] ) astfel generată este validă (adică dacă funcţia valid (p) a returnat true), atunci: - dacă soluţia în cauză este şi finală atunci o tipărim, apelând procedura tipar (p); - în caz contrar, trecem la nivelul următor al stivei prin atribuirea p ← p+1, apoi re-iniţializăm acest nou nivel p prin atribuirea st[p] ← 0. ► În caz contrar, respectiv dacă pe nivelul p nu mai putem încerca nici o valuare, nu ne rămâne altceva de făcut decât „pasul înapoi” la nivelul anterior, prin decrementarea lui p ( p ← p-1). Algoritmul ne-recursiv de backtracking va fi implementat într-o procedură back fără parametri. În programul principal avem doar două apeluri, pentru procedurile iniţializări şi back. Să se scrie un programcare, pentru un plan de aşezare dat, produce harta corespunzătoare. Dacă există mai multe harţi posibile, se vor determina toate. Pentru planu de aşezare dat există măcar o hartă de aşezare. Soluţie: Prezentăm direct programul cu comentarile necesare înţelegeri algoritmului. programul efectul_domino; type ve1=array[1..4] of integer; ve2=array[1..10] of integer; const dx:ve1=(-1,0,1,0); dy:ve1=(0,1,0,-1); var a,b:array[1..7,1..8] of integer; f:text; p,q,r:array[1..28] of integer; i,j,k:byte; n:integer; function intab(x,y:byte):Boolean; begin intab:=(x in [1..7] ) and (y in [1..8] ); end; function piesa( u,v:byte): byte; var i:byte; begin piesa:=0; for i:=1 to 28 do if (p[i], q[i]]=[u,v]) then if (r[i]=0) then begin r[i]:=1; piesa:=i; exit; end else exit; end; function vecin( x,y:byte): Boolean; var i, xv, yv: byte; begin vecin:=false; for i:=1 to 4 do begin xv:=x+dx[i]; yv:=y+dy[i]; if intab( xv,yv) and (b[xv,yv]<>0) then begin vecin:=true; exit; end; end end; procedure scrie; var i,j: byte; begin wrteln(‘ sol.’, n); for i:=1 to 7 do begin for j:=1 to 8 do write (b[i,j]: 3); writeln; end; procedure caut ( x,y,nr: byte); var x1, x3, y1, y3, i, t, g: byte; begin for i:=1 to 4 do begin x1:=x+dx[i]; y1:=y+dy[i]; if intab( x1,y1) then if b[x1,y1]=0 then begin t:=piesa (a[x,y], a[x1,y1]); if t <> 0 then begin b[x1,y1]:=t; b[x,y]:=t; if nr=28 then begin n:=n+1; scrie; readln; end else begin g:=0; for x3:=1 to 7 do begin for y3:=1 to 8 do if intab(x3,y3) then if b[x3, y3]=0 then if vecin( x3, y3) then begin g:=1; caut( x3, y3, nr+1); break; end; if g=1 then break; end; end; b[x,y]:=0; b[x1,y1]:=0; r[t]:=0; end; end; end; end; begin assign( f,’ f1.txt’); reset(f); for i:=1 to 7 do for j:=1 to 8 do begin read(f, a[I,j]); b[i,j]:=0; end; for i:=0 to 6 do for j:=i to 6 do begin k:=k+1; p[k]:=i: q[k]:=j; end; n:=0; caut (1,1,1); close( f ); end. 쥁@