Laborator

Algoritmul Backtracking

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:

• Solutia lor poate fi pusa sub forma unui vector S=x₁x₂.x_n cu x₁IA₁, x₂IA_2, ., x_nIA_n;

Multimile A₁, A₂, ., A_n sunt multimi finite, iar elementele lor se presupune ca se gasesc intr-o relatie de ordine bine stabilita;

• Nu se dispune de o alta metoda de rezolvare mai rapida.

La intalnirea unei astfel de probleme, daca nu se cunoaste aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A₁*A₂*.*A_n si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atit de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

Tehnica Backtracking are la baza un principiu extrem de simplu:

Se construieste solutia pas cu pas: x₁, x₂, ., x_n;

Daca se constata ca pentru o valoare aleasa nu avem cum sa ajungem la o solutie, se renunta la acea valoare si se reia cautarea din punctul in care am ramas.

Concret:

Se alege primul element x₁IA₁;

Presupunand generate elementele x₁, x₂, ., x_k apartinand multimilor A₁, A₂, ., A_n se alege (daca exista) x_k+1, primul element disponibil din multimea A_k+1, apar 2 posibilitati:

Nu s-a gasit un astfel de element, caz in care se reia cautarea considerand generate elementele x₁, x₂, ., x_k-1 iar aceasta se reia de la urmatorul element al multimii A_k, ramas netestat;

A fost gasit, caz in care se testeaza daca acesta indeplineste anumite conditii de continuare, aparand astfel doua posibilitati:

2.1) le indeplineste, caz in care se testeaza daca s-a ajuns la solutie si apar, din nou, doua posibilitati:

2.1.1) s-a ajuns la solutie, se tipareste solutia si se reia algoritmul considerand generate elementele x₁, x₂, ., x_k (se cauta in continuare un alt element al multimii A_k+1 ramas netestat).

2.1.2) nu s-a ajuns la o solutie, caz in care se reia algoritmul considerand generate elementele x₁, x₂, ., x_k+1 si se cauta un prim element x_k+2IA_k+2

2.2) nu le indeplineste, caz in care se reia algoritmul considerand generate elementele x₁, x₂, ., x_k, iar elementul x_k+1 se cauta intre elementele multimii A_k+1 ramase netestate.

Algoritmul se termina atunci cand nu mai exista nici un element x₁IA₁ netestat.

Tehnica Backtracking are a rezultat obtinerea tuturor solutiilor problemei. In cazul in care se cere o singura solutie se poate forta oprirea atunci cand solutia a fost gasita.

Pentru usurarea intelegerii metodei, vom prezenta o rutina unica, aplicabila oricarei probleme, rutina care utilizeaza notiunea de stiva. Rutina va apela proceduri si functii care au intotdeauna acelasi nume si parametrii si care din punct de vedere al metodei, realizeaza acelasi lucru. Sarcina programatorului este de a scrie explicit, pentru fiecare problema in parte, procedurile si functiile apelate in rutina backtracking. Evident, o astfel de abordare conduce la programe lungi. Nimeni nu ne opreste, ca dupa intelegerea metodei, sa scriem programe scurte, specifice fiecarei probleme in parte.

Se va folosii o procedura init_nivel care va initializa nivelul curent din stiva. Ea va avea doi parametrii: o stiva st si nivelul curent din stiva, k. Gasirea urmatorului element al multimii A_k se face cu ajutorul procedurii succesor(st,k,as). Parametrul as (am succesor) este o variabila booleana care va avea valoarea true daca s-a gasit un succesor si false in caz contrar. Odata ales un element trebuie vazut daca acesta indeplineste conditiile problemei. Acest lucru se va testa in procedura valid(st,k,ev). Testul daca s-a ajuns sau nu la o solutie finala se face cu ajutorul functiei solutie, iar o solutie se afiseaza cu ajutorul procedurii tip_sol.

Rutina backtracking este urmatoarea:

k:=1;

init_nivel(st,k);

while k>0 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

Probleme:

1. Generarea permutarilor:

Se citeste un numar natural n. Sa se genereze toate permutarile multimii .

uses crt;

type stiva=array[1..10] of integer;

var st:stiva;

n,i,k:integer;

as,ev:boolean;

procedure init_nivel(var st:stiva;k:integer);

begin

st[k]:=0;

end;

procedure succesor(var st:stiva;k:integer; var as:boolean);

begin

if st[k]<n then

begin

as:=true;

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

end

else

as:=false;

end;

procedure valid(st:stiva; k:integer; var ev:boolean);

begin

ev:=true;

for i:=1 to k-1 do

if st[i]=st[k] then

ev:=false;

end;

function solutie(st:stiva; k:integer):boolean;

begin

if k=n then

solutie:=true

else

solutie:=false;

end;

procedure tipar;

begin

for i:=1 to n do

write(st[i],' ');

writeln;

end;

begin

clrscr;

