METODA BACKTRACKING
Aceasta tehnica se foloseste
in general la rezolvarea problemelor care indeplinesc urmatoarele conditii:
Ø Solutia lor poate fi pusa sub
forma unui vector S= x1, x2, …, xn cu x1 apartine lui A1, x2 apartine lui A2 …
Ø Multimile A1, A2, …, A
n sunt multimi finite, iar elementele lor se
considera intr-o relatie de ordine bine stabilita.
Ø Nu se dispune de o alta metoda
de rezolvare, mai rapida.
Obs: In multe din probleme multimile A1, A2, …, An
coincid.
La intalnirea unei astfel de probleme, daca nu
cunoastem aceasta tehnica, suntem tentati sa generam toate elementele
produsului cartezian A1* A2* …* An si fiecare
element sa fie testat daca este solutie.
Ex. Consideram generarea
permutarilor multimii {1, 2, 3, …, n} unde n este un
numar natural.
In cazul de fata A1
=A2 =… = An = {1, 2, 3, …, n} = A
(notatie). Trebuie determinata o multime x1, x2, …, x
n cu propietatea ca x1
, x2, …, xn apartin lui A.
Elementul 1 * 1 * … * 1 este un element al produsului
cartezian A * A *… * A dar nu este o permutare a
multimii A fiind ca nu respecta
propietatea unei pertutari si anume ca toate elementele sunt distincte intre
ele. Deci daca s-a ales un element i care
apartine lui A atunci celalat element va
trebui sa fie diferit de i.
Elementele vectorului solutiei
se vor completa pe rand. Astfel x2 va primi o valoare doar dupa ce x1
a primit o valoare si va trebui sa fie
diferita de aceasta.
In general xk+1 va primi o valoare daca xk
a primit o valoare si daca x1
<>
x2 <> … <>xk <> xk+1
x1 va primi valoarea primului element al multimii
A. Se vor verifica conditiile
de continuare adica in sirul x al
solutiilor sa nu fie doua elemente egale, dar fiind ca sirul contine un singur
element acestea sunt indeplinite. x2 va primi la randul sau valoarea primului
element din A numai daca sunt indeplinite conditiile
de continuare. Deoarece atat x1 are deja valoarea primului element al multimii
A aceste conditii nu sunt indeplinite si deci va trebui
sa se aleaga o alta valoare pentru x2 si anume urmatorul element din A.
Daca xk
a primit o valoare atunci xk+1 va primi primul element din A daca
sunt indeplinite conditiile de continuare.
Daca k = n si sunt
indeplinite conditiile de continuare atunci
s-a determinat o solutie si se va afisa solutia
Daca primul element din A se afla
deja printre elementele x1, x2, …, xk
atunci se va alege urmatorul
element din A.
Daca in A nu se
mai afla nici un element care sa se aleaga si sa respecte conditiile
de continuare atunci se revine la xk
si se alege urmatorul
element din A de dupa elementul xk
Algoritmul
Backtraking este:
K=1
X1= 1
Cat timp k>0 executa
cat timp k <
n si sunt indeplinite Conditiile de
continuare executa
k =
k+1
xk = 1
Sf. Cat timp
Daca k=n si sunt indeplinite
Conditiile de continuare atunci
Tipareste Solutia – vectorul X
Sf Daca
Cat timp Nu mai sunt Elemente in A de ales executa
k = k –1
Sf Cat timp
Daca k >0 atunci
x
k = xk + 1
Sf Daca
Sf Cat timp
