In capitolul 1 am prezentat rutina de backtracking clasica,nerecursiva.In acest capitol prezentam rutina de backtracking recursiva.Procedurile si functiile folosite sunt in general aceleasi,cu doua mici exceptii:
- SUCCESOR nu mai este procedura ci functie booleana ;
- rutina backtracking se transforma in procedura,care se apeleaza prin BACK(1)
Principiul de functionare al procedurii BACK,corespunzator unui nivel k este urmatorul:
- in situatia in care avem o solutie,o tiparim si revenim pe nivelul anterior
- in caz contrar se initializeaza nivelul si se cauta un succesor
- cand am gasit unul verificam daca este valid;procedura se autoapeleaza pentru (k+1) , in caz contrar urmand a se continua cautarea succesorului;
- daca nu avem succesor,se trece pe nivel inferior (k-1) prin iesirea din procedura BACK
Vom explica in continuare utilizarea backtrackingului recursiv prin generarea permutarilor:
program permutari;
type stiva=array[1 9] of integer;
var st:stiva;
ev:boolean;n,k:integer;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
function succesor(var st:stiva;k:integer):boolean;
begin
if st[k]<n then
begin
st[k]:=st[k]+1;
succesor:=true;
end
else succesor:=false;
end;
procedure valid(var ev:boolean;st:stiva;k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do
if st[i]=st[k] then ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=n+1);
end;
procedure tipar;
var i:integer;
begin
for i:=1 to n do writeln(st[i]);
writeln;
end;
procedure back(k:integer);
begin
if solutie (k) then tipar
else
begin
init(k,st);
while succesor(st,k) do
begin
valid(ev,st,k);
if ev then back(k+1);
end;
end;
end;
begin
write('n=');readln(n);
back(1);
end.
Desigur orice problema care admite rezolvare backtracking,poate fi rezolvata in acest mod.Insa,de multe ori,aceeasi problema se poate rezolva scriind mai putin,daca renuntam la standardizare.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.