De multe ori, în aplicaţii apar probleme în
care se cere găsirea unor soluţii de forma x=x1x2…xn, unde xi aparţine Ai,
i=1,…,n, în care x1...xn trebuie să îndeplinească anumite condiţii. Am putea să
generăm toate combinaţiile posibile de valori şi apoi să le alegem doar pe cele
convenabile.[...]
Rezolvând problema în acest mod, deci
generând toate elementele produsului cartezian A1xA2x...xAn şi verificând abia
apoi dacă fiecare combinaţie este o soluţie, eficienţa este scăzută.
Astfel, dacă de exemplu ne propunem să
generăm toate cuvintele formate cu literele a, b, c, aşa încât fiecare literă
să apară o singură dată, combinaţiile posibile sunt în număr de 27, dintre care
convin doar 6.
Tehnica Backtracking propune generarea soluţiei
prin completarea vectorului x în ordinea x1x2...xn şi are la bază un principiu
„de bun simţ”: dacă se constată că având o combinaţie parţială de forma
v1v2...vk-1 (unde v1, ..., vk-1 sunt valori deja fixate), dacă alegem pentru xk
o valoare vk şi combinaţia rezultată nu ne permite să ajungem la o soluţie, se
renunţă la această valoare şi se încearcă o alta (dintre cele netestate în
această etapă).
Într-adevăr, oricum am alege celelalte
valori, dacă una nu corespunde nu putem avea o soluţie.
