Introducere .......................... 2

I. Metoda de programare Backtracking .................. 3

II. Metoda Backtracking generalizat .................... 5

III. Problema Labirintului ....................

IV. Problema sariturii calului ............... 11

V. Problema Bilei .................... 13

VI. Backtracking generalizat recursiv ................. 15

VII. Problema labirintului (recursiv) ................ 16

Bibliografie ......................

Pentru prelucrarea informatiei omul a inventat calculatorul, dar datoritǎ dezvoltǎrii vertiginoase a prelucrǎrilor de date cu calculatorul, s-au putut aborda si rezolva probleme din ce īn ce mai complexe.

Definit īn anul 1971 de cǎtre Niklaus Wirth, limbajul Pascal (numit astfel īn cinstea matematicianului francez Blaise Pascal), este un limbaj de interes general, coceput initial īn scop didactic, ca instrument de īnvǎtare a programǎrii īn mod sistematic. Datoritǎ calitǎtilor sale (foloseste un mod bine structurat de reprezentare a programelor, asigurǎ claritate, sugestivitate si simplitate), acest limbaj a fost adoptat rapid ca limbaj de initiere īn programare si a fost apoi axtins cu facilitǎti care sǎ-i asigure utilizarea performantǎ ca limbaj īnalt ce poate fi folosit īn rezolvarea unei mari diversitǎti de probleme, cu grad sporit de complexitate.

Limbajul de programare PASCAL este un limbaj agreat de programatori, permitāndu-le acestora sǎ alcǎtuiascǎ cu usurintǎ īn mod sistematic programe complexe.

Lucrarea urmǎreste prezentarea si explicarea detaliatǎ a metodei BACKTRACKING punānd accent pe forma generalizatǎ a metodei. Aceasta cuprinde, pe lāngǎ toate toate aspectele usual abordate īn cadrul metodei, si unele chestiuni de dificultate sporitǎ, oferind astfel puncte de pornire īn aprofundarea metodei.

Īn capitolele I si II, pentru fixarea cunostintelor de bazǎ si pentru crearea unor deprinderi de organizare riguroasǎ īn cadrul metodei Backtracking simple si generalizate.

S-au inclus īn capitolele III, IV si V probleme ce se rezolvǎ cu ajutorul metodei, toate fiind īnsotite de explicarea si rezolvarea completǎ, dānd si indicatii despre particularitǎti ale metodei. Problemele nu sunt de acelasi nivel, dificultatea acestora crescānd pe parcursul celor 3 capitole.

Facem referire cǎ problemele rezolvate sub formǎ de program īn limbaj de programare Borland Pascal      au fost mai īntāi testate si verificate pe 20120j912u ntru evitarea erorilor.

Capitolul VI exemplificǎ utilizarea metodei Backtracking generalizat recursive, dǎ detalii īn legǎturǎ cu modul acesta de rezolvare a problemelor, īn capitolul VII fiind reluatǎ problema din capitolul III dar implementatǎ acum recursiv.

De multe ori, īn aplicatii apar probleme īn care se cere gǎsirea unor solutii de forma x=x₁x₂... x_n unde x_i A, i = 1,.,n īn care x₁.x_n trebuie sǎ īndeplineascǎ anumite conditii.

Am putea sǎ generǎm toate combinatiile posibile de valori si apoi sǎ le alegem doar pe cele convenabile. Considerānd multimile A = , aceste combinatii s-ar putea construi astfel: pentru fiecare valoare posibilǎ fixatǎ pentru componenta x_i, vom alege toate valorile posibile pentru componenta x_i+1 si pentru fiecare astfel de valoare fixatǎ pentru x_i+1 vom alege toate valorile posibile pentru componenta x_i+2, etc.

Rezolvānd problema īn acest mod, deci generīnd tote elementele produsului cartezian si verificānd abia apoi dacǎ fiecare combinatie este o solutie, eficientǎ este scǎzutǎ.

Astfel, dacǎ de exemplu ne propunem sǎ generǎm toate cuvintele formate cu litere a,b,c, asa īncāt fiecare literǎ sǎ aparǎ o singurǎ datǎ, combinatiile posibile sunt īn numǎr de 27, dintre care convin doar 6.

