metoda greedy223

7

Click here to load reader

Upload: vladimirwelling

Post on 29-Jul-2015

83 views

Category:

Devices & Hardware


0 download

TRANSCRIPT

Page 1: Metoda greedy223

Arnăutu Vladimir cl. 11”A”

metoda Greedy

Page 2: Metoda greedy223

Metoda Greedy

Definiţie:Metoda Greedy este una dintre cele

mai directe tehnici de proiectare a algoritmilor care poate fi aplicată la o gamă largă de probleme.

Page 3: Metoda greedy223

Această metodă se aplică problemelor de optimizare, care constau în determinarea unei submultimi B, a unei mulţimi A cu n elemente care să îndeplinească anumite condiţii pentru a fi acceptate.

Page 4: Metoda greedy223

Orice submulţime de acest fel, care respectă aceste condiţii se numeşte soluţie posibilă.Din mulţimea tuturor soluţiilor posibile se doreştedeterminarea unei soluţii care maximizează sau minimizează o funcţie de cost. O soluţie posibilă care realizează acest lucru se numeşte soluţie optimă.

Page 5: Metoda greedy223

Descrierea metodei:Exemplu: Se dă o mulţime A cu n elemente şi se cere să se determine o submulţime B care satisface anumite restricţii. Această soluţie se numeşte soluţie posibilă. Se cere să se determine o soluţie posibilă care să maximizeze sau să minimizeze o anumită funcţie obiectiv dată. Această soluţie se numeşte soluţie optimă.

Page 6: Metoda greedy223

Specificul acestei metode constă în faptul că se construieştesoluţia optimă pas cu pas, la fiecare pas fiind selectat (sau "înghiţit") în soluţie elementul care pare "cel mai bun" la momentul respectiv, în speranţa că va duce la soluţia optimă globală.

Page 7: Metoda greedy223