write('n=');

read(n);

k:=1;

init_nivel(st,k);

while k>0 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

readln;

end.

2. Generarea aranjamentelor

Se citesc n si p numere naturale. Se cere sa se genereze toate submultimile multimii de p elemente. Doua multimi cu aceleasi elemente, la care ordinea acestora difera, sunt considerate distincte.

Din analiza problemei rezulta urmatoarele:

Stiva are inaltimea p

Fiecare nivel ia valori intre 1 si n

Elementele plasate pe diferite niveluri trebuie sa fie distincte.

uses crt;

type stiva=array[1..10] of integer;

var st:stiva;

n,p,i,k:integer;

as,ev:boolean;

procedure init_nivel(var st:stiva;k:integer);

begin

st[k]:=0;

end;

procedure succesor(var st:stiva;k:integer; var as:boolean);

begin

if st[k]<n then

begin

as:=true;

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

end

else

as:=false;

end;

procedure valid(st:stiva; k:integer; var ev:boolean);

begin

ev:=true;

for i:=1 to k-1 do

if st[i]=st[k] then

ev:=false;

end;

function solutie(st:stiva; k:integer):boolean;

begin

if k=p then

solutie:=true

else

solutie:=false;

end;

procedure tipar;

begin

for i:=1 to p do

write(st[i],' ');

writeln;

end;

begin

clrscr;

write('n=');

read(n);

writ('p=');

realn(p);

k:=1;

init_nivel(st,k);

while k>0 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

readln;

end.

Generarea combinarilor:

Se citesc n, p numere naturale, cu n>=p. Se cere sa se genereze toate submultimile cu p elemente al submultimii . Doua submultimi se considera egale daca si numai daca au aceleasi elemente, indiferent de ordinea in care ele apar.

Pentru rezolvarea problemei trebuie tinut cont de urmatoarele:

Stiva are inaltimea p

Elementele aflate pe nivele diferite ale stivei trebuie sa fie distincte

Nivelul k al stivei ia valori intre 1 si n-p+k

Este necesar ca pe nivelul k sa se afle o valoare mai mare decat pe nivelul k-1.

uses crt;

type stiva=array[1..10] of integer;

var st:stiva;

n,p,i,k:integer;

as,ev:boolean;

procedure init_nivel(var st:stiva;k:integer);

begin

st[k]:=0;

end;

procedure succesor(var st:stiva;k:integer; var as:boolean);

begin

if st[k]<n-p+k then

begin

as:=true;

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

end

else

as:=false;

end;

procedure valid(st:stiva; k:integer; var ev:boolean);

begin

ev:=true;

for i:=1 to k-1 do

if st[i]=st[k] then

ev:=false;

if k>1 then

if st[k]<st[k-1] then

ev:=false;

end;

function solutie(st:stiva; k:integer):boolean;

begin

if k=p then

solutie:=true

else

solutie:=false;

end;

procedure tipar;

begin

for i:=1 to p do

write(st[i],' ');

writeln;

end;

begin

clrscr;

write('n=');

read(n);

writ('p=');

realn(p);

k:=1;

init_nivel(st,k);

while k>0 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

readln;

end.

Problema colorarii hatilor:

Fiind data o harta cu n tari, se cer toate posibilitatile de colorare a hartii, utilizand cel mult 4 colori, astfel incat doua tari cu frontiera comuna sa fie colorate diferit. Harta este furnizata programului cu ajutorul unei matrici A_m,n

Matricea A este simetrica.

uses crt;

type stiva=array[1..10] of integer;

matrice=array[1..10,1..10] of integer;

var st:stiva;

n,p,i,k:integer;

as,ev:boolean;

a:matrice;

procedure init_nivel(var st:stiva;k:integer);

begin

st[k]:=0;

end;

procedure succesor(var st:stiva;k:integer; var as:boolean);

begin

if st[k]<4 then

begin

as:=true;

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

end

else

as:=false;

end;

procedure valid(st:stiva; k:integer; var ev:boolean);

begin

ev:=true;

for i:=1 to k-1 do

if (st[i]=st[k]) and (a[i,k]=1) then

ev:=false;

end;

function solutie(st:stiva; k:integer):boolean;

begin

if k=n then

solutie:=true

else

solutie:=false;

end;

procedure tipar;

begin

for i:=1 to n do

write(st[i],' ');

writeln;

end;

begin

clrscr;

write('n=');

read(n);

for i:=1 to n do

a[i,i]:=1;

for i:=1 to n do

for j:=i+1 to n do

begin

readln(a[i,j]);

a[j,i]:=a[i,j];

end;

k:=1;

init_nivel(st,k);

while k>0 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

readln;

end.

Problema comis-voiajorului:

Un comis voiajor trebuie sa viziteze un numar de n orase. Initial acesta se afla intr-unul dintre ele, notat 1. Comis voiajorul doreste sa nu treaca de doua ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Cunoscand legaturile existente intre orase, se cere sa se tipareasca toate drumurile posibile pe care le poate efectua comis-voiajorul.