Tehnica Backtracking propune generarea solutiei prin completarea vectorului x īn ordine x₁x₂... x_n si are la bazǎ un principiu "de bun simt": dacǎ se constatǎ cǎ avānd o combinatie partialǎ de formǎ v₁v₂...v _k-1 (unde v_i,.,v_k-1 sunt valori deja fixate), dacǎ alegem pentru x_k o valoare v_k si combinatia rezultatǎ nu ne permite sǎ ajungem la o solutie, se renuntǎ la aceastǎ valoare si se īncearcǎ o alta (dintre cele netestate īn aceastǎ etapǎ). Īntr-adevǎr, oricum am alega celelalte valori, dacǎ una nu corespunde nu putem avea o solutie.

Pentru exemplu ales anterior se observǎ cǎ dacǎ notǎm cuvāntul cu x₁x₂x₃, combinatia aax₃ nu ne poate conduce la o solutie (literele trebuie sǎ fie distincte) si deci nu are sens sǎ mai īncercǎm sǎ stabilim valori pentru x₃.

Altgoritmul general al metodei Backtracking

Pentru evitarea generǎrii combinatiilor neconvenabile se procedeazǎ astfel:

Presupunem cǎ s-au gǎsit valorile v₁v₂.v_k-1 pentru componentele x₁x₂... x_k-1 (au rǎmas de determinat valorile pentru x_k.x_n). ne ocupǎm īn continuare de componenta x_k Pasii urmati sunt:

Pentru īnceput, pentru x_k nu s-a testat īncǎ nici o valoare.

Se verificǎ dacǎ existǎ valori netestate pentru x_k

a)      Īn caz afirmativ, se trece la pasul 3.

b)     Altfel, se revine la componenta anterioarǎ, x_k-1; se reia pasul 2 pentru k=k-1.

Se alege prima valoare v dintre cele netestate īncǎ pentru x_k.

Se verificǎ dacǎ acestǎ combinatie partialǎ v₁v₂.v_k-1v ne poate conduce la un rezultat (dacǎ sunt īndeplinite anumite conditii de continuare).

a)      Dacǎ valoarea aleasǎ este bunǎ se trece la pasul 5.

b)     Altfel, se rǎmāne pe aceeasi pozitie k si se reia cazul 2.

Se verificǎ dacǎ s-a obtinut o solutie .

a)      Īn caz afirmativ, se tipǎreste aceastǎ solutie si se rǎmāne la aceeasi componentǎ x_k, reluāndu-se pasul 2.

b)     Altfel se reia altgoritmul pentru urmǎtoarea componentǎ (se trece la pasul 1 pentru k=k+1).

Altgoritmul īncepe prin stabilirea unei valori pentru componenta x₁(k=1) si se īncheie cānd pentru aceasta am testat toate valorile posibile si conform pasului 2b) ar trebui sǎ revenim la componenta anterioarǎ, care īn aceast caz nu existǎ.

Rezumānd, metoda Backtracking se foloseste īn rezolvarea problemelor care īndeplinesc conditiile:

solutia poate fi pusǎ sub forma unui vector S=x₁x₂.x_n, unde x_i

multimile A_i sunt finite si ordonate (pentru a lua īn considerare toate valorile posibile).

Īnainte de a scrie programul care ne va obtine solutiile, trebuie sǎ stabilim unele detalii cu privire la:

vectorul solutie - cāte componente are, ce mentine fiecare componentǎ.

multimea de valori posibile pentru fiecare componentǎ (sunt foarte importante limitele acestei multimi).

conditiile de continuare (conditiile ca o valoare x[k]sǎ fie acceptatǎ).

conditia ca ansamblul de valori generat sǎ fie solutie.

Pe baza acestor date vom scrie apoi procedurile si functiile pe care le vom apela īn altgoritmul general al metodei, dat mai jos, care se poate aplica tuturor problemelor ce respectǎ conditiile mentionate anterior. Aceste proceduri si functii au o semnificatie comunǎ, prezentānd īnsǎ particularitǎti īn functie de fiecare problemǎ īn parte.

