Uvod u pohlepni algoritam

Strategija koja se koristi za rješavanje problema. Pohlepni algoritam smatra se jednim od pristupa koji se koristi za rješavanje problema. Ovo heretičko rješavanje problema ide u odabiru izbora koji se u tom trenutku čini najboljim. Ovaj pristup se najbolje koristi za rješavanje problema optimizacije. Problemi s optimizacijom mogu se definirati kao problemi koji zahtijevaju minimalne ili maksimalne rezultate. Greedy algoritam je najjednostavniji i najpristraniji pristup koji se može koristiti za postizanje optimalnog rješenja.

Što je pohlepni algoritam?

Greedy Algorithm je algoritamska strategija koja se koristi za donošenje najboljeg izbornog izbora u vrlo maloj fazi, dok se na kraju postiže globalno optimalno rješenje. Ovaj algoritam odabire najbolje izvodljivo rješenje u tom trenutku bez obzira na posljedice. Pohlepna metoda kaže da bi problem trebalo riješiti u fazama u kojima se smatra da je svaki unos izvediv. Kako se ovaj pristup usredotočuje samo na neposredni rezultat bez obzira na širu sliku, smatra se pohlepnim.

Definiranje temeljnog koncepta

Do sada znamo što je pohlepni algoritam i zašto je tako nazvan. Dolje navedeni pokazivači olakšat će vam razumijevanje pohlepnog algoritma. Do sada je bilo vrlo jasno da pohlepni algoritam radi samo kad postoji problem; ipak, ovaj je pristup primjenjiv samo ako imamo uvjet ili ograničenje za taj problem.

Vrste problema

  1. Problem minimizacije: Rješavanje problema je jednostavno s obzirom da su svi uvjeti ispunjeni. Međutim, kada ovaj problem zahtijeva minimalan rezultat, tada se naziva minimizacijskim problemom.
  2. Problem s maksimiziranjem: Problem koji zahtijeva maksimalan rezultat poznat je kao problem maksimizacije.
  3. Problem s optimizacijom: Problem se naziva problem optimizacije kada zahtijeva minimalne ili maksimalne rezultate.

Vrste rješenja

  1. Izvodljivo rješenje: Sada kada se pojavi problem, imamo mnogo vjerojatnih rješenja za ovaj problem. Ipak, uzimajući u obzir uvjet postavljen na tom problemu, biramo rješenja koja zadovoljavaju zadani uvjet. Ovakva rješenja koja nam pomažu da postignemo rezultate koji ispunjavaju zadani uvjet naziva se izvedivim rješenjem .
  2. Optimalno rješenje: rješenje se naziva optimalnim onda kada je već izvedivo i postiže cilj problema; najbolji rezultat. Ovaj bi cilj mogao biti minimalni ili maksimalni rezultat. Ovdje se mora primijetiti da će svaki problem imati samo jedno optimalno rješenje.

Sljedeći će vam primjer olakšati razumijevanje pohlepne metode. Recimo, čovjek želi kupiti najbolji automobil koji je dostupan na tržištu. Jedna od metoda za odabir ovog automobila je analiza svih automobila na tržištu. E sad, ovo zahtijeva mnogo vremena da bi se olakšalo odabir automobila iz određenih marki u koje su zainteresirane uložiti. Kategorizirajući to dalje, opet bismo odabrali željene modele gledajući njegove karakteristike. Stoga je ovdje korišteni pristup pohlepan jer je ovo rješenje bilo optimalno rješenje za vas dok smo uvažili sve faktore koji su vam bili povoljni.

Ključne komponente pohlepnog algoritma

Sada kad bolje razumijemo ovaj mehanizam, istražimo osnovne komponente pohlepnog algoritma koji ga izdvaja od ostalih procesa:

  • Skup kandidata: Odgovor se stvara iz ovog skupa.
  • Funkcija odabira: odabire najboljeg kandidata koji će biti uključen u rješenje.
  • Funkcija izvodljivosti: Ovaj odjeljak izračunava može li se kandidat koristiti za doprinos rješenju.
  • Objektivna funkcija: dodjeljuje vrijednost cjelovitom ili djelomičnom rješenju.
  • Funkcija rješenja: koristi se za označavanje da li je zadovoljeno pravilno rješenje.

Gdje najbolji pohlepni algoritam najbolje djeluje?

Pohlepni algoritam može se primijeniti na dolje navedene probleme.

  • Pohlepni pristup može se upotrijebiti za pronalaženje grafa minimalnog raspona drveća pomoću Primovog ili Kruskalovog algoritma
  • Pronalaženje najkraćeg puta između dvaju vrhova još je jedan problem koji se može riješiti pohlepnim algoritmom. Primjena Dijkstra algoritma zajedno s pohlepnim algoritmom dobit će vam optimalno rješenje.
  • Huffman kodiranje

prednosti

Najveća prednost koju algoritam Greedy ima u odnosu na druge je ta što ga je lako implementirati i vrlo je učinkovit u većini slučajeva.

Nedostaci

Greedy Algorithm u osnovi gradi rješenje po dio i sljedeći dio odabire na način da odmah nudi najbolje rješenje postojećeg problema. Kao rezultat toga, nema brige ili brige o posljedicama donijeti trenutne odluke. Nikada ne preispitujući prethodno odabrane odluke, pohlepni algoritam ne uspijeva proizvesti optimalno rješenje, iako daje gotovo optimalno rješenje . Problem ruksaka i putnički prodavač problem su primjeri problema gdje pohlepni algoritam ne daje optimalno rješenje.

  • Problem s ruksakom : najčešće poznat pod nazivom problem ruksaka svakodnevni je problem s kojim se suočavaju mnogi ljudi. Recimo, postavili smo predmete i svaka od njih ima različitu težinu i vrijednost (dobit) koja se puni u spremnik ili ih treba sakupljati na način da je ukupna težina manja ili jednaka onoj u spremniku, dok je ukupna dobit maksimalna,

Zaključak

Pohlepni algoritam najbolje je primijeniti kada je potrebno rješenje u stvarnom vremenu, a približni odgovori su "dovoljno dobri". Jasno je da pohlepni algoritam minimizira vrijeme, osiguravajući da se proizvede optimalno rješenje, stoga je prikladnije koristiti u situaciji kada je potrebno manje vremena. Nakon čitanja ovog članka, možda bi se imala dobra ideja o pohlepnim algoritamima. Uz to, u ovom postu objavljeno je zašto se smatra najboljim okvirom koji odgovara na gotovo sve programske izazove, zajedno s time što vam pomaže u odlučivanju najoptimalnijeg rješenja u određenom trenutku.

Međutim, s grube strane, za primjenu teorije pohlepnog algoritma potrebno je više raditi na poznavanju ispravnih problema. Iako se radi o znanstvenom konceptu koji ima logiku, on ima i suštinu kreativnosti.

Preporučeni članci

Ovo je vodič za ono što je pohlepni algoritam. Ovdje smo razgovarali o temeljnom konceptu, komponentama, prednosti i nedostatku pohlepnog algoritma. Možete i proći naše druge predložene članke da biste saznali više -

  1. Algoritam u programiranju
  2. Što je Perl?
  3. Uvod u algoritam
  4. Što je Agile Sprint?

Kategorija: