.............................177Rezolvarea problemei198Biografie..23Capitolul 1PREZENTAREA TEHNICII BACKTRAKINGAceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditiisolutia lor poate fi pusa sub forma unui vector Sx1,x2,x3xn cu x1A1,x2A2,.....,xnAn multimile A1,A2,A3An sunt multimi finite ,iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilitanu se dispune de o alta metoda de rezolvare ,mai rapida.Observatiinu pentru toate problemele n este cunoscut de la inceputx1,x2,x3xn pot fi la randul lor vectoriin multe probleme multimile A1,A2,A3An coincidLa intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica,suntem tentati sa generam toate elementele produsului cartezian A1A2A3An si fiecare element sa fie testat daca este solutie.Rezolvand problema in acest mod,timpul de executie este atat de mare ,incat poate fi considerat infinit,neavand nici o valoare practica.De exemplu,daca dorim sa generam toate permutarile unei multimi finite A,nu are rost sa generam produsul cartezian A1A2A3An pentru ca apoi,sa testam,pentru fiecare element al acestuia,daca este sau nu permutare .Tehnica Backtracking are la baza un principiu extrem de simpluse construieste solutia pas cu pasx1x2x3xndaca se constata ca,pentru o valoare aleasa,nu avem cum sa ajungem la solutie ,se renunta la acea valoare si se reia cautarea din punctul in care am ramasConcretse alege primul element x1 ce apartine lui A1presupunand generate elementele x1,x2,x3xk apartinand multimilor A1 A 2A3Ak1 se alegedaca exista x,primul element disponibil din multimea Ak1,apar astfel 2 posibilitatinu s-a gasit un astfel de element,caz in care se reia cautarea considerand generate elementele x1,x2,x3xk1 iar aceasta se reia de la urmatorul element al multimii Ak ramas netestata fost gasit,caz in care se testeaza daca acesta indeplineste anumite coditii de continuare ,aparand astfel alte doua posibilitati2.1 le indeplineste,caz in care se testeaza daca s-a ajuns la solutie si apar din nou doua posibilitati2.1.1 s-a ajuns la solutie ,se tipareste solutia si se reia algoritmul considerand generate elementele x1,x2,xkse cauta in continuare un alt element al multimii Ak1 ramas netestat2.1.2 nu s-a ajuns la solutie ,caz in care se reia algoritmul considerand generate elementele x1,x2,x3xk1 si se cauta un prim element xk2 Ak22.2 nu le indeplineste caz in care se reia algoritmul considerand generate elementele x1x2 x3xk iar elementul xk1 se cauta intre elementele multimii Ak1 ramase netestate.Algoritmul se termina atunci cand nu mai exista nici un element x1A1 netestat.Observatie tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei.In cazul in care se cere o singura solutie se poate forta oprirea atunci cand a fost gasita.Pentru usurarea intelegerii metodei,vom prezenta o rutina unica aplicabila oricarei probleme,rutina care utilizeaza notiunea de stiva.Rutina va apela proceduri si functii care au totdeauna acelasi nume si parametri si care din punct de vedere al metodei realizeaza acelasi lucru.Sarcina rezolvitorului este de a scrie explicit pentru fiecare problema in parte procedurile si functiile apelate de Backtraking.Evident,o astfel de abordare conduce la programe lungi.Nimeni nu ne opreste,ca dupa intelegerea metodei sa scriem programe scurte specifice fiecarei probleme in partede exemplu scurtam substantial textul doar daca renuntam la utilizarea procedurilor si functiilorPrezentam in continuare rutina Backtrackingk1init1,sthile k0 do beginrepeat succesoras,st,k if as then validev,st,kuntil not as or as and ev if as then if solutiek then tiparelse beginkk1initk,stendelsekk-1 endObservatieProblemele rezolvate prin aceasta metoda necesita un timp indelungat.Din acest motiv,este bine sa utilizam metoda numai atunci cand nu avem la dispozitie un alt algoritm mai eficient.Cu toate ca exista probleme pentru care nu se pot elabora alti algoritmi mai eficienti,tehnica Backtracking trebuie aplicata numai in ultima instanta.CAPITOLUL 2NOTIUNI DESPRE RECURSIVITATERecursivitatea este una din notiunile fundamentale ale informaticii.Utilizarea frecventa a recursivitatii s-a facut dupa anii 80.Multe din limbajele de programare evoluate si mult utilizateFortran ,Cobol nu permiteau scrierea programelor recursive.In linii mari,recursivitatea este un mecanism general de elaborare a programelor .Ea a aparut din necesitati practice transcrierea directa a formulelor matematice recursive si reprezinta acel mecanism prin care un subprogramprocedura,functie se autoapeleaza.Daca lucrurile par usor de inteles in cazul functiilor,nu tot atat de simplu este sa aplicam recursivitatea utilizand proceduri.Astfel vom vedea ca putem genera recursiv probleme de genul permutarilor.Un algoritm recursiv are la baza un mecanism de gandire diferit de cel cu care ne-am obisnuit deja.Atunci cand scriem un algoritm recursiv este suficient sa gandim ce se intampla la un anumit nivel pentru ca la orice nivel se intampla exact acelasi lucru.Un algoritm recursiv corect trebuie sa se termine ,contrar programul se va termina cu eroare si nu vom primi rezultatul asteptat.Conditia de terminare va fi pusa de programator.Un rezultat matematic de exceptie afirma ca pentru orice algoritm iterativ exista si unul recursiv echivalentrezolva aceeasi problema si invers,pentru orice algoritm recursiv exista si unul iterativ echivalent.In continuare, raspundem la intrebareacare este mecanismul intern al limbajului care permite ca un algoritm recursiv sa poata fi implementatPentru a putea implementa recursivitatea ,se foloseste structura de date numita stiva.Mecanismul unui astfel de program poate fi generalizat cu usurinta pentru obtinerea recursivitatii.Atunci cand o procedura sau o functie se autoapeleaza se depun in stivavalorile parametrilor transmisi prin valoareadresele parametrilor transmisi prin referintavalorile tuturor variabilelor localedeclarate la nivelul procedurii sau functieiDin punct de vedere al modului in care se realizeaza autoapelul ,exista doua tipuri de recursivitatedirect si indirecta.Recursivitatea directa a fost deja prezentata.Recursivitatea indirecta are loc atunci cand o procedura functie apeleaza o alta procedurafunctie,care la randul ei o apeleaza pe ea.Un astfel de exemplu ar fi urmatorulSe considera doua valori reale,pozitive a0,b0 si n un numar natural.Definim sirul anan-1bn-12 bnan-1bn-1Vom folosi doua functii an si bn.Fiecare dintre ele se autoapeleaza dar o apeleaza si pe cealalalta.CAPITOLUL 3Backtracking recursivIn capitolul 1 am prezentat rutina de backtracking clasica,nerecursiva.In acest capitol prezentam rutina de backtracking recursiva.Procedurile si functiile folosite sunt in general aceleasi,cu doua mici exceptiiSUCCESOR nu mai este procedura ci functie booleana rutina backtracking se transforma in procedura,care se apeleaza prin BACK1Principiul de functionare al proce...
Download