Metoda "backtracking"

Metoda "backtracking", este una dintre metodele cele mai des folosite pentru cautarea solutiei unei probleme atunci cand multimea solutiilor posibile este cunoscuta sau poate fi generata. O verificare succesiva printr-o parcurgere dupa o metoda oarecare a multimii solutiilor posibile este costisitoare ca timp de executie. Ordinul de complexitate al unui astfel de algoritm este exponential. Se impune a se evita generarea si verificarea tuturor solutiilor posibile. Acest lucru este realizat prin metoda "backtracking".

Problema Se considera n multimi nevide si finite A₁, A₂, A_n si m₁, m₂, m_n, cardinalele acestor multimi.

Consideram o functie f: A₁ x A₂ x x A_n R O solutie a problemei este un n-uplu de forma x = (x₁, x₂, x_n)I A₁ x A₂ x x A_n care optimizeaza functia f

Solutie. Multimea finita A = A₁ x A₂ x x A_n se numeste spatiul solutiilor posibile ale problemei. Conditia de optim pe care trebuie sa o indeplineasca o solutie este exprimata printr-un set de relatii intre componentele vectorului x, relatii exprimate prin forma functiei f. O solutie posibila, care optimizeaza functia f, adica satisface conditiile interne ale problemei se numeste solutie rezultat, sau mai simplu, solutie a problemei.

Construirea unei solutii consta in determinarea componentelor vectorului x. La un moment dat se va alege un element dintr-o multime, pe care convenim sa o numim multimea curenta si, presupunand ca elementele fiecarei multimi A_i (1 i n) sunt ordonate, elementul care se adauga la vectorul x il vom numi elementul curent.

Urmatorul algoritm (reprezentat in limbaj natural) descrie esenta metodei backtracking:

Este evident ca intre conditiile interne (de optim) si conditiile de continuare exista o stransa legatura, sincronizarea acestora avand ca efect o importanta reducere a numarului de operatii.

O sinteza a metodei backtracking scoate in evidenta patru etape principale:

- etapa in care unei componente a vectorului solutie i se atribuie o valoare din multimea corespunzatoare acesteia, urmata de trecerea la multimea (componenta) urmatoare;

- etapa in care atribuirea unei valori pentru o componenta a vectorului solutie se soldeaza cu un esec, situatie care se incerca a fi depasita prin trecerea la urmatorul element din multimea (curenta) corespunzatoare componentei;

- etapa in care elementele multimii curente au fost epuizate, situatie generata de o alegere anterioara nepotrivita, caz in care se impune o revenire la multimea anterioara, revenire care poate incheia nefericit (fara gasirea unei solutii) intreg procesul de cautare a solutiilor;

- etapa revenirii in procesul de cautare a unei noi solutii dupa obtinerea unei solutii, etapa care se realizeaza prin trecerea la elementul urmator din ultima multime.

Algoritmul prezentat mai sus conduce la obtinerea unei solutii (daca macar o solutie exista). De fiecare data, pornind de la ultima solutie obtinuta pot fi determinate toate solutiile optime.

Procedura pseudocod de mai jos realizeaza acest lucru, pornind de la premiza ca cele n multimi sunt cunoscute.

Vom nota cu a_ik al k-lea element din multimea A_i si vom conveni ca valoarea variabilei k este proprie fiecarei valori a variabilei i, adica exista cate o variabila k pentru fiecare valoare a variabilei i, notata tot cu k, in loc de k_i

procedura backtracking

i = 1

k = 0 - k = 0 are semnificatia k₁ = 0

repeta

repeta

k = k + 1

daca ( k > m_k ) atunci

k = 0 - k = 0 are semnificatia k_i = 0

i = i - 1 - se realizeaza 'intoarcerea'

altfel

x_i = a_ik

daca (x₁, x₂, x_i) conduce la optim atunci

i = i + 1 - se verifica conditia de continuare

sfdaca

sfdaca

pana cand (i > n sau i = 0)

daca ( i > n ) atunci

afisare solutie

i = n

sfdaca

pana cand ( i = 0 )

sfarsit

Exemplul pe care-l vom prezenta evidentiaza ideea de "continuare si intoarcere" care sta la baza acestei metode.

Exemplu (Generarea permutarilor de n elemente). Sa consideram multimea A = , n>0. Sa se determine toate n-uplele de elemente distincte din A

Solutie. Aceasta problema reprezinta un caz particular a problemei generale prezentate anterior, caz in care toate cele n multimi sunt egale cu multimea A. Vom aplica metoda backtracking considerand functia de optim exprimata prin conditia: elementele vectorului solutie sa fie distincte. Programul Pascal care implementeaza algoritmul este urmatorul:

program generare_permutari;

var n,i : byte;

x : array [1..10] of 0..10;

function continuare(k:byte):boolean;

var i : byte;

t : boolean;

begin

t := true;

i :=1;

while (i<k) and t do

if ( x[ i] > x[k]) then

t := false

else

i := i + 1;

bun := t;

end;

begin

write (' Introduceti n : ');

readln(n);

for i := 1 to n do

x [i] := 0;

i := 1;

repeat

repeat

x [i] := x[i] + 1;

if ( x[i] >n ) then

begin

x [i] := 0;

i := i-1;

end

else

if ( continuare(i) ) then

i := i + 1;

until (i>n) or (i = 0);

if ( i > n ) then

begin

write (' Solutie : (');

for i := 1 to n do

write (x[i] ,',');

writeln (chr(8),')');

i := n;

end;

until ( i = 0);

readln

end.

Vom pune in evidenta secventele de program care implementeaza cele patru etape prezentate anterior:

- atribuirea unei valori, din multimea corespunzatoare acesteia, pentru o componenta a vectorului solutie:

repeat

x [i] := x[i] + 1;

if ( continuare(i) ) then

i := i + 1;

until (i > n) or (i = 0);

urmata de trecerea la multimea (componenta) urmatoare, sau etapa in care atribuirea unei valori pentru o componenta a vectorului solutie se soldeaza cu un esec, situatie care se incearca a fi depasita prin trecerea la urmatorul element din multimea (curenta) corespunzatoare componentei;

- etapa in care elementele multimii curente au fost epuizate:

if ( x[i] >n ) then

begin

x[i] := 0;

i := i - 1;

end

else

caz in care se impune o revenire la multimea anterioara, revenire care poate incheia (fara gasirea unei solutii), intreg procesul de cautare a solutiilor:

repeat

until (i > n) or (i = 0);

- etapa revenirii in procesul de cautare a unei noi solutii dupa obtinerea unei solutii:

repeat

repeat

until (i>n) or ..

if ( i>n ) then

begin

i := n;

end;

until i = 0;

etapa care se realizeaza prin trecerea la elementul urmator din ultima multime.

Programul implementeaza in esenta procedura backtracking, apeland functia continuare(k), care verifica conditiile interne ale componentelor solutiei.