Extras din curs
Este una dintre cele mai cunoscute metode de elaborare a algoritmilor. Ea se aplic acelor
probleme @n care solutia se poate reprezenta sub forma unui vector x=(x1,. . . , xn)ÎA1x. . .xAn, unde Ai,
i=1, n sunt finite ( i A =ni, i=1, n ). in plus, pentru fiecare problem @n parte este necesar ca solutia:
x1,...,xn sa satisfac anumite conditii interne r(x1, . . . , xn).
Multimea A=A1x. . .xAn este spatiul solutiilor posibile. Elementele xÎA care satisfac conditiile
interne se numesc solutii rezultat. Ne propunem determinarea tuturor solutiilor rezultat, eventual pentru
a alege dintre ele pe cea care minimizeaz sau maximizeaz o functie obiectiv.
Metoda Backtracking evit generarea tuturor solutiilor posibile (toate elementele produsului
cartezian A1x...xAn). Elementului xkÎAk, k=1, n i se atribuie o valoare dup ce au fost atribuite valori
pentru componentele x1ÎA1,..., xk-1ÎAk-1. Metoda trece la atribuirea unei valori pentru xk+1ÎAk+1 doar
dac xk @mpreun cu x1,...,xk-1 verific conditiile de continuare, notate rk(x1,...,xk). Dac conditiile
rk(x1,...,xk) sunt @ndeplinite se trece la atribuirea unei valori pentru elementul xk+1ÎAk+1 al solutiei.
Neindeplinirea conditiilor exprim faptul c oricum am alege xk+1ÎAk+1,...,xnÎAn nu vom putea ajunge
la o solutie rezultat @n care conditiile interne s fie @ndeplinite. in acest ultim caz va trebui s facem o
alt alegere pentru xk, iar acest lucru este posibil doar dac nu am epuizat toate valorile posibile din
multimea Ak. Dac multimea Ak a fost epuizat va trebui sa mic]or m pe k, k¬k-1 ]i s trecem la
Preview document
Conținut arhivă zip
- Backtracking.pdf
Alții au mai descărcat și
Adăugarea de câmpuri la o tabelă se face în modul de vizualizare:...... Previzualizare inaintea imprimarii Aplicarea unei restrictii de...
3.Introducere in bd si sgbd-uri Definitie: Numim baza de date o colectie partajata de date aflata in interdependenta logica impreuna cu o...
Te-ar putea interesa și
1. METODA BACKTRACKING 1. 1. Stiva Stiva este acea formã de organizare a datelor ( structurã de date ) cu proprietatea cã operatiile de...
Aparitia limbajului Pascal este un raspuns la criza care a aparut in domeniul programarii calculatoarelor , la sfarsitul anilor ’60 . Limitarile...
Metoda backtracking se utilizeaza pentru rezolvarea unor probleme in care: - se obtin mai multe solutii; -solutia este formata din unul sau mai...
1. Sarcina lucrării Să se scrie un program ce rezolvă următoarea problema: Problema celor 8 dame:Se cere să se găseasca toate soluţiile de...
CAPITOLUL 1: ASPECTE TEORETICE Această tehnică se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii: • soluţia...
I.1.Notiuni introductive Limbajul Turbo Pascal a aparut la inceputul anilor ’70 si a fost elaborat de matematicianul N. Wirth. Initial limbajul a...
METODA BACKTRACKING Tehnica folosita:Metoda Backtracking Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simulltan...
1 Metoda backtracking Stiva este acea forma de organizare a datelor (structura de date ) cu proprietatea ca operatiile de introducere si scoatere...