Acasa | Trimite referat | Cere referat | Contact

Referat METODA BACKTRACKING



METODA BACKTRACKING

Categorie: Referate Informatica

Referat downloadat de: 259 ori.


Cauta referat dupa: metoda backtracking


Descriere referat:
Stiva este acea form? de organizare a datelor (structur? de date) cu proprietatea c? opera?iile de introducere ?i scoatere a datelor se fac în vârful ei.¬ Stivele se pot simula utilizând vectori. Fie ST(i) un vector. ST(1), ST(2), ..., ST(n) pot re?ine numai litere sau numai cifre. O variabil? K indic? în permanent? vârful stivei. Exemplific?m, în continuare, modul de lucru cu stiva: În stiva ini?ial vid? se introduce litera A, vârful stivei va fi la nivelul 1 (k-1); introducem în stiv? litera B, deci k va lua valoarea 2; scoatem din stiv? pe B (A nu poate fi scos); scoatem din stiv? pe A; stiva r?mâne vid? Î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?. Prezentarea tehnicii Backtracking Aceast? tehnic? se folose?te în rezolvarea problemelor care îndeplinesc simultan urm?toarele condi?ii: - solu?ia lor poate fi pus? sub forma unui vector S=x1,x2, ...,xn, cu x1 € A1, x2 € A2 …,xn € An - mul?imile A1, A2 , …., An sunt mul?imi finite, iar elementele lor se consider? c? se afl? într-o rela?ie de ordine bine stabilit?; - nu se dispune de o alt? metod? de rezolvare, mai rapid? - x1 x2 …, xn pot fi la rândul lor vectori; - A1, A2 …, An pot coincide. La întâlnirea unei astfel de probleme, dac? nu cunoa?tem aceast? tehnic?, suntem tenta?i s? gener?m toate elementele produsului cartezian A1,A2 …,An si fiecare element s? fie testat dac? este solu?ie. Rezolvând problema în acest mod, timpul de execu?ie este atât de mare, încât poate fi considerat infinit, algoritmul neavând nici o valoare practic?. De exemplu, dac? dorim s? gener?m toate permut?rile unei mul?imi finite A, nu are rost s? gener?m produsul cartezian AxAx.....xA, pentru ca apoi, s? test?m, pentru fiecare element al acestuia, dac? este sau nu permutare (nu are rost s? gener?m 1.1,1.......1, pentru ca apoi s? constat?m c? nu am ob?inut o permutare, când de la a doua cifr? 1 ne puteam da seama c? cifrele nu sunt distincte). Tehnica Backtracking are la baz? un principiu extrem de simplu: - se construie?te solu?ia pas cu pas: x1, x2 …,xn - dac? se constat? c?, pentru o valoare aleas?, nu avem cum s? ajungem la solu?ie, se renun?? la acea valoare ?i se reia c?utarea din punctul în care am r?mas. Concret: - 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: ST 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.. Odat? ales un element, trebuie v?zut dac? acesta îndepline?te condi?iile de continuare (altfel spus, dac? elementul este valid). Acest test se face cu ajutorul procedurii VALID (EV,ST,K). Testul dac? s-a ajuns sau nu la solu?ia final? se face cu ajutorul func?iei SOLUTIE(k) iar o solu?ie se tip?re?te cu ajutorul procedurii TIPAR. Prezent?m în continuare rutina Backtracking: k:=1; init(1,st); while k>0 do begin repeat succesor (as, st, k) ; . if as then valid(ev,st,k)

Alte referate din materia: Informatica

Nr. Nume referat Hits
1 TkkvMlabSupl 10
2 qzpymq@dxuzju.com 111
3 email@gmail.com 224
4 pfuqxd@exjswl.com 249
5 ncqcez@hdtnnq.com 218
6 Hard 677
7 ISTORIA INTERNET-ULUI 744
8 Impera 423
9 Info Doc 479
10 Info-TIRON 432
11 Informatica - Grafica pentru web 890
12 Informatica - Introducere in HTML 660
13 Initiere in pc 657
14 Instalarea sistemului de operare Windows 551
15 Internetul ca sursa de comunicare 534
16 Istoria Internetului 568
17 Istoria calculatorului 490
18 Istoria metodelor de proiectare 326
19 Java visavis de C++ 364
20 Java vizavi de C 299
21 LIMBAJUL DE PROGRAMARE PASCAL - Programul defineste tipul salariat, o inregistrare cu variante, valorile citite fiind salvate in fisierul salariat.dat 0
22 Limbajul C 373
23 Lista vinuri prg 284
24 Lotus software 260
25 Lumea internetului 367
Trimite un referat !
Referatul tau ii poate ajuta si pe ceilalti! Ajuta-ti colegii!

Ai un referat facut de tine si consideri ca este bun si original ? Trimite-ti lucrarea ta si poti castiga premii, ajutandu-ti colegii sa ia note bune!

Trimite un referat!
Cere un
referat !
Ai nevoie de un referat bun si nu il gasesti ?

Noi te ajutam sa iti faci referatul de care ai nevoie. Da-ne detalii despre lucrarea pe care trebuie sa o redactezi si noi vom scotoci pentru tine!

Cere un referat!
Acasa Trimite referat Cere referat Adauga la favorite Seteaza ca homepage Contact libertateailuziei Trailere Filme Filme Noi Jocuri Online Jocuri Barbie Jocuri pentru Copii GameBox.ro Make Money Bucuresti regim hotelier
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea top-referat.ro si nu pot fi preluate fara acord scris. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate.