Metoda Backtracking

Previzualizare atestat:

Extras din atestat:

Prezenta aplicatie se doreste a fi un instrument pentru predarea si aprofundarea notiunilor de backtracking. Deoarece metoda backtracking este in sine o metoda relativ dificila, pe care elevii si-o insusesc dupa multe ore de exersare, am considerat util a realiza o aplicatie care sa vina in sprijinul tuturor celor ce doresc sa invete aceasta metoda. Elementul de noutate consta in faptul ca toate problemele rezolvate au si o interpretarea grafica, interpretare care face ca metoda sa fie inteleasa mai usor. Asadar a fost nevoie nu numai de metoda backtracking in sine ci si de cunostinte de grafica pe calculator, cunostinte ce nu mai fac obiectul materiei de studii al anilor de liceu. Desigur aplicatia de fata poate fi imbunatatita si cu alte probleme la care se poate da o interpretare grafica. Aplicatia este realizata modularizat, cate un program pentru fiecare dintre aplicatiile prezentate in atestat si un program principal care centralizeaza toate subprogramele. S-a utilizat metoda backtracking iterativa, mai precis metoda predata in manualul de Tehnici de Programare a lui Tudor Sorin si asta numai din considerente de standardizare, desi fara probleme se putea folosi si metoda recursiva. In documentatia aferenta programului s-au explicat atat metoda iterativa cat si cea recursiva precum si notiuni legate de grafica pe calculator si desenarea obiectelor grafice. In finalul documentatie sunt atasate toate sursele programului, ca model pentru cei ce doresc sa preia o parte dintre codurile aplicatiei.

Sper ca acest atestat sa fie un bun instrument si exemplu pentru cei ce invata metoda backtracking sau pentru realizarea unei aplicatii ce utilizeaza meniuri, subprograme si grafica computerizata.

2.Metoda backtracking - prezentare teoretica

2.1. Metoda backtracking iterativa

Aceasta metoda se foloseste in rezolvarea problemelor ce indeplinesc simultan urmatoarele conditii:

- Solutia lor poate fi pusa sub forma de vector S=x1,x2, ,xN, cu x1 apartinand multimii A1, x2 apartinand multimii A2, , xN apartinand multimii An;

- Multimile A1,A2, ,An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

- Nu se dispune de o solutie mai rapida.

Observatii:

- nu la toate problemele n este cunoscut de la inceput;

- x1, x2, ,xN pot fi la randul lor vectori;

- in multe probleme, multimile A1, A2, , An coincid.

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta metoda, suntem tentati sa generam toate elementele produsului cartezian A1- A2- - An si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de calcul este atat de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

Algoritmul backtracking consta in urmatoarele:

- se alege primul element, x1, ce apartine lui A1;

- presupunand generate elementele x1, x2, , xK, apartinanad multimilor A1, A2, ,Ak, se alege, daca exista, xK+1, primul element disponibil din multimea Ak+1 care indeplineste anumite conditii de continuare, aparand astfel doua posibilitati:

a) elementul exista, se testeaza daca nu s-a ajuns la o solutie, in caz afirmativ aceasta se tipareste, in caz contrar se considera generate x1, x2, , xK, xK+1;

b) elementul nu exista, situatie in care se considera generate elementele x1, x2, ,xK-1, reluandu-se cautarea de la elementul urmator lui xK in multimea Ak;

- algoritmul se incheie cand au fost luate in consideratie toate elementele multimii A1.

Implementarea acestei metode se poate face utilizand structura de stiva.

Astfel, elementele x1, x2, , xK ni le imaginam intr-o stiva ST: gasirea elementului xK+1 determina urcarea in stiva pe nivelul k+1, in caz contrar se coboara la nivelul k-1. In situatia ajungerii la nivelul 0 algoritmul se termina.

Facem urmatoarele conventii:

- la urcarea in stiva, pe nivelul la care am ajuns, se pune o valoare care nu se afla in multimea considerata, dar de la care, la pasul urmator, se ajunge la primul element din acea multime (procedura INIT);

- pe un anumit nivel gasirea elementului urmator celui considerat se face cu ajutorul procedurii SUCCESOR;

