| Referate | Online |
 | Gimnaziu | |
| Liceu | ||
| Facultate |
Referat Metoda Backtracking
În mod practic la scoaterea unei variabile din stivă, scade cu 1 valoarea variabilei ce indică vârful stivei, iar atunci când scriem ceva în stivă, o eventuală valoare reziduală se pierde:
Pe un anumit nivel se retine, de regulă, o singură informaţie (literă sau cifră), însă este posibil; aşa cum va rezulta din exemplele, prezentate în lucrare, să avem mai multe informaţii, caz în care avem de a face cu stive duble, triple, etc. Întreaga teorie a recursivităţii se bazează pe structura de tip stivă.
Pe un anumit nivel se retine, de regulă, o singură informaţie (literă sau cifră), însă este posibil; aşa cum va rezulta din exemplele, prezentate în lucrare, să avem mai multe informaţii, caz în care avem de a face cu stive duble, triple, etc. Întreaga teorie a recursivităţii se bazează pe structura de tip stivă.
| Nota : 8 | Nivel : Liceu |
 | |
| Categorie : Informatica | |
| Downloads : 8 | |
| Dimensiune : 102 kb | |
| Tip : Gratuit | |
| Pagini : 7 | |
Extras din referat
- se alege primul element x, ce aparţine lui A;
- presupunând generate elementele x1,x2 …,xk , aparţinând mulţimilor A1,
A2 …,Ak , se alege (dacă există) xk+1 , primul element disponibil din mulţimea Ak+1 , apar două posibilităţi :
1) Nu s-a găsit un astfel de element, caz în care caz în care se reia căutarea considerând generate elementele x1,x2 …,xk+1 , iar aceasta se reia de la următorul element al mulţimii Ak rămas netestat;
2) A fost găsit, caz în care se testează dacă acesta îndeplineşte anumite condiţii de continuare apărând astfel două posibilităţi:
- îndeplineşte, caz în care se testează dacă s-a ajuns la soluţie si apar din nou două posibilităţi
- s-a ajuns la soluţie, se tipăreşte soluţia si se reia algoritmul considerând generate elementele x1,x2 …,xk , (se caută în continuare, un alt element al mulţimii Ak , rămas netestat);
- nu s-a ajuns la soluţie, caz în care se reia algoritmul considerând generate elementele x1,x2 …,xk , si se caută un prim element xk+2 € Ak.
- nu le îndeplineşte caz în care se reia algoritmul considerând generate elementele x1,x2 …,xk , iar elementul xk-1 se caută între elementele mulţimii A, rămase netestate.
Algoritmii se termină atunci când nu există nici un element x1 € A1 netestat.
Observaţie: tehnica Backtracking are ca rezultat obţinerea tuturor soluţiilor problemei. În cazul în care se cere o sigură soluţie se poate forţa oprirea, atunci când a fost găsită.
Am arătat că orice soluţie se generează sub formă de vector. Vom considera că generarea soluţiilor se face intr-o stivă. Astfel, x1 € A1, se va găsi pe primul nivel al stivei, x2 € A2 se va găsi pe al doilea nivel al stivei,... xk € Ak se va găsi pe nivelul k al stivei. În acest fel, stiva (notată ST) va arăta astfel:
Nivelul k+1 al stivei trebuie iniţializat (pentru a alege, în ordine, elementele mulţimii k+1 ). Iniţializarea trebuie făcută cu o valoare aflată (în relaţia de ordine considerată, pentru mulţimea Ak+1 ) înaintea tuturor valorilor posibile din mulţime. De exemplu, pentru generarea permutărilor mulţimii {1,2.....n}, orice nivel al stivei va lua valori de la 1 la n. Iniţializarea unui nivel (oarecare) se face cu valoarea 0. Procedura de iniţializare o vom numi INIT şi va avea doi parametri: k (nivelul care trebuie iniţializat si ST (stiva)).
Găsirea următorului element al mulţimii Ak (element care a fost netestat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) este o variabilă booleană. În situaţia în care am găsit elementul, acesta este pus în stivă şi AS ia valoarea TRUE, contrar (nu a rămas un element netestat) AS ia valoarea FALSE..
- presupunând generate elementele x1,x2 …,xk , aparţinând mulţimilor A1,
A2 …,Ak , se alege (dacă există) xk+1 , primul element disponibil din mulţimea Ak+1 , apar două posibilităţi :
1) Nu s-a găsit un astfel de element, caz în care caz în care se reia căutarea considerând generate elementele x1,x2 …,xk+1 , iar aceasta se reia de la următorul element al mulţimii Ak rămas netestat;
2) A fost găsit, caz în care se testează dacă acesta îndeplineşte anumite condiţii de continuare apărând astfel două posibilităţi:
- îndeplineşte, caz în care se testează dacă s-a ajuns la soluţie si apar din nou două posibilităţi
- s-a ajuns la soluţie, se tipăreşte soluţia si se reia algoritmul considerând generate elementele x1,x2 …,xk , (se caută în continuare, un alt element al mulţimii Ak , rămas netestat);
- nu s-a ajuns la soluţie, caz în care se reia algoritmul considerând generate elementele x1,x2 …,xk , si se caută un prim element xk+2 € Ak.
- nu le îndeplineşte caz în care se reia algoritmul considerând generate elementele x1,x2 …,xk , iar elementul xk-1 se caută între elementele mulţimii A, rămase netestate.
Algoritmii se termină atunci când nu există nici un element x1 € A1 netestat.
Observaţie: tehnica Backtracking are ca rezultat obţinerea tuturor soluţiilor problemei. În cazul în care se cere o sigură soluţie se poate forţa oprirea, atunci când a fost găsită.
Am arătat că orice soluţie se generează sub formă de vector. Vom considera că generarea soluţiilor se face intr-o stivă. Astfel, x1 € A1, se va găsi pe primul nivel al stivei, x2 € A2 se va găsi pe al doilea nivel al stivei,... xk € Ak se va găsi pe nivelul k al stivei. În acest fel, stiva (notată ST) va arăta astfel:
Nivelul k+1 al stivei trebuie iniţializat (pentru a alege, în ordine, elementele mulţimii k+1 ). Iniţializarea trebuie făcută cu o valoare aflată (în relaţia de ordine considerată, pentru mulţimea Ak+1 ) înaintea tuturor valorilor posibile din mulţime. De exemplu, pentru generarea permutărilor mulţimii {1,2.....n}, orice nivel al stivei va lua valori de la 1 la n. Iniţializarea unui nivel (oarecare) se face cu valoarea 0. Procedura de iniţializare o vom numi INIT şi va avea doi parametri: k (nivelul care trebuie iniţializat si ST (stiva)).
Găsirea următorului element al mulţimii Ak (element care a fost netestat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) este o variabilă booleană. În situaţia în care am găsit elementul, acesta este pus în stivă şi AS ia valoarea TRUE, contrar (nu a rămas un element netestat) AS ia valoarea FALSE..
Nota: Textul de mai sus reprezinta un extras din referatul Metoda Backtracking. Pentru a intra in posesia referatului apasa butonul Download si descarca fisierul. Daca doresti sa intri in contact cu noi foloseste sectiunea Contact. Ia cunostinta de Termenii si conditiile site-ului.
TOATE referatele de pe Referate-Online.org sunt adaugate de catre utilizatori. Echipa Referate-Online.org nu va fi trasa la raspundere pentru aceste referate. In cazul in care vreun autor al vreunui referat este deranjat de aparitia acestuia pe site-ul Referate-Online.org, acesta este rugat sa ne trimita un e-mail pe adresa referateonline2012@yahoo.com si referatul va fi sters de pe site.
