logo

TechCodeview

Pohlepni algoritmi

Pohlepni algoritmi so razred algoritmov, ki naredijo lokalno optimalno izbire na vsakem koraku z upanjem, da bomo našli a globalni optimum rešitev. V teh algoritmih se odločitve sprejemajo na podlagi trenutno razpoložljivih informacij brez upoštevanja posledic teh odločitev v prihodnosti. Ključna ideja je izbrati najboljšo možno izbiro na vsakem koraku, kar vodi do rešitve, ki morda ni vedno najbolj optimalna, vendar je pogosto dovolj dobra za številne težave.

V tem članku bomo s primeri razumeli pohlepne algoritme. Ogledali si bomo tudi probleme in njihove rešitve s pohlepnim pristopom.

Pohlepni algoritmi



Kazalo

k algoritem najbližjega soseda

Kaj je Greedy Algoritem?

A požrešen algoritem je vrsta optimizacijskega algoritma, ki na vsakem koraku naredi lokalno optimalne izbire, da najde globalno optimalno rešitev. Deluje po načelu, da izbere najboljšo možnost zdaj brez upoštevanja dolgoročnih posledic.

Če želite izvedeti, kaj je pohlepna metoda in kako uporabljati pohlepni pristop, preberite dano vadnico o pohlepnem algoritmu:

Koraki za ustvarjanje pohlepnega algoritma

Koraki za definiranje pohlepnega algoritma so:

  1. Opredelite težavo: Jasno navedite problem, ki ga želite rešiti, in cilj, ki ga želite optimizirati.
  2. Prepoznajte pohlepno izbiro: Določite lokalno optimalno izbiro na vsakem koraku glede na trenutno stanje.
  3. Naredite pohlepno izbiro: Izberite pohlepno izbiro in posodobite trenutno stanje.
  4. Ponovi: Nadaljujte s pohlepnimi odločitvami, dokler ne pridete do rešitve.

Po podanih korakih se lahko naučimo, kako uporabljati pohlepne algoritme za iskanje optimalnih rešitev.

Primeri pohlepnih algoritmov

Primeri pohlepnih algoritmov so najboljši način za razumevanje algoritma. Nekateri primeri požrešnih algoritmov iz resničnega življenja so:

  • Frakcijski nahrbtnik : Optimizira vrednost predmetov, ki jih je mogoče delno vključiti v nahrbtnik z omejeno kapaciteto.
  • Dijkstrajev algoritem : Poišče najkrajšo pot od izvorne točke do vseh drugih točk v uteženem grafu.
  • Kruskalov algoritem : Poišče najmanjše vpeto drevo uteženega grafa.
  • Huffmanovo kodiranje : Stisne podatke tako, da pogostejšim simbolom dodeli krajše kode.

Uporaba pohlepnega algoritma

Veliko jih je aplikacije požrešne metode v DAA . Nekatere pomembne aplikacije pohlepnega algoritma so:

  • Dodeljevanje nalog virom, da zmanjšate čakalni čas ali povečate učinkovitost.
  • Izbira najdragocenejših predmetov, ki jih spravite v nahrbtnik z omejeno prostornino.
  • Razdelitev slike na območja s podobnimi lastnostmi.
  • Zmanjšanje velikosti podatkov z odstranitvijo odvečnih informacij.

Slabosti/omejitve uporabe pohlepnega algoritma

Spodaj je nekaj slabosti algoritma Greedy:

  • Pohlepni algoritmi morda ne bodo vedno našli najboljše možne rešitve.
  • Vrstni red, v katerem se upoštevajo elementi, lahko pomembno vpliva na rezultat.
  • Pohlepni algoritmi se osredotočajo na lokalne optimizacije in lahko zamudijo boljše rešitve, ki zahtevajo upoštevanje širšega konteksta.
  • Pohlepni algoritmi niso uporabni za probleme, kjer pohlepna izbira ne vodi do optimalne rešitve.

Osnove pohlepnega algoritma:

  • Pohlepni algoritmi (splošna struktura in aplikacije)
  • Razlika med pohlepnim algoritmom in algoritmom deli in vladaj
  • Pohlepni pristop proti dinamičnemu programiranju
  • Primerjava algoritmov Greedy, Divide and Conquer in dinamičnega programiranja

Standardni pohlepni algoritmi:

  • Težava pri izbiri dejavnosti
  • Težava z zaporedjem opravil
  • Huffmanovo kodiranje
  • Huffmanovo dekodiranje
  • Težava s priključkom na vodo
  • Najmanjše število zamenjav za uravnoteženje nosilcev
  • Egiptovski ulomek
  • Policisti ujamejo tatove
  • Težava pri nameščanju polic
  • Dodeli miši v luknje