- verificarea faptului ca aceasta indeplineste conditiile de continuare a algoritmului este facuta de procerura VALID;

- testarea, daca s-a ajuns la solutie, este facuta de functia SOLUTIE;

- tiparirea solutiei este realizata de procedura TIPAR.

Aceste proceduri sunt variabile de la aplicatie la aplicatie, insa, indiferent de aplicatie, exista o parte fixa si anume parte care implementeaza strategia generala backtracking:

k:=1;

init(1,st);

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 then tipar else begin k:=k+1; init (k, st); end else k:=k=1;

end;

In secventa considerata as si ev sunt doua variabile booleene avand semnificatia "exista succesor", respectiv "este valid".

Observatie: problemele rezolvate prin aceasta metoda necesita un timp indelungat. Din acest motiv, este bine sa utilizam metoda cand nu avem la dispozitie un alt algoritm.

2.2. Metoda backtracking recursiva

Procedurile si functiile folosite sunt in general aceleasi, existand doua mici exceptii:

- SUCCESOR nu mai este procedura, ci devine functie booleana (dispare variabila AS);

- Rutina backtracking devine ea in sine o procedura care se apeleaza prin BACK(1)

Principiul de functionare al procedurii BACK corespunzator unui anumit nivel k este urmatorul:

- In situatia cand avem o solutie o tiparim si revenim pe nivelul anterior;

- In caz contrar se initializeaza nivelul si se cauta un succesor;

- Daca am gasit unul, se verifica daca este valid, afirmativ procedura se autoapeleaza pentru k+1, in caz contrar urmand a se continua cautarea succesorului;

- Daca nu avem succesor, se trece pe un nivel inferior(k-1) prin iesirea din procedura BACK.

Vom explica in continuare utilizarea backtrackingului recursiv prin generarea permutarilor, insa recomandam cititorului sa rezolve prin aceasta rutina si cateva din problemele prezentate in capitolul 2.

Program permutari;

Type stiva= array [1 9] of integer;

Var st : stiva;

Ev : boolean;

N,k : integer;

Procedure init (k:integer; var st:stiva);

Begin

St[k]:=0;

End;

Bibliografie:

1.Tudor Sorin - Tehnici de programare, Editura Teora, 1995, Bucuresti

2. Grigore Albeanu - Programarea in Turbo Pascal - Culegere de probleme. Editura Tehnica, 1994

3.Andrei Cioroianu - Programe Turbo Pascal in detaliu. Editura Teora, 1997

4.George Daniel Mateescu - Teste si variante de subiecte pentru BACALAUREAT - Ed. Donaris, 2002

Download atestat

Primești atestatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc, htm, exe, pas, pif, bgi, dsk, tp, 000
Diacritice:
Nu
Nota:
9/10 (1 voturi)
Nr fișiere:
23 fisiere
Pagini (total):
28 pagini
Imagini extrase:
28 imagini
Nr cuvinte:
4 893 cuvinte
Nr caractere:
26 234 caractere
Marime:
209.84 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Atestat
Materie:
Informatica
Data publicare:
16.08.2017
Structură de fișiere:
  • atestat.doc
  • ATESTAT.EXE
  • ATESTAT.PAS
  • ATESTAT.PIF
  • CAL.EXE
  • CAL.PAS
  • CAL.PIF
  • DAME.EXE
  • DAME.PAS
  • DAME.PIF
  • EGAVGA.BGI
  • FRACTAL.EXE
  • FRACTAL.PAS
  • HARTA.EXE
  • HARTA.PAS
  • TURBO.DSK
  • TURBO.TP
  • TURE.EXE
  • TURE.PAS
  • VOIAJOR.EXE
  • VOIAJOR.PAS
  • Atestat2003.htm
  • DRVSPACE.000
Predat:
la liceu
Profil:
Real
Profesorului:
Vancea Ioan

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Academia Franceza definea informatica: Stiinta tratarii rationale prin masini automate a...
Prezentarea tehnicii Backtracking Aceasta tehnica se foloseste in rezolvarea problemelor care...
Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile...
Deseori in practica trebuie sa rezolvam probleme care au un numar foarte mare de solutii...
Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele...
Sus!