Metoda Backtracking

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 teoretică

2.1. Metoda backtracking iterativă

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 recursivă

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;

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