Astfel, se va nota cu x vectorul care contine solutia; x[k] = v va avea ca semnificatie faptul cǎ elementul al-v­-lea din multimea de valori ppsibile A_k a fost selectat pentru componenta x_k. dacǎ multimea A_k are m elemente, a₁a₂.a_m,pentru usurintǎ ne vom referii la indicii lor 1,2,.,m. Deci valorile posibile pentru o componentǎ vor fi 1,2,.,m īn aceastǎ ordine.

Initial, cānd pentru o componentǎ nu am testat īncǎ nimic, aceasta va avea valoarea 0 (un indice care nu existǎ). Aceastǎ operatie se va realiza īn procedura INIT care va avea ce parametru pozitia k.

Functia EXISTA(k) verificǎ dacǎ ultima valoare aleasǎ pentru componenta x_k nu a atins limita maximǎ admisǎ (indicele de valoare maximǎ). Īntrucāt elementele sunt testate īn ordine, acest lucru este echivalent cu a verifica dacǎ mai avem valori netestate īncǎ pentru aceastǎ componentǎ.

Functia CONT(k) verificǎ dacǎ valoarea aleasǎ pentru x[k] īndeplineste conditiile de continuare, deci dacǎ aceastǎ combinatie partialǎ v₁v₂.v_k poate sǎ conducǎ la o solutie.

Functia SOLUTIE(k) verificǎ dacǎ s-a ajuns la o solutie finalǎ.

Procedura TIPAR(k) tipǎreste o solutie.

Altgoritmul propus este:

procedure BKT;

var k:integer;

begin

k:=1;

INIT(k);

while k>0 do

if EXISTA(k) then

begin

x[k]:=x[k]+1;

VALPOS(k);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

begin

k:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

De asemenea, trebuie sǎ avem īn vedere cǎ altgoritmul general se poate modifica si adapta īn functie de problema rezolvatǎ.

Metoda Backtracking generalizat are urmǎtoarea deosebire fatǎ de metoda obisnuitǎ de Backtracking: īn metoda obisnuitǎ vectorul solutie este un tablou unidimensional, x₁,x₂.x_n, fiecare componentǎ avānd o anumitǎ valoare la un moment dat, dar dacǎ componenta x_k are mai multe caracteristici atunci este nevoie folosirea metodei generalizate.

Īn acest caz vectorul x trebuie sǎ descrie aceste caracteristici. Valorile posibile ale unei componente trebuie generate īn ordine, dar pentru cǎ o valoare are mai multe caracteristici vom utiliza o variabilǎ auxiliarǎ cu ajutorul cǎreia vom nota (si vom obtine) īn ordine toate aceste valori posibile.

Astfel, pentru a genera toate valorile posibile pentru o componentǎ k este suficient sǎ generǎm toate valorile posibile pentru aceastǎ variabilǎ auxiliarǎ si pe baza lor sǎ aflǎm valorile lui x[k]

De exemplu dacǎ x este vectorul solutie, iar d vectorul auxiliar, putem descrie un tip de bazǎ pentru o componentǎ astfel:

const nmax=20

type component=record

caract1: tip1;

caract2: tip2;

....

end;

var x:array[1..nmax] of component;

d:array[1..nmax] of integer;

Un altgoritm general ar putea fi:

procedure BKTG;

var k:integer;

begin

k:=1;

INIT(k);

while k>0 do

if EXISTA(k) then

begin

d[k]:=d[k]+1;

VALPOS(k);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

begin

k:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

Procedura INIT va initializa datele referitoare la componenta k-practic va initializa componenta corespunzǎtoare din vectorul auxiliar, d[k]

Functia EXISTA verificǎ dacǎ mai existǎ valori netestate īncǎ pentru componenta k (practic dacǎ mai existǎ valori posibile pentru componenta corespunzatoare din vectorul auxiliar).

Procedura VALPOS va completa pentru componenta k īn vectorul solutie valoarea caracteristicilor sale, īn functie de valoarea lui d[k]

CONT SOLUTIE TIPAR au aceeasi semnificatie ca si īn cazul metodei simple.

Se dǎ un labirint sub formǎ de matrice

cu m linii si n coloane. Fiecare element al matricei se codificǎ cu: '0' dacǎ este zid si cu '1' dacǎ este culoar.

