Document, comentariu, eseu, bacalaureat, liceu si facultate
Top documenteAdmitereTesteUtileContact
      
    


 


Ultimele referate adaugate

Adauga referat - poti sa ne ajuti cu un referat?

Politica de confidentialitate



Ultimele referate descarcare de pe site
  CREDITUL IPOTECAR PENTRU INVESTITII IMOBILIARE (economie)
  Comertul cu amanuntul (economie)
  IDENTIFICAREA CRIMINALISTICA (drept)
  Mecanismul motor, Biela, organe mobile proiect (diverse)
  O scrisoare pierduta (romana)
  O scrisoare pierduta (romana)
  Ion DRUTA (romana)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  Starea civila (geografie)
 

Ultimele referate cautate in site
   domnisoara hus
   legume
    istoria unui galban
   metanol
   recapitulare
   profitul
   caract
   comentariu liric
   radiolocatia
   praslea cel voinic si merele da aur
 
despre:
 
METODA BACKTRACKING
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 
v1z7zf
NOTIUNI GENERALE La dispozitia celor care rezolva probleme cu ajutorul calculatorului exista 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 aplica problemelor in care solutia poate fi reprezentata sub forma unui vector -; x = (x1, x2, x3, …xk,… xn) € S, unde S este multimea solutiilor problemei si S = S1 x S2 x… x Sn, si Si sunt multimi finite avand s elemente si xi € si , (¥)i = 1..n.
Pentru fiecare problema se dau relatii intre componentele vectorului x, care sunt numite conditii interne; solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Metoda de generare a tuturor solutiilor posibile si apoi de determinare a solutiilor rezultat prin verificarea indeplinirii conditiilor interne necesita foarte mult timp.
Metoda backtracking evita aceasta generare si este mai eficienta. Elementele vectorului x, primesc pe rand valori in ordinea crescatoare a indicilor, xaki va primi o valoare numai daca au fost atribuite valori elementelor x1.. xak-1i. La atribuirea valorii lui xaki se verifica indeplinirea unor conditii de continuare referitoare la x1…xak-1i. Daca aceste conditii nu sunt indeplinite, la pasul k, acest lucru inseamna ca orice valori i-am atribui lui xak+1i, xak+1i, .. xani nu se va ajunge la o solutie rezultat.
Metoda backtracking construieste un vector solutie in mod progresiv incepand cu prima componenta a vectorului si mergand 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…xak-1i, cu valori din S1..Sak-1i; pentru generarea lui xaki se alege primul element din Saki disponibil si pentru valoarea aleasa se testeaza indeplinirea conditiilor de continuare.
Pot aparea urmatoarele situatii : a) xaki indeplineste conditiile de continuare. Daca s-a ajuns la solutia finala (k = n) atunci se afiseaza solutia obtinuta. Daca nu s-a ajuns la solutia finala se trece la generarea elementului urmator -; x ak-1i; b) xaki nu indeplineste conditiile de continuare. Se incearca urmatoarea valoare disponibila din Saki. Daca nu se gaseste nici o valoare in Saki care sa indeplineasca conditiile de continuare, se revine la elementul xak-1i si se reia algoritmul pentru o noua valoare a acestuia. Algoritmul se incheie cand au fost luate in considerare toate elementele lui S1.
Problemele rezolvate prin aceasta metoda necesita timp mare de executie, de aceea este indicat sa se foloseasca metoda numai daca nu avem alt algoritm de rezolvare.
Daca multimile S1,S2,…Sn au acelasi numar k de elemente, timpul necesar de executie al algoritmului este k la n. Daca multimile S1, S2.. Sn nu au acelasi numar de elemente, atunci se noteaza cu „m” minimul cardinalelor multimilor S1…Sn si cu „M”, maximul. Timpul de executie este situat in intervalul am la n .. M la ni. Metoda backtracking are complexitatea exponentiala, in cele mai multe cazuri fiind ineficienta. Ea insa nu poate fi inlocuita cu alte variante de rezolvare mai rapide in situatia in care se cere determinarea tuturor solutiilor unei probleme.


Colt dreapta
Creeaza cont
Comentarii:

Nu ai gasit ce cautai? Crezi ca ceva ne lipseste? Lasa-ti comentariul si incercam sa te ajutam.
Esti satisfacut de calitarea acestui document, eseu, cometariu? Apreciem aprecierile voastre.

Nume (obligatoriu):

Email (obligatoriu, nu va fi publicat):

Site URL (optional):


Comentariile tale: (NO HTML)


Noteaza documentul:
In prezent fisierul este notat cu: ? (media unui numar de ? de note primite).

2345678910

 
Copyright© 2005 - 2024 | Trimite document | Harta site | Adauga in favorite
Colt dreapta