Greedy Težave na Array:

  • Najmanjša podmnožica produkta matrike
  • Povečanje vsote matrike po K negacij z uporabo razvrščanja
  • Najmanjša vsota produkta dveh nizov
  • Najmanjša vsota absolutne razlike parov dveh nizov
  • Najmanjše povečanje/zmanjšanje, da se matrika ne povečuje
  • Razvrščanje niza z vzvratno okoli sredine
  • Vsota površin pravokotnikov, možnih za polje
  • Največji leksikografski niz z največ K zaporednimi zamenjavami
  • Razdelitev na dve podnizici dolžin k in (N – k), tako da je razlika vsot največja

Požrešne težave z operacijskim sistemom:

  • First Fit algoritem v upravljanju pomnilnika
  • Algoritem najboljšega prileganja pri upravljanju pomnilnika
  • Najslabši algoritem za upravljanje pomnilnika
  • Najkrajše prvo delovno mesto
  • Načrtovanje opravil z dvema dovoljenima opraviloma hkrati
  • Program za optimalni algoritem zamenjave strani

Pohlepne težave na grafu:

  • Kruskalovo minimalno vpeto drevo
  • Primovo minimalno vpeto drevo
  • Boruvkino minimalno vpeto drevo
  • Dijkastrin algoritem najkrajše poti
  • Dialov algoritem
  • Minimalni stroški za povezavo vseh mest
  • Uvod v problem največjega pretoka
  • Število komponent posameznega cikla v neusmerjenem grafu

Približen algoritem Greedy za NP Complete:

  • Težava s pokrovom
  • Težava pri pakiranju koša
  • Barvanje grafov
  • Težave s K-centri
  • Problem najkrajšega superniza
  • Približna rešitev za problem trgovskega potnika z uporabo MST

Požrešen za posebne primere DP:

  • Problem frakcijskega nahrbtnika
  • Zahtevano najmanjše število kovancev

Enostavne težave na Greedy Algoritem :

  • Razdeli n na največja sestavljena števila
  • Kupi največje število zalog, če je i zalog mogoče kupiti na i-ti dan
  • Poiščite najmanjši in največji znesek za nakup vseh N bonbonov
  • Največja možna vsota je enaka vsoti treh skladov
  • Kvader razdeli na kocke tako, da je vsota prostornin največja
  • Največje število kupcev, ki so lahko zadovoljni z dano količino
  • Najmanjša rotacija za odklepanje okrogle ključavnice
  • Najmanjše število sob za m dogodkov n sklopov z danim urnikom
  • Najmanjši stroški za izdelavo niza velikosti 1 z odstranitvijo večjih parov
  • Najnižji stroški za pridobitev vseh kovancev s k dodatnimi kovanci, ki so dovoljeni z vsakim kovancem
  • Najmanjši prirastek za k operacij, da so vsi elementi enaki
  • Poiščite najmanjše število bankovcev in vrednosti, ki ustrezajo danemu znesku
  • Najmanjša podmnožica z vsoto, večjo od vseh drugih elementov

Srednje težave na Greedy Algoritem :

  • Največje število vlakov, za katere se lahko zagotovi ustavitev
  • Minimalni Fibonaccijevi členi z vsoto, enako K
  • Razdelite 1 do n v dve skupini z najmanjšo razliko v vsoti
  • Papir razrezan na minimalno število kvadratov
  • Najmanjša razlika med skupinami velikosti dve
  • Povežite n vrvi z minimalnimi stroški
  • Najmanjše število peronov, potrebnih za železniško/avtobusno postajo
  • Najmanjša začetna vozlišča za prečkanje celotne matrike z danimi pogoji
  • Največje palindromsko število s permutacijo števk
  • Poiščite najmanjše število z danim številom števk in vsoto števk
  • Leksikografsko največje podzaporedje, tako da se vsak znak pojavi vsaj k-krat

Težke težave na Greedy Algoritem :

  • Največje število elementov, ki jih je mogoče izenačiti s k posodobitvami
  • Zmanjšajte denarni tok med prijatelji
  • Minimalni stroški za rezanje deske na kvadrate
  • Minimalni stroški za obdelavo m nalog, kjer stroški zamenjave
  • Minimalni čas za dokončanje vseh opravil z danimi omejitvami
  • Zmanjšajte največjo razliko med višinami stolpov
  • Najmanjši robovi, ki jih je treba obrniti, da ustvarite pot od vira do cilja
  • Poiščite največjo kocko, sestavljeno z brisanjem najmanjših števk iz števila
  • Prerazporedite znake v nizu tako, da nobena dva sosednja nista enaka
  • Preuredite niz tako, da bodo vsi isti znaki oddaljeni d
  • Naučite se podatkovne strukture in algoritmov | Vadnica DSA
  • 20 najboljših vprašanj za intervjuje o pohlepnih algoritmih
  • 'Težave za vajo' o pohlepnih algoritmih
  • 'Kviz' o pohlepnih algoritmih