Īntr-un punct al labirintului, de coordonate (l0,c0) se gǎseste o persoanǎ. Se cere sǎ se gǎseascǎ toate iesirile din labirint.

De exemplu, pentru un labirint cu configuratia

unde l0=3, c0=3,

am putea avea posibilitǎtile:

Pentru a scrie programul stabilim urmǎtoarele:

vom folosi matricea tab pentru a memora configuratia labirintului.

vectorul solutie are un numǎr variabil de componente si contine o succesiune de elemente ale tabloului care ar reprezenta un drum īn labirint. Un element al vectorului, x[k], contine coordonatele unui punct īn care ne aflǎm la pasul respective: linia si coloana (l,c).

pentru a determina multimea de valori posibile pentru o componentǎ, tinem cont de urmǎtoarele:

Aflāndu-se īntr-un punct dat, persoana poate sǎ mearga īn 4 directii pe care le codificǎm cu 1,2,3,4

Fiecare directie de deplasare induce un anumit deplasament liniei, respectiv coloanei.

Astfel:

			j			- pe directia 1: linia scade cu o unitate, deci deplasamentul ei este -1
						coloana rǎmāne aceesi, deci deplasamentul ei este 0
						- pe directia 2: linia rǎmāne aceeasi, deci deplasamentul ei este 0
i						coloana creste cu o unitate, deci deplasamentul ei este 1
						- pe directia 3: linia creste cu o unitate, deci deplasamentul ei este 1
						coloana rǎmāne aceesi, deci deplasamentul ei este 0
						- pe directia 4: linia rǎmāne aceeasi, deci deplasamentul ei este 0
						coloana scade cu o unitate, deci deplasamentul ei este -1

Din punctul k-1 caracterizat de coordonatele (x[k-1].1,x[k-1].c) ca punct urmǎtor īn traseul urmat ar putea fi unul din punctele vecine date de directia de deplasare aleasǎ. Deci vom alege ca vector auxiliar un vector d care ne memoreazǎ directia aleasǎ pentru a ajunge īn punctul curent.

Astel, coordonatele punctului curent se deduc īn functie de punctul din care se pleacǎ, x[k-1], directia de deplasare aleasǎ, d[k], respectiv deplasamentul indus de aceastǎ directie liniei si coloanei:

X[k].l = x[k-1].l + depl[d[k]].l

X[k].c = x[k-1].c + depl[d[k]].c

Deplasamentele fiind niste mǎrimi constante, pot fi initializate de la declarare.

Procedura VALPOS calculeazǎ coordonatele punctului corespunzǎtor componentei k īn functie de punctul din care se porneste si de directia aleasǎ.

conditii de continuare pentru ca o valoare x[k] sǎ fie acceptatǎ:

- persoana nu trebuie sǎ treacǎ de 2 ori prin acelasi loc;

- valoarea x[k] trebuie sǎ corespundǎ unui culoar.

am gǎsit o solutie finalǎ dacǎ am ajuns pe una din laturile labirintului, deci linia sau coloana sǎ se afle pe una din margini.           

Pentru exemplu considerat, vectorul solutie se va completa astfel:

