Capitolul 1
PREZENTAREA TEHNICII BACKTRAKING
Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:
solutia lor poate fi pusa sub forma unui vector S=x1,x2,x3 . xn cu
x1(A1,x2(A2, ..,xn(An;
multimile A1,A2,A3 . An sunt multimi finite ,iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita
nu se dispune de o alta metoda de rezolvare ,mai rapida.
Observatii:
nu pentru toate problemele n este cunoscut de la inceput;
x1,x2,x3 . xn pot fi la randul lor vectori;
in multe probleme multimile A1,A2,A3 . An coincid;
La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica,suntem tentati sa generam toate elementele produsului cartezian A1(A2(A3 . (An si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod,timpul de executie este atat de mare ,incat poate fi considerat infinit,neavand nici o valoare practica.
De exemplu,daca dorim sa generam toate permutarile unei multimi finite A,nu are rost sa generam produsul cartezian A1A2A3 . An pentru ca apoi,sa testam,pentru fiecare element al acestuia,daca este sau nu permutare .
Tehnica Backtracking are la baza un principiu extrem de simplu:
se construieste solutia pas cu pas:x1x2x3 . xn;
daca se constata ca,pentru o valoare aleasa,nu avem cum sa ajungem la solutie ,se renunta la acea valoare si se reia cautarea din punctul in care am ramas
Concret:
se alege primul element x1 ce apartine lui A1
presupunand generate elementele x1,x2,x3 . xk apartinand multimilor A1 A 2A3 . Ak+1 se alege(daca exista) x,primul element disponibil din multimea Ak+1,apar astfel 2 posibilitati:
nu s-a gasit un astfel de element,caz in care se reia cautarea considerand generate elementele x1,x2,x3 . xk+1 iar aceasta se reia de la urmatorul element al multimii Ak ramas netestat
a fost gasit,caz in care se testeaza daca acesta indeplineste anumite coditii de continuare ,aparand astfel alte doua posibilitati:
2.
