Metoda de programare Backtracking

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 in ce mai complexe.

Definit in anul 1971 de cǎtre Niklaus Wirth, limbajul Pascal (numit astfel in cinstea matematicianului francez Blaise Pascal), este un limbaj de interes general, coceput initial in scop didactic, ca instrument de invǎtare a programǎrii in 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 in programare si a fost apoi axtins cu facilitǎti care sǎ-i asigure utilizarea performantǎ ca limbaj inalt ce poate fi folosit in rezolvarea unei mari diversitǎti de probleme, cu grad sporit de complexitate.

Limbajul de programare PASCAL este un limbaj agreat de programatori, permitandu-le acestora sǎ alcǎtuiascǎ cu usurintǎ in mod sistematic programe complexe.

Lucrarea urmǎreste prezentarea si explicarea detaliatǎ a metodei BACKTRACKING punand accent pe forma generalizatǎ a metodei. Aceasta cuprinde, pe langǎ toate toate aspectele usual abordate in cadrul metodei, si unele chestiuni de dificultate sporitǎ, oferind astfel puncte de pornire in aprofundarea metodei.

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

S-au inclus in capitolele III, IV si V probleme ce se rezolvǎ cu ajutorul metodei, toate fiind insotite de explicarea si rezolvarea completǎ, dand si indicatii despre particularitǎti ale metodei. Problemele nu sunt de acelasi nivel, dificultatea acestora crescand pe parcursul celor 3 capitole.

Facem referire cǎ problemele rezolvate sub formǎ de program in limbaj de programare Borland Pascal   au fost mai intai testate si verificate pentru evitarea erorilor.

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

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

Am putea sǎ generǎm toate combinatiile posibile de valori si apoi sǎ le alegem doar pe cele convenabile. Considerand 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.

Rezolvand problema in acest mod, deci generind tote elementele produsului cartezian si verificand 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 incat fiecare literǎ sǎ aparǎ o singurǎ datǎ, combinatiile posibile sunt in numǎr de 27, dintre care convin doar 6.

Tehnica Backtracking propune generarea solutiei prin completarea vectorului x in ordine x₁x₂ x_n si are la bazǎ un principiu "de bun simt": dacǎ se constatǎ cǎ avand 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 incearcǎ o alta (dintre cele netestate in aceastǎ etapǎ). Intr-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 cuvantul 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 incercǎ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 in continuare de componenta x_k Pasii urmati sunt:

Pentru inceput, pentru x_k nu s-a testat incǎ nici o valoare.

Se verificǎ dacǎ existǎ valori netestate pentru x_k

a)     In 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 incǎ pentru x_k.

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

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

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

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

a)     In caz afirmativ, se tipǎreste aceastǎ solutie si se rǎmane la aceeasi componentǎ x_k, reluandu-se pasul 2.

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

Altgoritmul incepe prin stabilirea unei valori pentru componenta x₁(k=1) si se incheie cand pentru aceasta am testat toate valorile posibile si conform pasului 2b) ar trebui sǎ revenim la componenta anterioarǎ, care in aceast caz nu existǎ.

Rezumand, metoda Backtracking se foloseste in rezolvarea problemelor care indeplinesc 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 in considerare toate valorile posibile).

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

vectorul solutie - cate 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 in 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ǎ, prezentand insǎ particularitǎti in functie de fiecare problemǎ in 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 in aceastǎ ordine.

Initial, cand pentru o componentǎ nu am testat incǎ nimic, aceasta va avea valoarea 0 (un indice care nu existǎ). Aceastǎ operatie se va realiza in 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ǎ). Intrucat elementele sunt testate in ordine, acest lucru este echivalent cu a verifica dacǎ mai avem valori netestate incǎ pentru aceastǎ componentǎ.

Functia CONT(k) verificǎ dacǎ valoarea aleasǎ pentru x[k] indeplineste 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 in vedere cǎ altgoritmul general se poate modifica si adapta in functie de problema rezolvatǎ.

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

In acest caz vectorul x trebuie sǎ descrie aceste caracteristici. Valorile posibile ale unei componente trebuie generate in ordine, dar pentru cǎ o valoare are mai multe caracteristici vom utiliza o variabilǎ auxiliarǎ cu ajutorul cǎreia vom nota (si vom obtine) in 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 incǎ pentru componenta k (practic dacǎ mai existǎ valori posibile pentru componenta corespunzatoare din vectorul auxiliar).

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

CONT, SOLUTIE, TIPAR au aceeasi semnificatie ca si in 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.

Intr-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:

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

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 in labirint. Un element al vectorului, x[k], contine coordonatele unui punct in 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:

