Despre Backtracking...

Metoda Backtracking este o metodă de elaborare a algoritmilor. Ea se aplică problemelor în care soluţia se poate reprezenta sub forma unui vector, X=(x1,x2,...xm), care aparţine lui S=S1xS2x...Sm

 S=S1xS2x...Sm se numeşte spaţiul soluţiilor posibile

 Pentru fiecare problemă în parte se dau anumite condiţii între componentele vectorului soluţie care se numesc condiţii interne

 Soluţiile posibile care verifică condiţiile interne se numesc soluţii rezultat

Metoda Backtracking îşi propune să genereze toate soluţiile rezultat

O metodă simplă de a genera soluţiile rezultat constă în a genera într-un mod oarecare toate soluţiile posibile şi de a alege dintre acestea doar pe cele care verifică condiţiile interne. Dezavantajul constă în faptul că timpul cerut este foarte mare.

Metoda Backtracking urmăreşte să evite generarea tuturor soluţiilor posibile. Pentru aceasta elementele vectorului x primesc pe rând valori în sensul că lui x[k] i se atribuie o valoare doar dacă componentele din faţa sa x1, x2,...x[k-1] au primit valori. 
Dacă lui x[k] i s-a atribuit o valoare, nu se trece direct la atribuirea de valori lui x[k+1], ci se verifică nişte condiţii de continuare, referitoare la x1, x2,...x[k-1], x[k]. Dacă condiţiile de continuare au fost satisfăcute, se trece la calculul lui x[k+1]. Neîndeplinirea lor exprimă faptul că oricum s-ar alege x[k+1],...,x[n], nu se va ajunge la o soluţie rezultat. Evident, ca în cazul neîndeplinirii condiţiilor de continuare va trebui să se facă o altă alegere pentru x[k]. Sau dacă S[k] a fost epuizat, să se micşoreze k cu o unitate, încercând să se facă o nouă alegere pentru xk.