Metoda bakctracking
Metoda bakctracking(BT) este o tehnică de programare aplicabilă algoritmilor care oferă mai multe soluţii . Fiecare soluţie se memorează intr-o structură de date de tip stivă, care poate fi implementată cu ajutorul unui vector.
Fie st - vectorul- stivă, nr – numărul valorilor care alcătuiesc o soluţie. Atunci adăugarea şi extragerea de elemente se va face numai pela capătul de sus, adică:
Într-un algoritm BT sunt precăutate toate soluţiile posibile. Fiecare soluţie se formează prin completarea soluţiei precedente cu încă un pas pe stivă. La fiecare nivel , vom încerca să punem valori din mulţimea soluţiilor care nu au fost încercate încă, pînă cînd nu obţinem o soluţie validă; în accest caaz “urcăm” cu încă un nivel în stivă şi reluăm încercările pe noul nivel.
Va apărea situaţia cînd la un moment dat, pe un nivel nu mai exista nici o valoare neincercată din mulţimea soluţiilor. În acest caz , vom faceeun pas înapoi , la nivelul anterior . Respectivul nivel a mai fost vizitat, dar l-am abandonat după ce am pus o valoare care a generat o soluţie validă, deci se poate să fi rămas aici valori neincercate. Dacă nici la acest nivel nu mai avem valori neîncercate, mai facem un pas înapoi ş.a..m..d.
Plecind de la nivelul 1 şi repetînd algoritmul pînă cînd pe toate nivele au fost încercate toate valorile din multimea soluţiilor, vvomobţine soluţii finale.
procedure bktr(p:integer); {algoritmul backtracking}
var val:integer; s:string;
begin {in variabila p trec pe rind toate valorile care pot fi incercate pe nivelul p al stivei}
for val:=v1 to v2 do
begin st[p]:=val; {se pune o noua valoare pe nivelul p al stivei}
if valid(p) then {daca solutia este valida}
if <soluţia este finală> then tipar (p) {daca solitia este
finala atunci ea se tipareste}
else bktr(p+1); {trece la nivelul urm[tor in stva}
end;
end;
Prob 1.
Să se genereze toate permutările din n elemente.
program permutari; {permutari de n elemente}
uses crt;
type vector=array[1..10] of integer;
var st:vector; {vectorul-stiva } n:integer;
procedure initializare; {initializeaza stiva siciteste n}
var i:integer;
begin write('n=');readln(n); for i:=1 to 10 do st[i]:=0;
end;
procedure tipar(p:integer); {tipareste o solutie memorata in vectorul st}
var i:integer;
begin for i:=1 to p do write(st[i]:4); writeln;
end;
function valid(p:integer):boolean;
{testeaza daca valoarea pusa pe nivelul p genereaza o solutie valida,
returnind true sau false}
var i:integer; posibil:boolean;
begin {st[p] nu trebuie sa se gaseasca pe nici un nivel anterior}
posibil:=true;
for i:=1 to p-1 do if st[p]=st[i] then posibil:=false;
valid:=posibil;
end;
procedure bktr(p:integer); {algoritmul backtracking}
var val:integer; s:string;
begin {in variabila p trec pe rind toate valorile care pot fi incercate pe nivelul p al stivei}
for val:=1 to n do
begin st[p]:=val; {se pune o noua valoare pe nivelul p al stivei}
if valid(p) then {daca solutia este valida}
if p=n then tipar (p) {daca solitia este finala atunci ea se tipareste}
else bktr(p+1); {trece la nivelul urm[tor in stva}
end;
end;
begin clrscr; initializare; bktr(1);{plecam de la nivelul 1 din stiva} readln;
end.
Prob. 2. {se considera n orase numerotate 1,2,3..n. Un comis-voiajor trebuie sa-si prezinte produsele in toate cele n orase, plecind dintr-un oras de start, trecind prin fiecare oras o singura data si revenind in orasul din care a plecat. Stiind ca intre unele orase exista drumuri, iar intre altele nu , sa se afiseze toate traseele posibile}
program comis_voiajor; uses crt; type vector=array[1..50] of integer; matrice=array[1..50,1..50] of 0..1;
var st:vector; {orasele sint numerotate de 1 la n;}
n,start:integer;{start- orasul de plecare} a:matrice; {a -matricea drumurilor}
procedure initializare;
var k,i,j:integer;
begin for k:=1 to 50 do st[i]:=0; write('n=');readln(n);
for i:=1 to n do a[i,i]:=0;
for i:=1 to n do
for j:=1 to n do
if i<j then
begin write('a[',i,',',j,']=');readln(a[i,j]);{completam cu 0 sau 1}
a[j,i]:=a[i,j];
end;
write('orasul de start');readln(start); st[1]:=start;
end;
procedure tipar(p:integer);
var i:integer;
begin for i:=1 to p do write(st[i]:4); writeln;
end;
function valid(p:integer):boolean;
var i:integer; posibil:boolean;
begin posibil:=true;
for i:=1 to p-1 do
if st[p]=st[i] then posibil:=false; {nu trebuie sa treaca de doua ori prin acelasi oras} {intre orasul dat si cel de pe nivelul anterior exista drum}
if a[st[p],st[p-1]]=0 then posibil:=false;
valid:=posibil;
end;
procedure bktr(p:integer);
var val:integer; s:string;
begin for val:=1 to n do
begin st[p]:=val;
if valid(p) then
if (p=n) and (a[st[p],start]=1)then tipar(p){daca a trecut prin toate orasele si intre ultimul oras si start exista drum}
else bktr(p+1);
end;
end;
begin clrscr; initializare;
bktr(2);{primul oras este orasul de start, deacea plecam de la nivelul 2 de pe stiva}
readln;
end.
Prob 3. {avind la dispozitie n tipuri de monede de valori v[1],v[2],...v[n] sa se tipareasca toate modalitatile de a plati o suma data s, daca se cunoaste numarul monedelor de fiecare tip}
program bani; uses crt; type vector=array[1..10] of integer; var n:integer;{tipurile monedelor sint codificate prin 1,2,3...n} v,nr,st:vector;{v[i]-valoarea monedei de tipul I, nr[i] - numarul monedelor de tipul i} s:integer;
procedure initializare;
var i:integer;
begin write('s='); readln(s); write('n=');readln(n);
for i:=1 to n do
begin write('v[',i,']=');readln(v[i]); write('nr[',i,']=');readln(nr[i]);
end;
for i:=1 to 10 do st[i]:=0;
end;
procedure tipar(p:integer);
var i:integer;
begin for i:=1 to p do write(st[i]:4); writeln;
end;
function sum(p:integer):integer;
var i,s:integer;
begin s:=0;
for i:=1 to p do s:=s+st[i]*v[i]; sum:=s;
end;
function valid(p:integer):boolean;
var i:integer; posibil:boolean;
begin posibil:=true; if sum(p)>s then posibil:=false; valid:=posibil;
end;
procedure bktr(p:integer);
var val:integer;
begin for val:=1 to nr[p] do
begin st[p]:=val;
if valid(p) then
if (p=n) and (sum(p)=s) then tipar(p)
else bktr(p+1);
end;
end;
begin clrscr; initializare; bktr(1); readln;
end.
Prob.4 {se dau n cuburi numerotate 1,2,3...n de laturi l[i] si culori c[i] ,i=1,2,...n(fiecare culoare e codificata printr-un caracter). Sa se afiseze toate turnurile care se pot forma din k cuburi din cele disponibile, astfel incit:
- laturile cuburilor sa fie in ordine crescatoare;
program cuburi;
uses crt;
type vector=array[1..10] of integer;
var n:integer;{cuburile sint numerotate prin 1,2,3...n}
l,st:vector; {l[i]-lungimea laturii cubului i}
c:array[1..10] of char; {c[i] - culoarea cubului i} k:integer;
procedure initializare;
var i:integer;
begin write('n=');readln(n); write('k='); readln(k);
for i:=1 to n do begin write('lungimea l[',i,']=');readln(l[i]);
write('culoarea c[',i,']=');readln(c[i]);
end;
for i:=1 to 10 do st[i]:=0;
end;
procedure tipar(p:integer);
var i:integer;
begin for i:=1 to p do write(st[i]:4); writeln;
end;
function valid(p:integer):boolean;
var i:integer; posibil:boolean;
begin posibil:=true;
for i:=1 to p-1 do if l[st[p]]<=l[st[i]] then posibil:=false;
if c[st[p]]=c[st[p-1]] then posibil:=false;
valid:=posibil;
end;
procedure bktr(p:integer);
var val:integer;
begin for val:=1 to n do
begin st[p]:=val;
if valid(p) then
if (p=k) then tipar(p)
else bktr(p+1);
end;
end;
begin clrscr; initializare; bktr(1); readln;
end.