Aflandu-se intr-un punct dat, persoana poate sǎ mearga in 4 directii pe care le codificǎm cu 1,2,3,4

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

Astfel:

Din punctul k-1 caracterizat de coordonatele (x[k-1].1,x[k-1].c) ca punct urmǎtor in 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 in punctul curent.

Astel, coordonatele punctului curent se deduc in 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 in 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:

Procedura BKTG este modificatǎ in 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ǎ in pozitia (l0,c0). Sǎ se gǎseascǎ toate modalitǎtile prin care acesta poate sǎ parcurgǎ intreaga 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 in cazul labirintului, avand 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: aflandu-se intr-un punct dat, calul poate sǎri in 8 directii pe care le codificǎm 1,2, . , 8, ca in 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 in 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 in punctul current.

Astfel, coordonatele punctului curent se deduc in 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 in 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 in care se aflǎ persoana initial: k =1, x[k].l = l0 =1, x[k].c = c0 = 1.

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

Datele folosite in 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 in care se cunoaste inǎltimea fiecǎrei portiuni de teren. O bilǎ se aflǎ in parcela (l0,c0).

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

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

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

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

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

- directia 1: bila se mutǎ cu 1 linie mai sus, deci deplasamentul liniei este -1      coloana rǎmane 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ǎmane 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 in 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 in punctual current.

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

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

Declaratiile folosite in 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;

Programul pacal pentru problema-saritura bilei este:

Program bila;

Const

Dx:array[1..8] of integer=(-1,-1,0,1,1,1,0,-1);

Dy:array[1..8] of integer=(0,1,1,1,0,-1,-1,-1);

Var

a:array[0..10,0..20] of integer;

h:array[1..20,1..20] of integer;

m,n,xi,yi,I,j,xf,yf,nr:integer;

ok:Boolean;

f:text;

sir:string;

procedure afisare(k:integer);

var i,j:integer;

begin

nr:=nr+1;

writeln('solutia '.nr);

for i:=1 to m do begin

for j:=1 to n do

write(a[I,j]:3,'');

writeln;

end;

writeln('avem',k,'mutari');

readln;

end;

function sol(x,y:integer):Boolean;

begin

sol:=false;

if(x=xf) and (y=yf) then sol:=true;

end;

function cont(x,y,xx,yy:integer):Boolean;

begin

cont:=true;

fi a[xx,yy]<>0 then cont:=false;

if(xx<1) or (xx>n) then cont:=false;

if(yy<1) or (yy>m) then cont:=false;

if h[x,y]<h[xx,yy] then cont:=false;

end;

procedure back(x,y,k:integer);

var

xx,yy,i:integer;

begin

if sol(x,y) then afisare(k-1)

else for i:=1 to 8 do begin

xx:=x+dx[i];

yy:=y+dy[i];

if cont(x,y,xx,yy)then begin

a[xx,yy]:=k;

back(xx,yy,k+1);

a[xx,yy]:=0;

end;

end;

end;

begin

clrscr;

assing(f,'bila.txt');

reset(f);

readln(f,xi,yi);

readln(f,xf,yf);

readln(f,m,n);nr:=0;

for i:=1 to m do for j:=1 to n do a[I,j]:=0;

a[xi,yi]:=1;

for i:=1 to m do begin

for j:=1 to n do read(f,h[I,j]);

readln(f);end;

back(xi,yi,2);

if nr=0 then write('nu are solutie');

readln;

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, insǎ aplicate altor valori). Dar cum trecerea de la componenta k la urmǎtoarea face parte din actiunea descrisǎ de acest altgoritm, inseamnǎ cǎ apelul este recursiv.

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

Presupunem ca altgoritmul descries pentru o componentǎ k se incheie la epuizarea valorilor posibile pentru aceasta. In aceastǎ situatie se revenea la componenta anterioarǎ, reluand testǎrile pentru aceastǎ componentǎ. Intr-un apel recursiv, la incheierea executiei acestuie se revine la programul apelant - in cazul nostru am fǎcut apel din altgoritmul corespunzǎtor lui k-1, deci aceastǎ intoarcere nu trebuie fǎcutǎ explicit.

Altgoritmul general in 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 in varianta nerecursivǎ.

In programul principal procedura se va apela avand ca parametru prima componentǎ pentru cǎ aceasta se va completa prima. Se observǎ cǎ altgoritmul se va incheia atunci cand vor fi testate toate valorile posibile pentru aceastǎ componentǎ si deci seria de apeluri este incheiatǎ.

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. Toca, 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