d1d2d3.	x1  x2 x3 .
		Stabilim valoarea primei componente, care este corespunzǎtoare punctului din care se pleacǎ(l0,c0). Directia din care s-a ajuns aici nu intereseazǎ.
		Prima directie posibilǎ este 1. Din (3,3) pe directia 1 ajungem in punctul (2,3) -convine este pe culoar. Trecem la urmǎtoarea componentǎ, k=3.
		Īncepem cu prima directie posibilǎ pentru acestǎ componentǎ, d[3]=1; coordonatele punctului corespunzǎtor lui k=3 īn care ajungem din x[2]pe directia 1 sunt (1,3) -convine. Se observǎ cǎ am ajuns la marginea labirintului, deci am obtinut o solutie ,pe care o tipǎrim. Rǎmānem la k=3.
		Urmǎtoarea valoare posibilǎ pentru d[3] este 2; punctul īn care ajungem este (2,4) care nu convine, fiind īn zid. Rǎmānem la k=3.
		Pornind din (2,3) pe directia 3 ajungem īn (3,3)- nu convine, am mai trecut pe aici. Deci in continuare k=3.
		Pentru urmǎtoarea directie, 4, punctul īn care se ajunge din (2,3) este (2,2) -nu convine este zid. Am epuizat toate directiile posibile pentru k=3, deci revenim la k=2.
		Urmǎtoarea directie posibilǎ pentru k=2 este 2; punctul īn care se ajunge este (3,4), care convine. Trecem la k=3;
		Prima directie aleasa este 1; pornind din x[k-1] -punctul (3,4), ajungem īn (2,4) - nu convine, fiind zid, rǎmānem la k=3;
		Pe directia d[3]=2, punctul īn care se ajunge este (3,5) -este pe margine, deci am obtinut o nouǎ solutie. Rǎmānem la k=3, pentru o nouǎ directie.
		Urmǎtoarea valoare pentru d[3]este 3, iar x[3]-punctul (4,4) -convine; trecem la k=4.
		Prima directie posibilǎ este d[4]=1, iar x[4]este punctul (3,4) -nu convine; rǎmānem la k=4.
		Procedeul continuǎ pānǎ cānd am epuizat toate valorile posibile pentru componenta d[2](de la ea īncepe generarea).

Procedura BKTG este modificatǎ īn ceea ce priveste faptul cǎ generarea se face pentru componentele 2,3,. deoarece prima pozitie este fixatǎ.

Programul corespunzǎtor este:

program labirint1;

uses crt;

type component=record

l,c:integer;

end;

vectsol=array[1..100]of component;

auxiliar=array[1..100]of 0..4;

labirint=array[1..25,1..25]of char;

const depl:array[1..4]of component=((l:-1;c:0),(l:0;c:1), (l:1;c:0),(l:0;c:-1));

var x:vectsol;

d:auxiliar;

tab:labirint;

n,m:integer;

l0,c0:integer;

procedure citire;

var i,j:integer;

begin

clrscr;

writeln('configuratia labirintului: ');

write('m=');readln(m);

write('n=');readln(n);

writeln('Se codifica astfel: 1-culoar; 0-zid');

for i:=1 to m do

for j:=1 to n do

begin

write('tab[',i,',',j,']=');

readln(tab[i,j]);

end;

writeln('Pozitia initiala: ');

write('l0=');readln(l0);

write('c0=');readln(c0);

x[1].l:=l0;

x[1].c:=c0;

end;

procedure INIT(k:integer);

begin

d[k]:=0;

end;

function EXISTA(k:integer):boolean;

begin

EXISTA:=d[k]<4;

end;

procedure VALPOS(k:integer);

begin

x[k].l:=x[k-1].l+depl[d[k]].l;

x[k].c:=x[k-1].c+depl[d[k]].c;

end;

function CONT(k:integer):boolean;

var i:integer;

begin

CONT:=true;

for i:=1 to k-1 do

if(x[i].l=x[k].l)and(x[i].c=x[k].c)then

CONT:=false;

with x[k] do

if tab[l,c]='0'then

CONT:=false;

end;

function SOLUTIE(k:integer):boolean;

begin

with x[k] do

SOLUTIE:= (l=1)or(c=1)or(l=m)or(c=n)

end;

procedure TIPAR(k:integer);

var i,j:integer;

begin

for i:=1 to k do

with x[i] do

write(l,' ',c, ' ');

readln;

end;

procedure BKTG;

var k:integer;

begin

k:=2;

INIT(k);

while k>1 do

if EXISTA(k)then

begin

d[k]:=d[k]+1;

VALPOS(k);

if CONT(k)then

if SOLUTIE(k)then

TIPAR(k)

else

begin

k:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

begin

CITIRE;

BKTG;

end.

Se dǎ o tablǎ de sah de dimensiune mxn. Un cal se aflǎ īn pozitia (l0,c0). Sǎ se gǎseascǎ toate modalitǎtile prin care acesta poate sǎ parcurgǎ īntreaga tablǎ farǎ sǎ treacǎ de douǎ ori prin acelasi loc.

De exemplu, pentru n = m = 5, si pozitia initialǎ (1,1) o solutie este:

