PREZENTAREA METODEI ŞI APLICAŢII

Metoda backtracking

Prezentarea metodei

Se aplică pentru rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:

soluţia se poate reprezenta sub forma unui vector X=(x[1],x[2],...,x[n]) S[1]xS[2]x...xS[n]. Mulţimea S=S[1]xS[2]x...xS[n] se numeşte spaţiul soluţiilor posibile

mulţimile S1,S2,...,Sn sunt mulţimi finite, au un număr cunoscut de elemente, iar elementele lor se consideră că se află într-o relaţie de ordine bine stabilită;

nu se dispune de o altă metodă de rezolvare mai rapidă

Prezentarea metodei

Între componentele vectorului X sunt date mai multe

condiţii interne, care depind de natura problemei date. Soluţiile posibile pentru care sunt verificate condiţiile de interne le numim soluţii rezultat. În unele probleme se cere alegerea dintre soluţiile rezultat a soluţiei optime după un anumit criteriu.Soluţie parţială = o soluţie pentru care sunt

indeplinite condiţiile de continuare. Condiţiile de continuare se obţin din condiţiile interne aplicate pentru o soluţie parţială.

Construirea soluţiei

La fiecare pas se alege o valoare pentru elementulcurent x[k] (soluţia se construieşte progresiv).Elementului x[k] i se atribuie următoarea valoare dinmulţimea S[k] (dacă există). Pentru soluţia parţială obţinută (x[1],x[2],...,x[k]) sunt verificate condiţiile de continuare. Apar astfel două posibilităţi:1) Condiţia de continuare este adevărată: în acest caztestăm dacă am completat toate componentele soluţiei (k=n+1) . În caz afirmativ, am obţinut o soluţie pe care o reţinem. Dacă k<n incrementăm k cu 1 (avansăm la nivelul următor) şi iniţializăm x[k] cu o valoare anterioară primei valori din mulţimea S[k].

Construirea soluţiei

2) Dacă condiţia de continuare este falsă, aleg pentru x[k] următoarea valoare posibilă din S[k] şi verific din nou condiţiile de continuare. Dacă nu pot face altă alegere, revin şi caut altă valoare pentru x[k-1].

Din modul de construire a soluţiei rezultă şi numele metodei backtracking: metoda avansului cu reveniri.

Termenul „backtrack” a fost inventat de matematicianul american D.H. Lehmer în anii 1950.

Aplicarea metodei

Pentru o problemă particulară care se rezolvă prin

metoda backtracking trebuie precizat:(1) spaţiul soluţiilor, adică mulţimile S[1], S[2], ..., S[n]. Nu este necesar ca aceste mulţimi să aibă acelaşi număr de elemente.(2) mai trebuie precizate condiţiile de continuare.Alegerea acestor condiţii influenţează decisiv eficienţa metodei. Condiţiile de continuare se obţin din condiţiile interne aplicate pentru o soluţie parţială.

Procedura backtracking iterativă

procedure backtracking; begin k:=1; x[k]:=init(k); while (k>0) do begin while {exista o valoare netestata in Sk} do begin x[k]:=urmator(k); if continuare(x[1],x[2],...,x[k]) then

if (k=n) then solutie(x[1],x[2],...,x[n]) else begin {avans la nivelul k+1} k:=k+1; x[k]:=init(k); end end; k:=k-1; {revenire la nivelul anterior} end end;

Procedura backtracking recursivă

procedure back(k: integer); begin x[k]:=init(k); while are_succesor(x[k]) do if continuare(k) then if este_solutie(k) then solutie else back(k+1) end; 

* O variantă recursivă în cazul în care toate mulţimile S[k] sunt egale, S[k]={1,2,…,n} k= 1,n este următoarea:  procedure back(k: integer); var i: integer; begin if este_solutie(k) then solutie else for i:=1 to n do begin x[k]:=i; if continuare(k) then else back(k+1) end end;

Generarea permutărilor

Se citeşte un număr natural n. Să se genereze toate permutările mulţimii {1,2,…,n}.

De exemplu, pentru n=3, permutările mulţimii {1,2,3} sunt:

123, 132, 213, 231, 312, 321Se observă că fiecare componentă a soluţiei

poate lua valorile 1,2,...,n=3Condiţiile interne: ultima valoare adăugată

x[k] să fie diferită de valorile anterioare x[1],x[2],…,x[k]

Programul de generare a permutărilor

type vector=array[1..20] of integer;var x:vector; n,nr:integer;procedure solutie;var i:integer;begin inc(nr); write(nr,':'); for i:=1 to n do write(x[i],' '); writeln; end;function continuare(k:integer):boolean;var i:integer;begin continuare:=true; for i:=1 to k-1 do if x[i]=x[k] then continuare:=false;end;

procedure back(k:integer);var i:integer;begin if k=n+1 then solutie else for i:=1 to n do begin x[k]:=i; if continuare(k) then back(k+1); end;end;

begin n:=5; back(1);writeln(nr,’ permutari’ readln;end.

Exerciţii

Utilizând metoda backtracking se generează permutările de 5 elemente, în ordine lexicografică. Se consideră permutarea p=(2,1,3,4,5).

a) Care sunt, în ordine, următoarele trei permutări generate de algoritm?

b) Care sunt cele trei permutări generate înaintea permutării p?

Întrebări grilă

1. Dacă pentru nivelul k oarecare al vectorului soluţie am verificat toate valorile posibile:

a) algoritmul se încheieb) se revine pe nivelul anteriorc) se trece pe nivelul următor

2. În ce condiţii se trece de la componenta k la componenta k+1?a) după ce am găsit o valoare convenabilă pentru componenta kb) dacă nici o valoare pentru componenta k nu convinec) după ce am testat toate valorile posibile pentru

componenta k

Întrebări grilă

3. Algoritmul se încheie dacă:a) s-au testat toate valorile posibile pentru primul

nivelb) s-au testat toate valorile posibile pentru ultimul

nivelc) pe un nivel oarecare k, nu am găsit nicio valoare

care să verifice condiţiile de continuare4. După găsirea unei soluţii, pasul următor este:

a) se revine pe nivelul anteriorb) se rămâne pe acelaşi nivel, testându-se

următoarea valoare disponibilăc) se încheie algoritmul