Referat Backtracking Generalizat In Plan

Mai jos puteti citi fragmente din Referat Backtracking Generalizat In Plan si de asemenea puteti face Download Referat Backtracking generalizat in plan

Citeste fragmente din Referat Backtracking Generalizat In Plan

Backtracking generalizat în plan Problema labirintului Metoda Backtracking Introducere Metoda backtracking foloseşte la rezolvarea multor probleme. Pentru ca o problemă să poată să fie rezolvată cu metoda backtracking, ea trebuie să îndeplinească simultan următoarele condiţii: - poate avea mai multe soluţii, acestea fiind puse sub formă de vector ca de exemplu S(x1,x2,x3,...xn), unde x1ЄA1, x2ЄA2,..., xnЄAn - mulţimile A1, A2, A3, ..., An sunt mulţimi finite, având elementele aflate într-o ordine bine stabilită, ele putând să fie chiar identice. În acest caz, vectorul care conţine soluţii se numeşte stivă. Descrierea metodei Se alege primul element x1 din A1. Se repetă într-o structură repetitivă până când nu mai există elemente netestate din mulţimea A1; - se presupune că am ajuns la elementul xk din mulţimea Ak şi se doreşte găsirea unui element xk+1 din mulţimea Ak+1. Acesta trebuie să îndeplinească condiţiile de existenţă a unui astfel de element, impuse de problemă, iar dacă: - îndeplineşte aceste condiţii atunci trebuie să îndeplinească alte condiţii impuse de problemă, prin care se determină dacă el ar putea face parte din soluţie. Dacă: - da, atunci se testează dacă şirul de elemente este o soluţie a problemei. Dacă: - da, atunci se tipăreşte vectorul care conţine aceste soluţii; - nu, atunci se trece pe următorul nivel din şir (k:=k+1); - nu, nu îndeplineşte condiţiile de a face parte din soluţie, atunci se trece la următorul element netestat din mulţimea Ak; - nu mai poate exista un element pe nivelul k, atunci se trece la nivelul anterior şi se încearcă aici găsirea unui element; - repetiţia se termină când am ajuns pe nivelul 0. Backtraking generalizat în plan Metoda Backtracking în plan are câteva modificări: - stiva conţine mai multe coloane (este dublă, triplă, ...); - trebuiesc codificate oarecum direcţiile prin numere, litere, elemente, etc. Problema labirintului se poate rezolva după un algoritm de backtracking generalizat în plan. Ea va fi prezentată în continuare. Problema labirintului. Enunt: Se dă un labirint sub formă de matrice de m linii şi n coloane. Fiecare element al matricii reprezintă o cameră. Într-una din camerele labirintului se găseşte un om. Se cere să se afle toate soluţiile ca acel om să iasă din labirint, fără să treacă de două ori prin aceeaşi cameră. Generalizare. Această variantă a problemei este varianta în care fiecare cameră are pereţii proprii în părţile laterale. Există o altă variantă în care fiecare element al matricii este fie un culoar, fie un perete, putându-se trece doar dintr-un culoar în altul. Aici, se poate trece dintr-o cameră în alta, doar dacă între cele două camere nu există perete (camerele sunt imediat apropiate). Prin labirint, putem trece dintr-o cameră în alta doar mergând în sus, în jos, la stânga sau la dreapta, nu şi în diagonală. Codificare. Principiul backtracking generalizat spune că trebuies codificate direcţiile. În aceste caz vor fi codificate şi combinaţiile de pereţi ai fiecărei camere. Asftel, un element al camerei va fi un element al unei matrici cu n linii şi n coloane, având valori de la 0 la 15. În sistemul binar, numerele 0..15 sunt reprezentate ca 0..1111, fiind memorate pe 4 biţi consecutivi. Vom lua în cosiderare toţi cei 4 biţi, astfel numerele vor fi 0000..1111. Fiecare din cei 4 biţi reprezintă o direcţie, iar valoarea lui ne spune dacă în acea direcţie a camerei există sau nu un perete. Vom reprezenta numărul astfel: nr = b1 b2 b3 b4 (b = bit) Asftel, b1 indică direcţia nord (sus), b2 indică direcţia est (dreapta), b3 indică direcţia sud (jos) iar b4 indică direcţia vest (stânga). Valorile unui bit sunt, fireşte, 0 şi 1. 0 înseamnă că în direcţia respectivă nu există un perete, iar 1 înseamnă că în direcţia respectivă există un perete şi pe acolo nu se poate trece. De exemplu: 0111 - camera aceasta are pereţi în dreapta, în jos şi în stânga, iar în sus este drum liber spre camera vecină. Acest număr este de fapt 7, aşa fiind notat în matricea labirintului. În ceea ce priveşte direcţiile, vom reţine doar coordonatele unde se află omul din labirint, acestea fiind schimbate în funcţie de drumul pe care-l urmează. Vom avea o stivă triplă astfel: - coloana 1 va indica direcţia. Aceasta va fi de la 1 la 4, 1 reprezentând sus, 2 reprezentând dreapta, 3 reprezentând jos, iar 4, stânga. - coloana 2 va reţine indicele de linie al camerelor parcurse în labirint - coloane 3 va reţine indicele de coloană al camerelor parcurse în labirint - fiecare linie va însemna o cameră, cu indicele de linie şi de coloană Astfel, în cazul în care direcţia este 1 (sus), linia se va micşora cu 1, dacă direcţia este 2 (dreapta), coloana se va mări cu 1, dacă direcţia este 3 (jos), linia se va mări cu 1, iar dacă direcţia este 4 (stânga), coloana se va micşora cu 1. Exemplu: Să presupunem că introducem următoarea matrice: 5 7 5 13 3 8 0 4 14 5 5 7 11 2 6 15 Această matrice corespunde labirintului din desen: & ( , . 4 6 : < J L P R p r x z € ‚ P R ^ ` T Punctul de pornire din acest labirint este linia 3, coloana 4. Astfel, avea 3 soluţii de a ieşi din labirint, fără a trece de două ori prin aceeaşi cameră: (3,4)-(2,4)-(2,3)-(1,3)-ieşire (3,4)-(2,4)-(2,3)-(2,2)-(2,1)-(1,1)-ieşire (3,4)-(2,4)-(2,3)-(3,3)-(4,3)-(4,2)-(3,2)-(2,2)-(2,1)-(1,1)-ieşire Rezolvare. După metoda backtracking, trebuiesc găsite toate posibilităţile de a ieşi din labirint. S-a ieşit din labirint când linia este 0, coloana este 0, linia este m+1 sau când coloana este n+1. Trebuie să trecem din cameră în cameră, să verificăm toate posibilităţile de ieşire. Când trecem dintr-o cameră în alta, reţinem în matricea triplă, direcţia, linia şi coloana respectivă. Va trebui să respectăm regulile preoblemei, adică să nu trecem de două ori prin aceeaşi cameră. Această regulă a fost impusă deoarece dacă am rezolva problema fără ea, atunci ne-am învârti în gol ! Această verificare se face comparând coordonatele camerei în care suntem cu coordonatele camerelor prin care am trecut, cele reţinute de matricea triplă pe coloanele 2 şi 3. Pentru a verifica dacă între două camere exisă sau nu un perete, va trebui să respectăm un lucru: dacă o cameră are perete în sus, atunci obligatoriu şi camera de sus trebuie să aibă perete jos, iar dacă o cameră nu are perete sus, atunci nici camera de sus nu trebuie să aibă perete jos. Aceasta deoarece dacă ar fi aşa, am trece dintr-o cameră în alta, dar invers nu, ceea ce este imposibil. Imaginaţi-vă că sunteţi într-o cameră. Vreţi să ieşiţi în hol. Din cameră se vede holul şi uşa, dar după ce ieşiţi în hol şi vreţi să reveniţi în cameră, vă întoarce-ţi şi constataţi că în spatele vostru nu există nici o uşă pentru a intra înapoi în cameră, în locul ei fiind doar un perete. Astfel vom verifica după relaţiile: a[st[k,2],st[k,3]] and 8 = 0 - nu putem merge în sus a[st[k,2],st[k,3]] and 4 = 0 - nu putem merge la dreapta a[st[k,2],st[k,3]] and 2 = 0 - nu putem merge în jos a[st[k,2],st[k,3]] and 1 = 0 - nu putem merge la stânga a – matricea labirintului st – stiva triplă Operatorul logic AND verifică biţii corepunzători ai 2 numere întregi, returnând 1 dacă ambii sunt 1 şi 0 în rest. Acesta este rezultatul final. 8 înseamnă 1000, adică dacă camera respectivă are perete sus, rezultatul va fi tot 8, dacă nu, va fi 0. Când mergem prin labirint, înaintâm în camera respectivă iar apoi verificăm dacă între cele două camere există sau nu perete pentru a putea trece pe acolo. Apoi verificăm să nu fi ieşit din labirint ( l1<1 or l1>m or c1<1 or c1>n ) şi dacă prin această cameră am mai trecut odată. Afişare. Când am găsit o soluţie, afişăm pe rând toate liniile din matricea triplă, dar fără coloana 1, ci numai coloanele 2 şi 3. În continuare, programul care rezolvă problema labirintului. Program labirint; type stiva=array[1..100,1..3] of integer; var st:stiva; m,n,k,i,j,l,c,l1,c1:integer; as,ev:boolean; a:array[1..100,1..100] of integer; procedure init(var st:stiva;k:integer); begin st[k,1]:=0; if k=1 then begin st[k,2]:=l;st[k,3]:=c; end else begin st[k,2]:=l1;st[k,3]:=c1; end; end; procedure succesor(var as:boolean;var st:stiva;k:integer); begin if st[k,1]<4 then begin st[k,1]:=st[k,1]+1; as:=true; end else as:=false; end; procedure valid(var ev:boolean;st:stiva;k:integer); begin l1:=st[k,2];c1:=st[k,3]; case st[k,1] of 1: l1:=l1-1; 2: c1:=c1+1; 3: l1:=l1+1; 4: c1:=c1-1; end; ev:=true; case st[k,1] of 1: if a[st[k,2],st[k,3]] and 8<>0 then ev:=false; 2: if a[st[k,2],st[k,3]] and 4<>0 then ev:=false; 3: if a[st[k,2],st[k,3]] and 2<>0 then ev:=false; 4: if a[st[k,2],st[k,3]] and 1<>0 then ev:=false; end; for i:=1 to k-1 do if (l1=st[i,2]) and (c1=st[i,3]) then ev:=false; end; function solutie(k:integer):boolean; begin solutie:=(l1<1) or (l1>m) or (c1<1) or (c1>n); end; procedure tipar; for i:=1 to k do write(st[i,2],‘ ‘,st[i,3],‘ ‘); writeln; end; begin write( m,n: );readln(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); write( l,c: );readln(l,c); k:=1;init(st,k); 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+1; init(st,k); end else k:=k-1; end; end. 쥁@