Problema trateazǎ aceeasi situatie ca si īn cazul labirintului, avānd specificǎ alegerea valorilor posibile pentru o componentǎ.

Pentru a scrie programul, vom stabili urmǎtoarele repere:

- vectorul solutie are nxm componente, fiind nxm elemente pe tabla de sah (iar calul trebuie sǎ treacǎ prin toate). Fiecare componentǎ caracterizeazǎ un element al tablei prin coordonatele sale l,c;

- determinarea valorilor posibile pentru componenta k se face astfel: aflāndu-se īntr-un punct dat, calul poate sǎri īn 8 directii pe care le codificǎm 1,2, ., 8, ca īn figura alǎturatǎ.

- pe directia 1: calul se mutǎ cu 2 linii mai sus, deci deplasamentul liniei este -2

coloana se mutǎ la dreapta cu 1, deci deplasamentul ei este 1

- pe directia 2: linia scade cu 1, deci deplasamentul ei este -1

coloana creste cu 2 unitati, deci deplasamentul ei este 2

- pe directia 3: linia coboarǎ cu o unitate, deci deplasamentul ei este -1

coloana se mutǎ la dreapta cu 2, deci deplasamentul ei este 2

.........

(analog se completeazǎ deplasamentele pentru toate cele 8 cazuri).

Din punctual k-1,caracterizat de coordonatele (x[k-1].l,x[k-1].c), ca punct urmǎtor īn traseul urmat ar putea fi unul din punctele date de directia de deplasare aleasǎ. Deci vom alege ca vector auxiliar un vector d care ne memoreazǎ directia aleasǎ pentru a ajunge īn punctul current.

Astfel, coordonatele punctului curent se deduc īn functie de punctul din care se pleacǎ, x[k-1], directia de deplasare aleasǎ, d[k],respective deplasamentul Indus de aceastǎ directie liniei si coloanei:

X[k].l = x[k-1].l + depl[d[k]].l

X[k].c = x[k-1].c + depl[d[k]].c

Deplasamentele fiind niste mǎrimi constante, pot fi initializate de la declarare.

- conditii de continuare:

- pozitia aleasǎ nu trebuie sǎ fie īn afara tablei de sah;

- calul nu trebuie sǎ trecǎ de mai multe ori prin acelasi loc, deci x[k]≠x[i] pentru orice i=1, .,k-1

- am am gǎsit o solutie finalǎ dacǎ am completat toate componentele vectorului (deci k=nxm ).

Pentru exemplul considerat se va stabili prima componentǎ cu coordonatele punctului īn care se aflǎ persoana initial: k =1, x[k].l = l0 =1, x[k].c = c0 = 1.

Se īncepe de la k = 2. Vectorul solutie se va completa astfel:

Datele folosite īn program sunt:

type component=record

l,c:integer;

end;

vectsol=array[1..100]of component;

auxiliar=array[1..100]of 0..4;

tabla=array[1..25,1..25]of integer;

const depl:array[1..8]of component=((l:-2;c:1),(l:-1;c:2),(l:1;c:2),

(l:2;c:1),(l:2;c:-1),(l:1;c:-2),(l:-1;c:-2),(l:-2;c:-1));

var x:vectsol;

d:auxiliar;

n,m:integer;

l0,c0:integer;

Procedurile si functiile care prezintǎ particularitǎti sunt:

procedure citire;

var i,j:integer;

begin

write('m=');readln(m);

write('n=');readln(n);

writeln('Pozitia initiala: ');

write('l0=');readln(l0);

write('c0=');readln(c0);

x[1].l:=l0;

x[1].c:=c0;

end;

function EXISTA(k:integer):boolean;

begin

EXISTA:=d[k]<=8;

end;

function CONT(k:integer):boolean;

var i:integer;

begin

CONT:=true;

with x[k] do

if (l<1)or(c<1)or(l>m)or(c>n)then

CONT:=false;

for i:=1 to k-1 do

if(x[i].l=x[k].l)and(x[i].c=x[k].c)then

CONT:=false;

end;

function SOLUTIE(k:integer):boolean;

begin

SOLUTIE:=(k=m*n);

end;

Se dǎ un teren parcelat īn care se cunoaste īnǎltimea fiecǎrei portiuni de teren. O bilǎ se aflǎ īn parcela (l0,c0).

