Problemă labirint - Turbo Pascal

1 Metoda backtracking

Stiva este acea forma de organizare a datelor (structura de date ) cu proprietatea ca operatiile de introducere si scoatere a datelor se fac în vârful ei.

Pentru a intelege modul de lucru cu stiva ,ne imaginam un numar n de farfurii identice ,asezate una peste alta (o ‘stiva de farfurii’). Adaugarea sau scoaterea unei farfurii se face , cu usurinta ,numai în vârful stivei .Daca toate cele n farfurii sunt asezate una peste alta ,spunem ca stiva este plina .Dupa ce am scos toate farfuriile di n stiva ,spunem ca aceasta este vida .Oricât ar parea de simplu principiul stivei ,el are consecinte uriase în programare.

Stivei se pot simula utilizand vectori.

Fie ST(i) un vector .ST(1),ST(2),……ST(n) pot retine numai litere sau numai cifre .O variabila K indica în permanenta vârful stivei.

Observatii:

- În mod practice ,la scoaterea unei variabile din stiva ,scade cu 1 valoarea variabilei ce indica varful stivei ,iar atunci când scriem ceva în stiva ,o eventuala valoare reziduala se pierde;

- Stivele pot fi simulate si altfel decât cu vectori ,însa despre aceasta vom vorbi în capitolul Structuri de date ;

- Pe un anumit nivel se retine ,de regula o singura informatie (litera sau cifra) ,însa este posibil ,asa cum va rezulta din exemplele prezentate în lucrare ,sa avem mai multe informatii ,caz în care avem de a face cu stive duble ,triple , etc;

- Întreaga teorie a recursivitatii se bazeaza pe structura de tip stiva.

1.1 Prezentarea tehnicii Backtracking

Aceasta tehnica se foloseste în rezolvarea problemelor care îndeplinesc simultan urmatoarele conditii:

- Solutia lor poate pusa sub forma unui vector S=X1 +X2 ,…..,Xn ,cu X1€ A1 . X2 € A2,……., . Xn € An ;

- Multimile A1 , A2 ,…. An sunt multimile finite ,iar elementele lor se considera ca se afla într-o relatie de ordine bine stabilita;

- Nu se dispune de o afla metoda de rezolvare ,ami rapida

Obesrvatii :

- Nu pentru toate probleme n este cunoscut de la început ;

- X1, X,…. Xn pot fi la randul lor vectori ;

- Nu se dispune probleme ,multimile A1 , A2 ,…. An coincid.

La întâlnirea unei astfel de probleme ,daca nu cunoastem aceasta tehnica ,suntem tentati sa generam toate elementele produsului cartezian A1 x,A2x….xAn si fiecare element sa fie testat daca este solutie .Rezolvând problema în acest mod , timpul de executie este atât de mare , incât poate fi considerat infinit ,algoritmul neavând nici o valoare practica.

De exemplu ,daca dorim sa generam toate permutarile unei multimi finite A ,nu are rost sa generam produsul cartezian A1 x,A2x….xAn pentru ca apoi ,sa testam ,pentru fiecare element al acestuia ,daca este sau nu permutare (nu are rost sa generam 1,1,1, …..1, pentru ca apoi sa constatam ca nu am obtinut o permutare , când de la a doua cifra 1 ne puteam da seama ca cifrele nu sunt distincte ).

Tehnica Backtracking are la baza un principui extrem de simplu:

- Se construieste solutia pas cu pas : X1, X,…. Xn ;

- daca se constata ca , pentru o valoare aleasa ,nu avem cum sa ajungem la solutie ,se renunta la acea valoare si se reia cautarea din punctual în care am ramas .

Concret :

- se alege element X1 ,ce apartine lui A1 ;

- presupunând generate elentele X1, X,…. Xk apartinând multimilor A1 , A2 ,…. Ak se alege (daca exista )xk-1 ,primul element disonibil din multimea Ak-1 ,apar doua posibilitati :

1. nu s-a gasit un astfel de element ,caz în care caz în care se reia cautarea considerând generate elementele X1, X,…. Xk+1 ,iar aceasta se reia de la urmatorul element al multimii Ak ramas netestat .

2. a fost gasit ,caz în care se tasteaza daca aceasta îndeplinste anumite conditii , aparând astfel doua posibilitatii :

I. le îndeplineste ,caz în care se tasteaza daca s-a ajuns la solutie si apar .din nou ,doua posibilitati :

1) s-a ajuns la o solutie ,se tipareste solutia si se reia algoritmul considerând generate elementele X1, X,…. Xk ( se cauta în continuare un alt element al multimi Ak+1 ramas netestat )

2) nu s-a ajuns la o solutie ,caz în care se reia algoritmul considerând

3) d generate elemente X1, X,…. Xk+1 si se cauta un prim element Xk+2 €Ak+2 .

4) nu le îndeplineste ,caz în care reia algoritmul considerând generate elementele X1, X,…. Xk ,iar elementul Xk+1 se cauta între elementele multimii Ak+1 ramase netestate .

Algoritmul se termina atunci când nu mai exista nici un element X1 € A1 netestat .

Observatie :tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei .În cazul în care se cere o singura solutie ,se poate forta oprirea , atunci când a fost gasita .

Pentru usurarea metodei ,vom prezenta o rutina unica ,aplicabila oricarei probleme ,rutina care utilizeaza notiunea de stiva .Rutina va apela produceri de functii care au întotdeauna acelasi nume si parametri si care ,din punctul de vedere