Legaturile dintre orase sunt date de matricea A_m,n

Matricea A este simetrica.

Pentru rezolvarea problemei vom folosii o stiva st. La baza stivei (nivelul 1) se incarca numarul 1. Algoritmul continua In acest mod pana cand se ajunge din nou la nivelul 1. Un succesor intre 2 si n, aflat pe nivelul k al stivei, este considerat valid daca sunt indeplinite urmatoarele conditii:

Nu s-a mai trecut prin orasul simbolizat de succesor, deci acesta nu se regaseste in stiva

Exista drum intre orasul aflat pe nivelul k-1 si cel aflat pe nivelul k

Daca succesorul se gaseste pe nivelul n, sa existe drum aflat intre el si orasul 1.

uses crt;

type stiva=array[1..10] of integer;

var st:stiva;

n,p,i,k:integer;

as,ev:boolean;

procedure init_nivel(var st:stiva;k:integer);

begin

st[k]:=1;

end;

procedure succesor(var st:stiva;k:integer; var as:boolean);

begin

if st[k]<n then

begin

as:=true;

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

end

else

as:=false;

end;

procedure valid(st:stiva; k:integer; var ev:boolean);

begin

ev:=true;

if a[st[k-1],st[k]]=0 then

ev:=false

else

for i:=1 to k-1 do

if (st[i]=st[k]) then

ev:=false;

if (k=n) and (a[1,st[k]]=0) then

ev:=false;

end;

function solutie(st:stiva; k:integer):boolean;

begin

if k=n then

solutie:=true

else

solutie:=false;

end;

procedure tipar;

begin

for i:=1 to n do

write(st[i],' ');

writeln;

end;

begin

clrscr;

write('n=');

read(n);

for i:=1 to n do

for j:=1 to i-1 do

begin

readln(a[i,j]);

a[j,i]:=a[i,j];

end;

st[1]:=1;

k:=2;

init_nivel(st,k);

while k>1 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

readln;

end.

Partitiile unui numar natural:

Se citeste un numar natural n. Se cere sa se tipareasca toate modurile de descompunere a sa ca suma de numere naturale.

Ex: n=4. Avem: 1111, 112, 121, 13, 211, 22, 31, 4.

Ordinea numerelor din suma este importanta. Astfel, se tipareste 112 dar si 121, 211.

Pentru rezolvare, vom observa ca nivelul 1 al stivei ia valori intre 1 si n, nivelul 2 ia valori intre 1 si n-1, in general, nivelul k ia valori intre 1 si n-k+1 (succesor). O solutie partiala este valida daca suma elementelor pe care le contine este mai mica sau egala cu n (valid) si am obtinut o solutie cand aceasta suma este egala cu n.

uses crt;

type stiva=array[1..10] of integer;

var st:stiva;

n,p,i,k:integer;

as,ev:boolean;

procedure init_nivel(var st:stiva;k:integer);

begin

st[k]:=0;

end;

procedure succesor(var st:stiva;k:integer; var as:boolean);

begin

if st[k]<n-k+1 then

begin

as:=true;

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

end

else

as:=false;

end;

procedure valid(st:stiva; k:integer; var ev:boolean);

begin

s:=0;

for i:=1 to k do

s:=s+st[i];

if s<=n then

ev:=true

else

ev:=false;

end;

function solutie(st:stiva; k:integer):boolean;

begin

if s=n then

solutie:=true

else

solutie:=false;

end;

procedure tipar;

begin

for i:=1 to p do

write(st[i],' ');

writeln;

end;

begin

clrscr;

write('n=');

read(n);

k:=1;

init_nivel(st,k);

while k>0 do

begin

repeat

succesor(st,k,as);

valid(st,k,ev);

until ((as=true) and (ev=true)) or (as=false);

if as=true then

if solutie(st,k) then tipar

else

begin

k:=k+1;

init_nivel(st,k);

end

else

k:=k-1;

end;

end.

Tema:

Sa se genereze toate aranjamentele de n luate cate p cu proprietatea ca diferenta in modul dintre oricare doua numere consecutive este cel putin egala cu o valoare v citita de la tastatura.

Sa se genereze toate permutarile lexicografice ale unui cuvant citit de la tastatura.

Sa se genereze toate partitiile multimii

Ex. : Pentru n=3 se obtin urmatoarele partitii ale multimii

Se citeste de la tastatura un numar natural n. Sa se genereze toate numerele intregi a caror reprezentare in baza 2 au acelasi numar de cifre 0 (semnificative) si respectiv si respectiv 1 ca si reprezentarea in baza 2 a numarului n.

Ex.: Pentru n=53 se vor afisa numerele 39, 43, 45, 46, 51, 53, 54, 57, 58, 60.