Sǎ se gǎseascǎ toate modalitǎtile prin care bila poate ajunge la marginea terenului stiind cǎ ea poate trece doar īntr-o parcelǎ vecinǎ de īnǎltime mai micǎ.

Configuratia terenului poate fi memoratǎ sub forma unei matrici, un element al matricii corespunzānd unei parcele.

Pentru a scrie programul, vom stabili urmǎtoarele repere:

- vectorul solutie are un numǎr variabil de componente si mentine īn ordine parcelele prin care trece bila.

- valorile posibile se determinǎ tinānd cont cǎ, dintr-un punct dat, bila poate sǎ meargǎ īn 8 directii pe care le codificǎm cu 1,2, ., 8; fiecare directie de deplasare induce un anumit deplasament linie, respective coloanei; astfel:

			j
i

- directia 1: bila se mutǎ cu 1 linie mai sus, deci deplasamentul liniei este -1      coloana rǎmāne neschimbatǎ, deci deplasamentul ei este 0

- pe directia 2: bila se mutǎ cu 1 linie mai sus, deci deplasamentul liniei este -1   coloana se mutǎ la dreapta cu 1, deci deplasamentul ei este 1

- pe directia 3: bila rǎmāne pe aceeasi linie , deci deplasamentul liniei este 0   coloana se mutǎ la dreapta cu 1, deci deplasamentul ei este 1

(analog se completeazǎ deplasamentele pentru toate cele 8 cazuri).

Din punctual k-1, caracterizat de coordonatele (x[k-1].l,x[k-1].c), ca punct urmǎtor īn traseu ar putea fi unul din punctele vecine date de directia de deplasare aleasǎ. Deci vom alege ca vector auxiliar un vector d care ne memorezǎ directia aleasǎ pentru a ajunge īn punctual current.

- conditii de continuare pentru ca o valoare x[k]sǎ fie acceptatǎ: bila nu poate trece decāt pe o pozitie vecinǎ cu īnǎltimea mai mica;

- am gǎsit o solutie finalǎ dacǎ am ajuns la marginea terenului.

Declaratiile folosite īn program sunt:

type component=record

l,c:integer;

end;

vectsol=array[1..100]of component;

auxiliar=array[1..100]of 0..4;

teren=array[1..25,1..25]of integer;

const depl:array[1..8]of component=((l:1;c:-1),(l:-1;c:1),(l:0;c:1),

(l:1;c:1),(l:1;c:0),(l:1;c:-1),(l:0;c:-1),(l:-1;c:-1));

var x:vectsol;

d:auxiliar;

n,m:integer;

l0,c0:integer;

cote:teren;

Procedurile si functiile care prezintǎ particularitǎti sunt:

procedure citire;

var i,j:integer;

begin

writeln('configuratia terenului:');

write('m=');readln(m);

write('n=');readln(n);

for i:=1 to m do

for j:=1 to n do

begin

write('cote[',i,',',j,']=');

readln(cote[i,j]);

end;

writeln('Pozitia initiala: ');

write('l0=');readln(l0);

write('c0=');readln(c0);

x[1].l:=l0;

x[1].c:=c0;

end;

function EXISTA(k:integer):boolean;

begin

EXISTA:=d[k]<=8;

end;

function CONT(k:integer):boolean;

var i:integer;

begin

with x[k] do CONT:=cote[x[k-1].l,x[k-1].c]>cote[l,c];

end;

function SOLUTIE(k:integer):boolean;

begin

with x[k] do SOLUTIE:=(l=1)or(c=1)or(l=m)or(c=n);

end;

Dacǎ am scrie un altgoritm care operatiile efectuate asupra unei componente (fie ea k) a vectorului solutie generat prin metoda Backtracking generalizat, atunci am putea apela acest altgoritm si pentru componenta urmatoare, k+1 (pentru cǎ actiunile realizate asupra acestei componente sunt similare, īnsǎ aplicate altor valori). Dar cum trecerea de la componenta k la urmǎtoarea face parte din actiunea descrisǎ de acest altgoritm, īnseamnǎ cǎ apelul este recursiv.

