TOATE REFERATELE - ADAUGA REFERAT

COLORAREA HARTILOR FOLOSIND METODA BACKTRACKING - Informatica

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

descarcat de 389 ori

nota totala 4.29

autor: c


Inscriere in newsletter

Referate liceu (1282)

Ultimele cautari

Cele mai downloadate

 

acasa -
Viata de Student Referate Filme Porno Sex Shop Moda si Fashion Fashion Sales