ݺߣ

ݺߣShare a Scribd company logo

Metoda greedy

•Download as PPTX, PDF•
•
L
Luminița Mihailov

folos

1 of 7
Download to read offline
Metoda greedy
Medoda greedy poate folosii în problemele care dîndu-se o mulțime finită A trebuie determinată o mulțime care să îndeplinească anumite condiții. Metoda data furnizează o singură soluție,reprezentat prin elementul mulțimii S. Scop- indentificarea problemelor în care solțiile optimă este o submulțime inclusă intr-o submulțime de dată,care trebuie să îndeplinească anumite condiții.
01.Elevul sa defineasca si sa clasifice 02.Pe baza explicatiilor date de profesor, elevul sa conceapa un algoritm Greedy 03.Sa identifice avantajele si dezavantajele utilizarii acestei tehnici de programare. 04.Sa scrie programe Pascal pentru algoritmi Greedy
 Conversatia euristica  Observatia participativa  Expunerea  Invatarea prin descoperire dirijata  Metoda orientata pe exemple si pe rezolvarea de exercitii in laborator  Modelarea matematica  Instruirea asistata de calculator
Metoda greedy construieste soluția prin selectarea,dintr-o mulțime de elemente,a elementelor care îndeplinesc anumite condiții. Pentru ca elementele care se selectează,să aparțină soluției optime,la pasul k se alege candidatul optim pentru elementul x,al soluției. Acestă metodă duce la obținerea soluției optme în cazul problemelor care au proprietatea de optim local,adică soluția optimă a problemei cu dimensiuni n a datelor de intrare conține soluți optime ale subprogramelor similare cu problema inițial,cu dimensiuni mici. Medoda greedy se mai numește metoda optimului local.
Pașii algoritmici metodei greedy  Pasul 1- se inițializează mulțimes S cu mulțimea vidă;  Pasul 2 –se alege din mulțimea A elementului a care este candidatul optim al soluției;  Pasul 3- se elimină elementul a din mulțimea A  Pasul 4 – dacă el poate fii elemnent al soluției,atunci elementul a se adaugă la mulțimea S;  Pasul 5- dacă mulțimea S este soluția problemei,atuni se afisează soluția.astfel se afisează mesajul “Nu s-a găsit soluția”.
Algoritmul greedy este un algoritm iterativ care determină soluția optimă a problemei în urma unor succesiuni care reduc dimensiunea problemei respective. Pentru opținerea soluției optime algoritmul greedy trebuie să îndeplnească două condiții principale: Alegerea optimului localpentru fiecare element al soluției duce la alegerea soluției optime globale Soluția optimă a problemei conține soluții optime ale subproblemelor

More Related Content

Metoda greedy

  • 2. Medoda greedy poate folosii în problemele care dîndu-se o mulțime finită A trebuie determinată o mulțime care să îndeplinească anumite condiții. Metoda data furnizează o singură soluție,reprezentat prin elementul mulțimii S. Scop- indentificarea problemelor în care solțiile optimă este o submulțime inclusă intr-o submulțime de dată,care trebuie să îndeplinească anumite condiții.
  • 3. 01.Elevul sa defineasca si sa clasifice 02.Pe baza explicatiilor date de profesor, elevul sa conceapa un algoritm Greedy 03.Sa identifice avantajele si dezavantajele utilizarii acestei tehnici de programare. 04.Sa scrie programe Pascal pentru algoritmi Greedy
  • 4.  Conversatia euristica  Observatia participativa  Expunerea  Invatarea prin descoperire dirijata  Metoda orientata pe exemple si pe rezolvarea de exercitii in laborator  Modelarea matematica  Instruirea asistata de calculator
  • 5. Metoda greedy construieste soluția prin selectarea,dintr-o mulțime de elemente,a elementelor care îndeplinesc anumite condiții. Pentru ca elementele care se selectează,să aparțină soluției optime,la pasul k se alege candidatul optim pentru elementul x,al soluției. Acestă metodă duce la obținerea soluției optme în cazul problemelor care au proprietatea de optim local,adică soluția optimă a problemei cu dimensiuni n a datelor de intrare conține soluți optime ale subprogramelor similare cu problema inițial,cu dimensiuni mici. Medoda greedy se mai numește metoda optimului local.
  • 6. Pașii algoritmici metodei greedy  Pasul 1- se inițializează mulțimes S cu mulțimea vidă;  Pasul 2 –se alege din mulțimea A elementului a care este candidatul optim al soluției;  Pasul 3- se elimină elementul a din mulțimea A  Pasul 4 – dacă el poate fii elemnent al soluției,atunci elementul a se adaugă la mulțimea S;  Pasul 5- dacă mulțimea S este soluția problemei,atuni se afisează soluția.astfel se afisează mesajul “Nu s-a găsit soluția”.
  • 7. Algoritmul greedy este un algoritm iterativ care determină soluția optimă a problemei în urma unor succesiuni care reduc dimensiunea problemei respective. Pentru opținerea soluției optime algoritmul greedy trebuie să îndeplnească două condiții principale: Alegerea optimului localpentru fiecare element al soluției duce la alegerea soluției optime globale Soluția optimă a problemei conține soluții optime ale subproblemelor