O soluţie are forma unui vector
Mulţimile sunt finite având elemente aflate într-o relaţie
de ordine bine stabilită
Se caută soluţia/soluţiile valide în spaţiul tuturor soluţiilor
Nu există altă rezolvare cu timp de rulare mai rapid
, ,..., / , ,..., , 1,... Sv
x1 x2 xn x1 A1 x2 A2 xn An v
A A An
, ,..., 1 2
Backtracking. Observații
Mulţimile pot fi identice
pot fi şi vectori
Numărul de elemente ale soluţiei poate fi sau
nu cunoscut; depinde de fiecare problemă
Dacă se caută o singură soluţie, algoritmul se
opreşte forţat pentru a economisi timp
Ai
/ i 1, n
xi
/ i 1, n
S
Backtracking. Analiza complexității
Produs cartezian: Se doreşte spargerea unui cifru
format din 4 cifre. Se presupune că există o funcție
care primeşte ca parametru o combinaţie de 4 cifre
şi returnează 0 (combinație incorectă) sau 1
(combinație corectă).
Generând produsul cartezian se
baleiază spaţiul tuturor soluţiilor:
Rezolvare : adunare cu 1 în baza 10
4, / 1, / {0..9}, 1,4
, ,..., / , ,..., , 1,...
1 2 3 4
( )
1 2 1 1 2 2
n A A i n S x x x x x j
S x x x x A x A x A v
i v j
not
v n n n
Sv
A A A A
(0,0,0,9)... (0,0,9,9)...
(0,0,0,0) (0,0,0,1) (0,0,0,2)...
10 100
1 2 3
S S
S S S
Backtracking. Analiza complexității
Permutări: Se doreşte generarea tuturor permutărilor de 4 elemente.
Se poate folosi produsul cartezian
Câte soluţii posibile? Câte valide?
4, / 1, / {1..4}, 1,4 1 2 3 4
( )
n A Ai
i n Sv
x x x x x j j
not
(1,1,2,1) (1,1,2,2) (1,1,2,3)...
(1,1,1,1) (1,1,1,2) (1,1,1,3) (1,1,1,4)
5 6 7
1 2 3 4
S S S
S S S S
Backtracking. Cu alte cuvinte
(Backtracking == Brute-force) ?
Se generează toţi candidaţii parţiali la “titlul” de soluţie
Candidaţii la soluţie se construiesc pe vectori
unidimensionali/bidimensionali
Generarea candidaţiilor se face în paşi succesivi (înainte şi inapoi)
După fiecare pas se poate face o validare pentru reducerea numărului
căutărilor în spaţiul soluţiilor
Când s-a ajuns la o anumită dimensiune a vectorului, se verifică dacă
candidatul parţial (vectorul) este sau nu o soluţie
Se alege soluţia/soluţiile din candidaţii parţiali după criterii impuse de
problemă
Backtracking. Permutări.
Generare permutări mulţime de 4 elemente.
proiectare algoritm generare permutări pornind de la un
exemplu
Pas 1: Se utilizează un vector v cu 4 elemente.
v[i] : elementul de pe poziţia i din permutare
v[3]=2 → elementul de pe poziţia 3 din permutare este 2
3 1 2 4
1
v:
index : 2 3 4
Backtracking. Permutări.
Pas 2: Se completeză vectorul v de la stânga la dreapta cu
valori succesive de la 1 la n. dacă s-a ajuns cu completarea până la un index k şi nu
există duplicate până la indexul respectiv, se continuă
completarea cu indexul k+1 (k<n).
dacă s-a ajuns cu completarea până la un index k şi nu
se mai poate completa (s-a ajuns la valoarea n) şi există
duplicate până la indexul respectiv, se continuă
completarea cu indexul k-1(k>0).
1
v:
k: 2 3 4
1
1
v:
k: 2 3 4
Backtracking. Permutări.
1 1
1
v:
k: 2 3 4
1 2
1
v:
k: 2 3 4
1 2 1
1
v:
k: 2 3 4
1 2 2
1
v:
k: 2 3 4
1 2 3
1
v:
k: 2 3 4
1 2 3 1
1
v:
k: 2 3 4
Backtracking. Permutări.
1 2 3 2
1
v:
k: 2 3 4
1 2 3 3
1
v:
k: 2 3 4
1 2 3 4
1
v:
k: 2 3 4
1 2 4
1
v:
k: 2 3 4
1 2 4 1
1
v:
k: 2 3 4
... 1 2 4 3
1
v:
k: 2 3 4
SOL
SOL
Backtracking. Permutări.
1 2 4 4
1
v:
k: 2 3 4
1 3
1
v:
k: 2 3 4
1 3 1
1
v:
k: 2 3 4
1 3 2
1
v:
k: 2 3 4
1 3 2 1
1
v:
k: 2 3 4
... 1 3 2 4
1
v:
k: 2 3 4
SOL
Backtracking. Permutări.
Pas 3: Se aleg soluţiile dintre candidaţi. Condiţia este ca toate
elementele vectorului să fie completate şi diferite între ele.
Pas 4: Se repetă algoritmul până când nu se mai îndeplineşte
condiţia: indexul k al vectorului >0 (stiva este goală).
4 3 4
1
v:
k: 2 3 4
4 4
1
v:
k: 2 3 4
4
1
v:
k: 2 3 4
1
v:
k: 2 3 4
Backtracking. Preambul implementare
Pentru generarea tuturor soluţiilor se foloseşte o structură de date de tip
stivă, v. Vârful stivei se notează cu k
Algoritmul ciclează, adăugând/modificând/ştergând valori din vârful stivei
iniţializează valoare element din vârful stivei – funcţia Init(k)
modificare valoare element din vârful stivei – funcţia Successor(k)
validarea elementului din vârful stivei – funcţia Valid(k)
dacă elementul din vârful stivei este valid, putem avea un cantidat la soluţie
- funcţia Solution(k), iar în caz favorabil, afişare - Print(k)
3 variante de poziţionare în stivă :
Nu se modifică poziţia – k rămâne neschimbat
Se urmăreşte adăugarea unui nou element în stivă – k++
Se coboară o poziţie în stivă pentru că elementul curent din vârf nu mai
satisface condiţiile problemei– k--
Backtracking. Implementare
Funcția Init
void Init(int k){ // k – vârful stivei
v[k]=0; //iniţializează/resetează, valoarea din
// vârful stivei