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
|