Vom demonstra cǎ altgoritmul recursiv urmeazǎ corect pasii metodei Backtracking generalizat.

Presupunem ca altgoritmul descries pentru o componentǎ k se īncheie la epuizarea valorilor posibile pentru aceasta. Īn aceastǎ situatie se revenea la componenta anterioarǎ, reluānd testǎrile pentru aceastǎ componentǎ. Īntr-un apel recursiv, la īncheierea executiei acestuie se revine la programul apelant - īn cazul nostru am fǎcut apel din altgoritmul corespunzǎtor lui k-1, deci aceastǎ īntoarcere nu trebuie fǎcutǎ explicit.

Altgoritmul general īn varianta recursivǎ ar putea avea forma:

procedure BKTGR(k:integer);

begin

INIT(k);

while EXISTA(k) do

begin

d[k]:=d[k]+1;

VALPOS(k,d);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

BKTGR(k+1)

end;

end;

Celelalte functii care apar au aceeasi semnificatie si implementare ca si īn varianta nerecursivǎ.

Īn programul principal procedura se va apela avānd ca parametru prima componentǎ pentru cǎ aceasta se va completa prima. Se observǎ cǎ altgoritmul se va īncheia atunci cānd vor fi testate toate valorile posibile pentru aceastǎ componentǎ si deci seria de apeluri este īncheiatǎ.

program labirintul;

uses crt;

type component=record

l,c:integer;

end;

vectsol=array[1..100]of component;

auxiliar=array[1..100]of 0..4;

labirint=array[1..25,1..25]of 0..2;

const depl:array[1..4]of component= ((l:-1;c:0),(l:0;c:1), (l:1;c:0),(l:0;c:-1));

var x:vectsol;

d:auxiliar;

tab:labirint;

n,m:integer;

l0,c0:integer;

procedure citire;

var i,j:integer;

begin

clrscr;

writeln('configuratia labirintul:');

write('m=');readln(m);

write('n=');readln(n);

writeln('Se codifica astfel: 1-culoar; 0-zid');

for i:=1 to m do

for j:=1 to n do

begin

write('tab[',i,',',j,']=');

readln(tab[i,j]);

end;

writeln('Pozitia initiala: ');

write('l0=');readln(l0);

write('c0=');readln(c0);

x[1].l:=l0;

x[1].c:=c0;

end;

procedure INIT(k:integer);

begin

d[k]:=0;

end;

function EXISTA(k:integer):boolean;

begin

EXISTA:=d[k]<4;

end;

procedure VALPOS(k:integer);

begin

x[k].l:=x[k-1].l+depl[d[k]].l;

x[k].c:=x[k-1].c+depl[d[k]].c;

end;

function CONT(k:integer):boolean;

var i:integer;

begin

CONT:=true;

for i:=1 to k-1 do

if(x[i].l=x[k].l)and   (x[i].c=x[k].c)then

CONT:=false;

with x[k] do

if tab[l,c]=0 then

CONT:=false;

end;

function SOL(k:integer):boolean;

begin

with x[k] do

SOL:= (l=1)or(c=1)or

(l=m)or(c=n)

end;

procedure TIPAR(k:integer);

var i,j:integer;

begin

for i:=1 to k do

with x[i] do

writeln(l,' ',c);

readln;

end;

procedure BKTGR(k:integer);

begin

INIT(k);

while EXISTA(k) do

begin

d[k]:=d[k]+1;

VALPOS(k);

if CONT(k)then

if SOL(k)then

TIPAR(k)

else

BKTGR(k+1);

end

end;

begin

CITIRE;

BKTGR(2);

end.

BIBLIOGRAFIE:

L. Ţoca, A. R. Demco, C. Opincaru, A. Sindile

Informaticǎ - Manual pentru clasa a X-a

Editura Niculescu - Bucuresti, 2000

Fl. Munteanu, T. Ionescu, Gh. Muscǎ, D. Saru, S. M. Dascǎlu

Programarea calculatoarelor - Manual pentru liceele de informaticǎ,

clasele X-XII

Editura Didacticǎ si Pedagogicǎ - Bucuresti, 1995

S. Niculescu si colaboratori

Bacalaureat si atestat

Editura L&S, 1998