METODA BACKTRACKING
NOÅ¢IUNI GENERALE


    La dispoziÅ£ia celor care rezolvă probleme cu ajutorul calculatorului există mai multe metode . Dintre acestea cel mai des utilizate sunt:

metoda Greedy;
metoda Divide et impera;
metoda Branch and Bound;
metoda Backtracking;

Metoda Backtracking se aplică problemelor în care soluÅ£ia poate fi reprezentată sub forma unui vector – x = (x1, x2, x3, …xk,… xn) € S, unde S este mulÅ£imea soluÅ£iilor problemei ÅŸi S = S1 x S2 x… x Sn, ÅŸi Si sunt mulÅ£imi finite având s elemente si xi € si , (¥)i = 1..n.
    Pentru fiecare problemă se dau relaÅ£ii între componentele vectorului x, care sunt numite condiÅ£ii interne; soluÅ£iile posibile care satisfac condiÅ£iile interne se numesc soluÅ£ii rezultat. Metoda de generare a tuturor soluÅ£iilor posibile si apoi de determinare a soluÅ£iilor rezultat prin verificarea îndeplinirii condiÅ£iilor interne necesită foarte mult timp.
    Metoda backtracking evită această generare ÅŸi este mai eficientă. Elementele vectorului x, primesc pe rând valori în ordinea crescătoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica îndeplinirea unor condiÅ£ii de continuare referitoare la x1…x[k-1]. Daca aceste condiÅ£ii nu sunt îndeplinite, la pasul k, acest lucru înseamnă ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o soluÅ£ie rezultat.
Metoda backtracking construieÅŸte un vector soluÅ£ie în mod progresiv începând cu prima componentă a vectorului ÅŸi mergând spre ultima cu eventuale reveniri asupra atribuirilor anterioare.
    Metoda se aplica astfel :
1)    se alege prima valoare sin S1 si I se atribuie lui x1 ;
2)    se presupun generate elementele x1…x[k-1], cu valori din S1..S[k-1]; pentru generarea lui x[k] se alege primul element din S[k] disponibil si pentru valoarea aleasa se testează îndeplinirea condiÅ£iilor de continuare.
Pot apărea următoarele situaţii :
a)    x[k] îndeplineÅŸte condiÅ£iile de continuare. Daca s-a ajuns la soluÅ£ia finală (k = n) atunci se afiÅŸează soluÅ£ia obÅ£inută. Daca nu s-a ajuns la soluÅ£ia finală se trece la generarea elementului următor – x [k-1];
b)    x[k] nu îndeplineÅŸte condiÅ£iile de continuare. Se încearcă următoarea valoare disponibila din S[k]. Daca nu se găseÅŸte nici o valoare în S[k] care să îndeplinească condiÅ£iile de continuare, se revine la elementul x[k-1] ÅŸi se reia algoritmul pentru o nouă valoare a acestuia. Algoritmul se încheie când au fost luate in considerare toate elementele lui S1.
Problemele rezolvate prin această metodă necesită timp mare de execuţie, de aceea este indicat sa se folosească metoda numai daca nu avem alt algoritm de rezolvare.

Pentru a vedea tot referatul

CLICK AICI