1. se aplică numai atunci cînd nu există o altă cale de rezolvare a problemei propuse, deoarece timpul de execuție este de ordin exponențial (crește exponențial o dată cu dimensiunea datelor de intrare ), rezolvarea problemei, chiar pe un calculator rapid, poate dura foarte mult.
2. Observații
2.1. nu pentru toate problemele n este cunoscut de la început;
2.2. x1,x2,...,xn pot fi la rîndul său vectori;
2.3. în multe probleme, mulțimile A1, A2,..., An
3. Conditii necesare pentru rezolvarea problemelor
3.1. soluția problemelor poate fi pusă sub forma unui vector S= x1,x2,...,xn cu x1ÎA1, x2ÎA2,...,XnÎAn;
3.2. mulțimile A1,A2,...,An sunt mulțimi finite, iar elementele lor se consideră că se află într-o ordine bine stabilită;
3.3. nu se dispune de o altă metodă de rezolvare, mai rapidă.
4. Exemplu:
5. Generarea permutărilor 123 132 213 231 312 321 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 : Pentru această problemă A1=A2=A3=(1,2,3) în cazul permutării 213 este scrisă sub forma unui vector, unde 2ÎA1, 1ÎA2 și 3ÎA3
6. Deosebirea de Metoda Greedy
6.1. Este o metodă ”constructivă”, la fel ca Metoda Greedy, dar spre deosebire de aceasta, are proprietatea de a reveni asupar valorilor nealese.
7. Tehnica Backtracking are la baza principiul:
8. Daca in procesul de generare al unui vector solutie S=x1*x2....*xn pentru componenta k, atunci cand am generat deja x1, x2,...xn constatam ca valoarea xk nu este bine aleasa, nu trecem la componenta k+1, ci reluam cautarea pentru alta valoare a lui k, iar daca aceasta valoare nu exista => reluam cautarea pentru componenta k-1.
9. Observam ca dupa ce am analizat posibilele valori pe care le poate lua componenta k, avem doua posibilitati:
9.1. Trece la componenta k+1 (facem pasul inainte)
9.2. Mergem la componenta k-1 (facem pasul inapoi)
