METODA BACKTRAKCING
1) PREZENTARE GENERAL
In informatica apare frecvent situatia in care rezolvarea unei probleme conduce la determinarea unor vectori de forma X,x1,x2...xn, unde fiecare componenta xi apartine unei anumite multimi finite Vi, exista anumite relatii ce trebuie satisfacute de componentele vectorului ,numite CONDI[II INTERNE, astfel incat X este o solutie a problemei daca si numai daca aceste conditii sunt satisfacute de componentele x1,x2...xn ale vectorului.
EX.1
Fie 2 multimi de litere V1={a,b,cs si V2={m,ns., se cere sa se determine acele perechi x1,x2 cu x1V1 si x2V2 cu propietatea ca daca x1 este a sau b atunci x2 nu poate fi n.
rezolvarea problemei de mai sus conduce la vectorii {a, ms , {b, ms, {c, ms, {c, ns deoarece din cele sase solutii posibile doar acestea indeplinesc conditiile interne puse in enuntul problemei. Produsul cartezian V1*V2*..*Vn se nume 333t198d ste spatiul solutiilor posibile. Solutiile problemei sunt deci exact acele solutii care indeplinesc conditiile interne.
EX.2
Fie un joc de tip pronosport la care vom considera doar 4 meciuri. Sa presupunem ca un elev doreste sa participe la acest joc, plecand cu convingerea ca in variantele castigatoare nu pot exista mai mult de doua meciuri nule(cu pronostic X), iar la ultimul meci gazdele nu castiga; pentru aceasta el doreste sa gaseasca variantele care indeplinesc aceste conditii.
Se cere deci determinarea anumitilor vectori X={x1,x2,x3,x4s, in care valorile componentelor sunt pronosticuri pentru cele 4 meciuri. Prin urmare ,in aceasta problema V1=V2=V3=V4={X,1,2s. Pentru a fi solutie un asemenea vector trebuie sa indeplineasca urmatoarele doua conditii:
-in vectorul X nu pot aparea mai mult de doua pronosticuri X;
-ultima componenta poate fi doar X sau 2.
Exista mai multi vectori ce indeplinesc conditiile interne ,ca de exemplu :{x,1,2,xs,{1,2,1,2s, etc
O modalitate de a rezolva problema este in felul urmator: se genereaza pe rand toate cele 81 solutii posibile si se aleg cele care satisfac conditiile. Dar daca exista 13 meciuri exista 1.594.323 solutii, deci un numar foarte mare.
Conform celor de mai sus ,este foarte indicat ca pentru o problema data sa elaboram algoritmi care sa nu fie exponentiali. Sunt considerati buni algoritmii pentru care numarul operatiilor este polinomial -adica se poate exprima sub forma unui polinom n ,in care n este numarul datelor de intrare-.Nu este posibil sa evitam totdeauna algoritmii exponentiali ;un exemplu il constituie problema generarii tuturor submultimilor unei multimi, avand n elemente , cand numarul rezultatelor este 2n si deci numarul de operatii va fi inerent exponential.
astfel vom prezenta o metoda foarte importanta de elaborare a algoritmilor pentru probleme de genul descris mai sus: METODA BACKTRACKING.
2) PREZENTAREA METODEI.
Metoda BACKTRACKING urmareste sa evite generarea tuturor solutiilor posibile , scurtandu-se timpul de calcul .
Componentele vectorului X primesc valori in ordinea crescatoare a indicilor . Aceasta inseamna ca lui Xk nu i se atribuie o valoare decat dupa ce X1....Xk-1 au primit valori care nu contrazic conditiile interne. Mai mult , valoarea lui Xk trebuie aleasa astfel incat X1,....Xk sa indeplineasca si ele anumite conditii numite conditii de continuare, care sunt strans legate de conditiile interne. Astfel , daca in exemplul 2 componentele X1si X2 au primit ambele valoarea X, atunci numarului X3 nu i se poate atribui aceasta valoare -pentru a nu incalca restrictia ca numarul maxim de pronosticuri X sa fie cel mult 2-.
Neindeplinirea conditiilor de continuare exprima faptul ca oricum am alege Xk+1,...Xn, nu vom obtine o solutie -deci conditiile de continuare sunt STRICT NECESARE pentru obtinerea unei solutii-Ca urmare se va trece la atrbuirea unei valori lui Xk , doar cind conditiile de continuare sunt satisfacute. In cazul neindepleniri conditiilor de continuare , se alege o noua valoare Xk sau in cazul cand multimea finita de valori Vk a fost epuizata ,se incearca sa se faca o noua alegere pentru componenta precedenta Xk-1 a vectorului, micsorand pe k cu o unitate. Aceasta revenire da numele metodei , exprimand faptul ca atunci cand nu putem avansa, urmarim inapoi secventa curenta din solutie.
Prin metoda BACKTRACKING , orice vector solutie este construit progresiv incepand cu prima componenta si mergand catre ultima , cu eventuale reveniri asupra valorilor atribuite anterior. Prin atribuiri sau incercari de atribuire esuate din cauza nerespectarii conditiilor, anumite valori sunt consumate. Pentru o componenta oarecare , vom nota prin Ck multimea valorilor consumate la momentul curent.
O descriere completa a metodei se a metodei se poate face prin precizarea ,in momentul in care se incearca atribuirea unei valori componente Xk a urmatoarelor elemente:
1.valorile curente V1..Vk-1 ale componentelor X1..Xk-1
2.multimile C1..Ck-1 de valori consumate pentru fiecare dintre componentele X1..Xk-1
Semnificatia este urmatoarea:
-in incercarea de a construi un vector solutie componentele X1,...Xk-1 au primit valorile V1,...Vk-1;
-aceste valori satisfac conditiile de continuare ;
-urmeaza sa se faca o incercare de atribuire asupra componentei Xk; deoarece valorile consumate pana in acest moment sunt cele din Xk ea urmeaza a primi o valoare vk apartinand Vk \ Ck;
-valorile consumate pentru componentele X1..Xk-1 sunt cele din multimile C1..Ck-1 cu precizarea caa valorile curente V1..Vk-1 sunt considerate consumate deci apar in multimile C1..Ck-1;
-pentru componentele Xk+1...Xn nu s-a consumat nici o valoare deci Ck+1=...=Cn=
-pana in acest moment au fost deja construite
-eventualele solutii de forma V(1),...V(k-1), cu kCk;
-eventualele solutii de forma c(1),..c(k-1), cu c(1)..c(k-1) C(1)..C(k-1) si C(1),..C(k-1)V(1),...V(k-1)
METODA BACKTRACKING incepe a fi aplicata in situatia in care nu a fost consumata nici o valoare si se incearca o atribuire asupra primei componente.
In cursul aplicarii metodei , o configuratie poate fi obiectul a 4 tipuri de modificari , prezentate in cele ce urmeaza:
ATRIBUIE {I AVANSEAZ~. Acest tip de modificare are loc atunci cand mai exista valori neconsumate pentru x(k),( deci CkVk), iar valoarea aleasa vk apartine Vk\Ck are proprietatea ca V1...Vk satisfac conditiile de continuare. In acest caz valoarea Vk se atribuie lui Xk si se adauga multimii Ck( adica este considerata consumata), dupa care se avanseaza la componenta urmatoare Xk+1.
INCERCARE ESUAT~. Acest tip de modificare are loc atunci cand , ca si in cazul anerior, mai exista valori neconsumate pentru Xk , dar de data aceasta valoarea aleasa vk apartine Vk\Ck face ca v1...vk-1, vk, sa nu verifice conditiile de continuare. In acest caz vk este adaugat multimii Ck este deci consumata, dar nu se avanseaza la componenta urmatoare.
REVENIRE Acest tip de modificare are loc atunci cand toate valorile pentru xk au fost consumate (Ck=Vk) ; in acest caz se revine la componenta xk-1 , incercand atribuirea unei valori noi acestei componente; este important de remarcat ca pentru aceasta noua valoare xk-1 se vor incerca ulterior toate valorile posibile pentru xk, deci revenirea la xk-1 trebuie insotita de reconsiderarea valorilor consumate (Ck =>multimea vida).
REVENIRE DUP~ CONSTRUIREA UNEI SOLU[II. Acest tip de modificare are loc atunci cand toate componentele vectorului au primit valori ce satisfac conditiile interne, adica a fost construita o solutie , in acest caz se revine dinnou la situatia in care ultima componenta Xn urmeaza sa primeasca alte valori (daca mai exista) pentru construirea altor solutii.
Aceasta revenire dupa construirea unei solutii este de fapt un caz particular de revenire:
- canditia K=n+1 este cea mai utilizata de obicei in practica pt. a sesiza obtinrea unei solutii .
-conditia k=0 e cea mai utilizata de obicei in practica pentru a sesiza finalul procesului de construire a solutiilor
-Oproblema importanta e cea a incheierii procesului de cautare a tuturor solutiilor tinand cont ca V1,V2,...Vn sunt finite iar prin modificari succesive de configuratie nu e posibil sa se ajunga de doua ori la aceeasi configuratie rezulta ca la un moment dat se va ajunge la configuratia finala:
Procesul de obtinere a vectorilor solutie prin metoda BACKTRACKING este usor de programat deoarece orice modificare de configuratie nu afecteaza decat putine elemente si anume indicele k al componentei din dreapta barei (cea care urmeaza sa primeasca o valoare), componenta x(k) si multimea Ck de valori consumate.
ALGORITMUL CORESPUNZATOR ESTE:
-initializeaza multtimile de valori V1...Vn;construieste configuratia initiala
k:=1; c1:=multimea vida, oricare ar fi i=1..n
while k>0 -configuratia nu e finala -
if k=n+1 then - configuratia este de tip solutie retine solutia x=(x1,..xn)
k:=k-1 - revenire dupa construirea unei solutii -
else if Ck<>Vk then - mai exista valori neconsumate, alege o valoare vk din Vk\Ck -
Ck:=Ck+1;
if (v1,...vn satisfac conditiile de continuare)
then - atribuie si avanseaza-
else - incercare esuata-
else -revenire-
Programarea algoritmului de mai sus se simplifica mult daca se considera ca multimile de valori V1,....Vn sunt de forma:V1=1,2,...1,.....Vn=1,2,...n deci fiecare multime Vk poate fi reprezentata simplu prin numarul sau de elemente s(k). Se presupune de asemenea ca valorile pentru fiecare componenta x(k) vor fi alese in ordine crescatoare. In aceasta situatie fiecare multime de valori consumate Ck este de forma 1,2,..k si drept consecinta poate fi reprezentata doar prin valoarea Vk. Cum Vk este numarul elementelor multimii Ck aceasta multime este vida daca si numai daca Vk=0.
Cele de mai sus permit inlocuirea in algoritm a multimilor cu numere; mai mult , linia a doua a configuratiilor devine inutila, ea putand fi dedusa din valorile componentelor x1,...xk.
Se observa ca desi A,M sunt codificate prin acelasi numar , ele sunt distinse prin pozitia pe care o ocupa in vectorul solutie. In multe probleme , multimile in care pot lua valori componentele vectorului sunt identice cu o multime finita oarecare S cu s elemente, codificata astfel: S=1,2..s. In acest caz PROCEDURA CORESPUNZ~TOARE ESTE:
procedure backtracking;
var k,i:integer;
begin k:=1;
for i:=1 to n do x(I):=0; {configuratia initiala s
While k <>0 do
if k=n+1 then begin
retsol
k:=k-1;
end
else if x(k)<s then
begin
x(k):=x(k)+1;
if continuare(k) then k:=k+1;
end
else
begin
x(k):=0;
k:=k-1;
end;
end
Procedura backtracking apeleaza:
-procedura RETSOL care retine solutia , adica valorile vectorului x. Concret , aceasta poate insemna listarea solutiei , compararea ei cu solutiile precedente etc.
-functia CONTINUARE (K) verifica daca valorile primelor k componente ale vectorului x satisfac conditiile de continuare ; in caz afirmativ este intoarsa valoarea TRUE iar in caz contrar valoarea FALSE.
Sa se genereze folosind backtraking recursiv combinari de n luate cate k.
program combinari;
uses crt;
var x:array[1..100t of integer;
n,p,i,k:integer;
procedure retsol;
begin
for i:=1 to p do write(x[it,' ');
writeln
end
function cont(k:integer):boolean;
begin
cont:=true;
if k>=2 then if x[k-1t>=x[kt then cont:=false;
end
procedure back(k:integer);
var j:integer;
begin
for j:=1 to n do begin
x[kt:=j;
if cont(k) then if k<p then back(k+1)
else retsol;
end;
end
begin
clrscr
write('N=');readln(n);
write('P=');readln(p);
back(
readkey
end
Sa se genereze folosind backtraking recursiv aranjamente de n luate cate k.
program aranjamente;
uses crt;
var x:array[1..100t of integer;
n,p,i,k:integer;
procedure retsol;
begin
for i:=1 to p do write(x[it,' ');
writeln
end
function cont(k:integer):boolean;
begin
cont:=true;
for i:=1 to k-1 do if x[it=x[kt then cont:=false;
end
procedure back(k:integer);
var j:integer;
begin
for j:=1 to n do begin
x[kt:=j;
if cont(k) then if k<p then back(k+1)
else retsol;
end;
end
begin
clrscr
write('N=');readln(n);
write('P=');readln(p);
back(
readkey
end
Sa se genereze folosind backtraking recursiv permutari de n luate cate k.
program permutari;
uses crt;
var x:array[1..100t of integer;
n,i,k:integer;
procedure retsol;
begin
for i:=1 to n do write(x[it,' ');
writeln
end
function cont(k:integer):boolean;
begin
cont:=true;
for i:= 1 to k-1 do if x[it=x[kt then cont:=false;
end
procedure back(k:integer);
var j:integer;
begin
for j:=1 to n do begin
x[kt:=j;
if cont(k) then if k<n then back(k+1)
else retsol;
end;
end
begin
clrscr
write('N=');readln(n);
back(
readkey
end
Sa se genereze folosind backtraking recursiv produsul cartezian a trei multimi.
program produscart;
uses crt;
var y,x:array[1..100t of integer;
a,b,c:array[1..10t of char;
var i,k:integer;
procedure retsol;
begin write(a[x[1tt:4,b[x[2tt:4,c[x[3tt:4);
writeln
readln
end
function cont(k:integer):boolean;
begin
cont:=true;
end
procedure back(k:integer);
var j:integer;
begin
for j:=1 to y[kt do begin
x[kt:=j;
if cont(k) then if k<3 then back(k+1)
else retsol;
end;
end
begin
clrscr
for i:=1 to 3 do begin
write('Numarul de elemente al multimii ',i,': ');
readln y[it);
end;
write('Introduce-ti elementele multimii 1:');
for i:=1 to y[1t do begin
write('A[',i,'t=');
readln a[it);
end;
write('Introduceti elemntele multimii 2:');
for i:=1 to y[2t do begin
write('B[',i,'t=');
read (b[it);
end;
write('Introduceti elemntele multimii 3:');
for i:=1 to y[3t do begin
write('C[',i,'t=');
read(c[it);
end;
back(
readkey
end
|
