Pohlepna metoda je ena od strategij, kot je razdeli in vladaj, ki se uporablja za reševanje težav. Ta metoda se uporablja za reševanje problemov optimizacije. Optimizacijski problem je problem, ki zahteva maksimalne ali minimalne rezultate. Razumejmo skozi nekaj izrazov.

Metoda Greedy je najenostavnejši in neposreden pristop. To ni algoritem, je pa tehnika. Glavna funkcija tega pristopa je, da se odločitev sprejme na podlagi trenutno razpoložljivih informacij. Ne glede na to, katere trenutne informacije so prisotne, se odločitev sprejme brez skrbi o učinkih trenutne odločitve v prihodnosti.

režiser Karan Johar

Ta tehnika se v bistvu uporablja za določitev izvedljive rešitve, ki je lahko optimalna ali ne. Izvedljiva rešitev je podmnožica, ki izpolnjuje dane kriterije. Optimalna rešitev je rešitev, ki je najboljša in najugodnejša rešitev v podmnožici. V primeru izvedljivosti, če več kot ena rešitev izpolnjuje dane kriterije, se te rešitve štejejo za izvedljive, medtem ko je optimalna rešitev najboljša rešitev med vsemi rešitvami.

Značilnosti metode Greedy

Sledijo značilnosti pohlepne metode:

• Za optimalno konstrukcijo rešitve ta algoritem ustvari dva niza, pri čemer en niz vsebuje vse izbrane elemente, drugi niz pa zavrnjene elemente.
• Algoritem Greedy naredi dobre lokalne izbire v upanju, da bo rešitev izvedljiva ali optimalna.

Komponente pohlepnega algoritma

Komponente, ki jih je mogoče uporabiti v pohlepnem algoritmu, so:

string.contains java

Nabor kandidatov:Rešitev, ki je ustvarjena iz nabora, je znana kot nabor kandidatov.Izbirna funkcija:Ta funkcija se uporablja za izbiro kandidata ali podnabora, ki ga je mogoče dodati v rešitev.Funkcija izvedljivosti:Funkcija, ki se uporablja za ugotavljanje, ali je kandidata ali podnabor mogoče uporabiti za prispevanje k rešitvi ali ne.Ciljna funkcija:Funkcija se uporablja za dodelitev vrednosti rešitvi ali delni rešitvi.Funkcija rešitve:Ta funkcija se uporablja za ugotavljanje, ali je bila celotna funkcija dosežena ali ne.

Uporaba pohlepnega algoritma

• Uporablja se pri iskanju najkrajše poti.
• Uporablja se za iskanje najmanjšega vpetega drevesa z uporabo Primovega algoritma ali Kruskalovega algoritma.
• Uporablja se pri zaporedju opravil z rokom.
• Ta algoritem se uporablja tudi za reševanje problema delnega nahrbtnika.

Psevdo koda pohlepnega algoritma

 Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } 

Zgoraj je požrešen algoritem. Na začetku je rešitvi dodeljena vrednost nič. V požrešnem algoritmu posredujemo niz in število elementov. Znotraj zanke for izberemo element enega za drugim in preverimo ali je rešitev izvedljiva ali ne. Če je rešitev izvedljiva, potem izvedemo unijo.

Razumejmo skozi primer.

Recimo, da obstaja težava 'P'. Želim potovati od A do B, kot je prikazano spodaj:

P: A → B

Težava je v tem, da moramo potovati od A do B. Obstajajo različne rešitve, da gremo od A do B. Od A do B lahko gremo tako, da hoja, avto, kolo, vlak, letalo , itd. Na potovanju je omejitev, da moramo to potovanje opraviti v 12 urah. Samo če grem z vlakom ali letalom, lahko to razdaljo prevozim v 12 urah. Obstaja veliko rešitev za ta problem, vendar obstajata le dve rešitvi, ki zadostita omejitvi.

Če rečemo, da moramo pot opraviti z minimalnimi stroški. To pomeni, da moramo to razdaljo prevoziti čim manj, zato je ta problem znan kot problem minimizacije. Zaenkrat imamo dve izvedljivi rešitvi, eno z vlakom in drugo z letalom. Ker bo potovanje z vlakom povzročilo minimalne stroške, je to optimalna rešitev. Optimalna rešitev je tudi izvedljiva rešitev, vendar zagotavlja najboljši rezultat, tako da je rešitev optimalna rešitev z minimalnimi stroški. Optimalna rešitev bi bila samo ena.

Težava, ki zahteva najmanjši ali največji rezultat, je znana kot optimizacijska težava. Greedy metoda je ena od strategij, ki se uporablja za reševanje problemov optimizacije.

polna oblika i d e

Slabosti uporabe algoritma Greedy

Pohlepni algoritem sprejema odločitve na podlagi informacij, ki so na voljo v vsaki fazi, ne da bi upošteval širši problem. Torej obstaja možnost, da pohlepna rešitev ne ponudi najboljše rešitve za vsako težavo.

Sledi lokalni optimalni izbiri na vsaki stopnji z namenom iskanja globalnega optimuma. Razumejmo skozi primer.

Razmislite o grafu, ki je podan spodaj:

Potovati moramo od izvora do cilja z minimalnimi stroški. Ker imamo tri izvedljive rešitve s stroškovnimi potmi 10, 20 in 5. 5 je pot minimalnih stroškov, zato je to optimalna rešitev. To je lokalni optimum in na ta način najdemo lokalni optimum na vsaki stopnji, da izračunamo globalno optimalno rešitev.

css komentar