7/26/2019 Back Tra King

1/1

Backtrackingeste numele unui algoritmgeneral de descoperire a tuturor soluiilor unei probleme decalcul, algoritm ce se bazeaz pe construirea incremental de soluii-candidat, abandonnd fiecare candidatparial imediat ce devine clar c acesta nu are anse s devin o soluie valid.Exemplul de baz folosit n numeroase manuale de liceu i de nivel universitar esteproblema reginelor, carecere s se gseasc toate modurile n care pot fi aezate pe o tabl de ah opt regine astfel nct s nu seatace. n abordarea bac!trac!ing, candidatele pariale sunt aran"amente de cte kregine pe primele krnduriale tablei, toate pe rnduri i coloane diferite. #rice soluie parial ce conine dou regine care se atacpoate fi abandonat, deoarece n mod clar restul de regine nu pot fi aezate ntr-o soluie valid.$ehnica bac!trac!ing se poate aplica doar pentru probleme ce admit conceptul de %candidat parial desoluie& i ofer un test relativ rapid asupra posibilitii ca un astfel de candidat s fie completat ctre osoluie valid. 'nd se poate aplica, ns, bac!trac!ingul este adesea mult mai rapid dect cutarea prinmetoda forei brute prin toi candidaii, ntruct este capabil s elimine dintr-un singur test un mare numrde candidai.Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:

solutia lor poate fi pusa sub forma unui vector ()x*,x+,xxncux**,x++,.....,xnn/ multimile *,+,nsunt multimi finite ,iar elementele lor se considera ca se afla intr-o relatie de

ordine bine stabilita

nu se dispune de o alta metoda de rezolvare ,mai rapida.

$ehnica 0ac!trac!ing are la baza un principiu extrem de simplu1 se construieste solutia pas cu pas1x*x+xxn/ daca se constata ca,pentru o valoare aleasa,nu avem cum sa a"ungem la solutie ,se renunta la acea

valoare si se reia cautarea din punctul in care am ramas

2entru usurarea intelegerii metodei,vom prezenta o rutina unica aplicabila oricarei probleme,rutinacare utilizeaza notiunea de stiva.3utina va apela proceduri si functii care au totdeauna acelasi nume siparametri si care din punct de vedere al metodei realizeaza acelasi lucru.(arcina rezolvitorului este de ascrie explicit pentru fiecare problema in parte procedurile si functiile apelate de 0ac!tra!ing.Evident,o

astfel de abordare conduce la programe lungi.4imeni nu ne opreste,ca dupa intelegerea metodei sa scriemprograme scurte specifice fiecarei probleme in parte5de exemplu scurtam substantial textul doar dacarenuntam la utilizarea procedurilor si functiilor62rezentam in continuare rutina 0ac!trac!ing1 !1)*/init5*,st6/

7hile !89 dobegin

repeatsuccesor5as,st,!6/

if as then valid5ev,st,!6/until 5not as6 or 5as and ev 6/

if as thenif solutie5!6 then

tiparelse

begin!1)!:*/init5!,st6/end

else!1)!-*/

end/

http://ro.wikipedia.org/wiki/Algoritmhttp://ro.wikipedia.org/wiki/Algoritmhttp://ro.wikipedia.org/w/index.php?title=Problema_reginelor&action=edit&redlink=1http://ro.wikipedia.org/wiki/Algoritmhttp://ro.wikipedia.org/w/index.php?title=Problema_reginelor&action=edit&redlink=1