Uvod v pohlepni algoritem

Strategija, ki se uporablja za reševanje problemov. Pohlepni algoritem velja za enega od pristopov, ki se uporabljajo za reševanje problemov. To heretično reševanje težav gre pri izbiri, ki se zdi najboljša v tistem trenutku. Ta pristop je najbolje uporabiti za reševanje težav z optimizacijo. Težave z optimizacijo lahko opredelimo kot težave, ki zahtevajo minimalne ali največje rezultate. Greedy algoritem je najpreprostejši in najbolj preprost pristop, ki ga je mogoče uporabiti za dosego optimalne rešitve.

Kaj je pohlepni algoritem?

Greedy Algorithm je algoritmična strategija, ki se uporablja za najboljšo neobvezno izbiro na zelo majhni stopnji, hkrati pa ustvari globalno optimalno rešitev. Ta algoritem izbere najboljšo izvedljivo rešitev v tistem trenutku, ne glede na posledice. Pohlepna metoda pravi, da je treba težavo reševati v stopnjah, v katerih se šteje, da je vsak vnos izvedljiv. Ker se ta pristop osredotoča le na takojšen rezultat brez upoštevanja širše slike, se šteje za pohlepno.

Opredelitev temeljnega koncepta

Do zdaj vemo, kaj je pohlepni algoritem in zakaj je tako imenovan. Spodnji kazalci vam bodo omogočili boljše razumevanje pohlepnega algoritma. Do zdaj je bilo že jasno, da pohlepni algoritem deluje le, kadar obstaja težava; kljub temu pa je ta pristop uporaben le, če imamo pogoj ali omejitev za to težavo.

Vrste problemov

  1. Problem minimiziranja: Reševanje težave je enostavno, saj so izpolnjeni vsi pogoji. Ko pa ta težava zahteva minimalne rezultate, se potem imenuje problem minimizacije.
  2. Problem maksimizacije: Problem, ki zahteva maksimalen rezultat, je znan kot problem maksimizacije.
  3. Težava z optimizacijo: Težavo imenujemo težava z optimizacijo, kadar potrebuje minimalne ali največje rezultate.

Vrste rešitev

  1. Izvedljiva rešitev: Ko se pojavi težava, imamo veliko verjetnih rešitev tega problema. Vendar ob upoštevanju pogoja, ki je postavljen na to težavo, izberemo rešitve, ki izpolnjujejo dani pogoj. Takšne rešitve, ki nam pomagajo doseči rezultate, ki izpolnjujejo dani pogoj, se imenujejo izvedljiva rešitev .
  2. Optimalna rešitev: rešitev se imenuje optimalna, ko je že izvedljiva in doseže cilj problema; najboljši rezultat. Ta cilj je lahko najmanjši ali največji rezultat. Tu je treba opozoriti, da bo vsak problem imel le eno optimalno rešitev.

Naslednji primer vam bo zlahka razumel pohlepno metodo. Recimo, nekdo želi kupiti najboljši avtomobil, ki je na voljo na trgu. Eden od načinov za izbiro tega avtomobila je analiza vseh avtomobilov na trgu. Zdaj je to precej zamudno, da si olajšamo izbiro avtomobila med tistimi določenimi znamkami, v katere so zainteresirane investirati. Če bi to nadalje razvrstili, bi spet izbrali želene modele, ki bi upoštevali njegove značilnosti. Zato je pristop, ki se tukaj uporablja, pohleven, saj je bila ta rešitev optimalna rešitev za vas, ob upoštevanju vseh dejavnikov, ki so vam bili naklonjeni.

Ključne sestavine pohlepnega algoritma

Zdaj, ko bomo bolje razumeli ta mehanizem, raziščimo osnovne sestavine pohlepnega algoritma, ki ga ločuje od drugih procesov:

  • Kandidatski niz: iz tega sklopa se ustvari odgovor.
  • Izbirna funkcija: izbere najboljšega kandidata, ki bo vključen v rešitev.
  • Funkcija izvedljivosti: V tem razdelku se izračuna, ali se lahko kandidat uporabi za rešitev.
  • Ciljna funkcija: Dodeli vrednost celotni ali delni rešitvi.
  • Funkcija rešitve: Uporablja se za označevanje, ali je bila izpolnjena ustrezna rešitev.

Kje najbolj uspeva pohlepni algoritem?

Za spodnje težave je mogoče uporabiti pohlepni algoritem.

  • Pohlepni pristop lahko uporabimo za iskanje grafa minimalnega razpona drevesa s pomočjo algoritma Prim ali Kruskal
  • Iskanje najkrajše poti med dvema vozliščema je še en problem, ki ga je mogoče rešiti s pohlepnim algoritmom. Uporaba algoritma Dijkstra skupaj z pohlepnim algoritmom vam bo dala optimalno rešitev.
  • Huffman kodiranje

Prednosti

Največja prednost, ki jo ima algoritem Greedy pred drugimi, je, da je v večini primerov enostaven za izvajanje in zelo učinkovit.

Slabosti

Greedy Algorithm v osnovi gradi rešitev po del in naslednji del izbere tako, da takoj najde najboljšo rešitev sedanjega problema. Posledično ni nobenega pomisleka ali skrbi glede posledic trenutne sprejete odločitve. Greedy Algorithm, ki nikoli ne preuči predhodno sprejetih odločitev, ne pripravi optimalne rešitve, čeprav daje skoraj optimalno rešitev . Problem nahrbtnika in problem prodajalca potovanja sta primera težav, pri katerih pohlepni algoritem ne pripravi optimalne rešitve.

  • Problem nahrbtnika : najpogosteje znan po imenu problem nahrbtnika je vsakdanja težava, s katero se srečuje veliko ljudi. Recimo, imamo na voljo predmete in vsak ima drugačno tehtano vrednost (dobiček), ki jo je treba napolniti v zabojnik, ali pa ga je treba zbrati tako, da je skupna teža manjša ali enaka masi posode, medtem ko je skupni dobiček povečan .

Zaključek

Pohlepni algoritem je najprimernejši, kadar potrebujemo rešitev v realnem času, približni odgovori pa so »dovolj dobri«. Jasno je, da pohlepni algoritem zmanjša čas, hkrati pa poskrbi, da se pripravi optimalna rešitev, zato je bolj uporabna za uporabo v razmerah, ko je potrebnih manj časa. Po branju tega članka se lahko kdo zamisli o požrešnih algoritmih. Poleg tega je v tej objavi razloženo, zakaj velja za najboljše okvire, ki odgovorijo na skoraj vse programske izzive in vam pomagajo pri odločitvi za najbolj optimalno rešitev v določenem času.

Vendar pa moramo v grobem uporabljati teorijo pohlepnega algoritma, da bi vedeli pravilna vprašanja. Čeprav gre za znanstveni koncept, ki ima logiko, ima tudi bistvo ustvarjalnosti.

Priporočeni članki

To je vodilo o tem, kaj je požrešen algoritem. Tu smo razpravljali o osnovnem konceptu, sestavnih delih, prednosti in pomanjkljivosti pohlepnega algoritma. Če želite izvedeti več, lahko preberete tudi druge naše predlagane članke -

  1. Algoritem v programiranju
  2. Kaj je Perl?
  3. Uvod v algoritem
  4. Kaj je Agile Sprint?

Kategorija:

Razvoj programske opreme