Pohlepni algoritem s primeri: Pohlepna metoda & Pristop

Kazalo:

Anonim

Kaj je pohlepni algoritem?

V Pohlepnem algoritmu se nabor virov rekurzivno deli na podlagi največje in takojšnje razpoložljivosti tega vira v kateri koli fazi izvedbe.

Za rešitev problema, ki temelji na pohlepnem pristopu, obstajata dve stopnji

  1. Optično branje seznama elementov
  2. Optimizacija

Te stopnje so vzporedno opisane v tej vadnici Pohlepnega algoritma o poteku delitve polja.

Če želite razumeti požrešen pristop, boste morali dobro poznati rekurzijo in preklapljanje konteksta. To vam pomaga razumeti, kako slediti kodi. Pohlepno paradigmo lahko definirate z lastnimi potrebnimi in zadostnimi izjavami.

Pohlepno paradigmo opredeljujeta dva pogoja.

  • Vsaka postopna rešitev mora problem strukturirati tako, da bo najbolje sprejeta.
  • Dovolj je, če se lahko strukturiranje problema ustavi v končnem številu pohlepnih korakov.

Z nadaljevanjem teoretiziranja opišimo zgodovino, povezano s pristopom pohlepnega iskanja.

V tej vadnici Pohlepnega algoritma boste izvedeli:

  • Zgodovina pohlepnih algoritmov
  • Pohlepne strategije in odločitve
  • Značilnosti pohlepnega pristopa
  • Zakaj uporabiti pohlepni pristop?
  • Kako rešiti problem izbire dejavnosti
  • Arhitektura pohlepnega pristopa
  • Slabosti pohlepnih algoritmov

Zgodovina pohlepnih algoritmov

Tu je pomemben mejnik požrešnih algoritmov:

  • Pohlepni algoritmi so bili konceptualizirani za številne algoritme sprehajanja grafov v petdesetih letih.
  • Esdger Djikstra je zasnoval algoritem za generiranje minimalnih dreves. Želel je skrajšati razpon poti znotraj nizozemske prestolnice Amsterdam.
  • V istem desetletju sta Prim in Kruskal dosegla optimizacijski strategiji, ki sta temeljili na zmanjšanju stroškov poti po tehtanih poteh.
  • V sedemdesetih so ameriški raziskovalci Cormen, Rivest in Stein v svoji klasični predstavitvi knjige o algoritmih predlagali rekurzivno prestrukturiranje pohlepnih rešitev.
  • Pohlepna iskalna paradigma je bila v evidenci NIST leta 2005 registrirana kot drugačna vrsta strategije optimizacije.
  • Do danes protokoli, ki poganjajo splet, na primer OSPF in številni drugi protokoli za preklapljanje omrežnih paketov, uporabljajo pohlepno strategijo, da minimizirajo čas, porabljen v omrežju.

Pohlepne strategije in odločitve

Logika v svoji najlažji obliki se je svedla na "pohlepno" ali "ne pohlepno". Te izjave so bile opredeljene s pristopom za napredovanje v vsaki fazi algoritma.

Na primer, Djikstrin algoritem je uporabil postopno pohlepno strategijo za prepoznavanje gostiteljev v internetu z izračunom stroškovne funkcije. Vrednost, ki jo vrne funkcija stroškov, je določala, ali je naslednja pot "pohlepna" ali "nepohlepna".

Skratka, algoritem preneha biti požrešen, če v kateri koli fazi naredi korak, ki ni lokalno požrešen. Pohlepni problemi se ustavijo brez nadaljnjega pohlepa.

Značilnosti pohlepnega pristopa

Pomembne značilnosti algoritma Pohlepne metode so:

  • Obstaja urejen seznam virov s pripisovanjem stroškov ali vrednosti. Te količinsko opredelijo omejitve sistema.
  • Vzeli boste največjo količino virov v času, ko velja omejitev.
  • Na primer, pri težavi z razporejanjem dejavnosti so stroški virov v urah, dejavnosti pa je treba izvajati v zaporednem vrstnem redu.

Zakaj uporabiti pohlepni pristop?

Tukaj so razlogi za uporabo pohlepnega pristopa:

  • Pohlepni pristop ima nekaj kompromisov, zaradi česar je primeren za optimizacijo.
  • Eden pomembnih razlogov je, da takoj dosežemo najučinkovitejšo rešitev. Če je v težavi z izbiro dejavnosti (razloženo spodaj), če je pred zaključkom trenutne dejavnosti mogoče opraviti več dejavnosti, lahko te dejavnosti opravite v istem času.
  • Drugi razlog je, da problem razdelimo rekurzivno na podlagi stanja, pri čemer ni treba kombinirati vseh rešitev.
  • V težavi z izbiro dejavnosti se korak "rekurzivna delitev" doseže s pregledom seznama elementov samo enkrat in upoštevanjem določenih dejavnosti.

Kako rešiti problem izbire dejavnosti

V primeru razporejanja dejavnosti je za vsako dejavnost določen čas "začetek" in "zaključek". Vsaka aktivnost je za referenco indeksirana s številko. Obstajata dve kategoriji dejavnosti.

  1. obravnavana dejavnost : je dejavnost, ki je referenca, na podlagi katere se analizira sposobnost opravljanja več kot ene preostale dejavnosti.
  2. preostale dejavnosti: dejavnosti z enim ali več indeksi pred obravnavano dejavnostjo.

Skupno trajanje prikazuje stroške izvajanja dejavnosti. To je (zaključek - začetek) nam daje trajanje kot strošek dejavnosti.

Izvedeli boste, da je požrešen obseg število preostalih dejavnosti, ki jih lahko opravite v času obravnavane dejavnosti.

Arhitektura pohlepnega pristopa

KORAK 1)

Preglejte seznam stroškov dejavnosti, začenši z indeksom 0 kot upoštevanim indeksom.

2. KORAK)

Ko je do takrat mogoče zaključiti več dejavnosti, se obravnavana dejavnost konča, začnite iskati eno ali več preostalih dejavnosti.

3. KORAK)

Če preostalih dejavnosti ni več, postane trenutna preostala dejavnost naslednja obravnavana dejavnost. Ponovite 1. in 2. korak z novo obravnavano dejavnostjo. Če ni preostalih dejavnosti, pojdite na 4. korak.

4. KORAK)

Vrni zvezo obravnavanih indeksov. To so indeksi dejavnosti, s katerimi bomo povečali pretočnost.

Arhitektura pohlepnega pristopa

Razlaga kode

#include#include#include#define MAX_ACTIVITIES 12

Pojasnilo kode:

  1. Vključene datoteke / razredi glave
  2. Največje število dejavnosti, ki jih zagotavlja uporabnik.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Pojasnilo kode:

  1. Imenski prostor za pretočne operacije.
  2. Definicija razreda za TIME
  3. Časovni žig ure.
  4. Privzeti konstruktor TIME
  5. Spremenljivka ur.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Pojasnilo kode:

  1. Definicija razreda iz dejavnosti
  2. Časovni žigi, ki določajo trajanje
  3. Vsi časovni žigi so v privzetem konstruktorju inicializirani na 0
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Pojasnilo kode:

  1. 1. del definicije razreda načrtovalca.
  2. Upoštevani indeks je izhodišče za skeniranje matrike.
  3. Inicializacijski indeks se uporablja za dodelitev naključnih časovnih žigov.
  4. Niz objektov dejavnosti se dinamično dodeli z uporabo novega operaterja.
  5. Razporejeni kazalnik definira trenutno osnovno lokacijo za pohlep.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Pojasnilo kode:

  1. Konstruktor načrtovalca - 2. del definicije razreda načrtovalca.
  2. Upoštevani indeks določa trenutni začetek trenutnega pregleda.
  3. Trenutni pohlepni obseg na začetku ni opredeljen.
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++){current_activities[init_index].start.hours =rand() % 12;current_activities[init_index].finish.hours =current_activities[init_index].start.hours +(rand() % 2);printf("\nSTART:%d END %d\n",current_activities[init_index].start.hours,current_activities[init_index].finish.hours);}… …

Pojasnilo kode:

  1. Zanka for za inicializacijo začetnih in končnih ur vsake trenutno načrtovane dejavnosti.
  2. Inicializacija začetnega časa.
  3. Inicializacija končnega časa vedno po ali natančno ob začetni uri.
  4. Stavek za odpravljanje napak za izpis dodeljenih trajanj.
public:Activity * activity_select(int);};

Pojasnilo kode:

  1. 4. del - zadnji del definicije razreda načrtovalca.
  2. Funkcija za izbiro dejavnosti za osnovo vzame indeks izhodišča in pohlepno iskanje razdeli na pohlepne podprobleme.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Z uporabo operaterja ločljivosti obsega (: :) je na voljo definicija funkcije.
  2. Upoštevani indeks je indeks, ki se imenuje po vrednosti. Greedy_extent je inicializirano samo indeks za obravnavanim indeksom.
Activity * Scheduler :: activity_select(int considered_index){while( (greedy_extent < MAX_ACTIVITIES ) &&((this->current_activities[greedy_extent]).start.hours <(this->current_activities[considered_index]).finish.hours )){printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",(this->current_activities[greedy_extent]).start.hours,(this->current_activities[greedy_extent]).finish.hours,greedy_extent + 1);greedy_extent++;}… …

Pojasnilo kode:

  1. Bistvena logika - Pohlepni obseg je omejen na število dejavnosti.
  2. Začetne ure trenutne dejavnosti se preverijo kot razporejene, preden se obravnavana aktivnost (podana z upoštevanim indeksom) konča.
  3. Dokler je to mogoče, se natisne neobvezna izjava o odpravljanju napak.
  4. Prehod na naslednji indeks v nizu dejavnosti
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Pojasnilo kode:

  1. Pogojni pregled, ali so bile zajete vse dejavnosti.
  2. V nasprotnem primeru lahko pohlepno znova zaženete z upoštevanim indeksom kot trenutno točko. To je rekurziven korak, ki pohlepno razdeli stavek o težavi.
  3. Če je odgovor da, se vrne kličočemu, ki nima prostora za podaljšanje pohlepa.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Pojasnilo kode:

  1. Glavna funkcija, ki se uporablja za priklic načrtovalnika.
  2. Primeren je nov razporejevalnik.
  3. Funkcija za izbiro dejavnosti, ki vrne kazalec na vrsto dejavnosti, se po končanem pohlepnem iskanju vrne klicatelju.

Izhod:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Slabosti pohlepnih algoritmov

Ni primeren za pohlepne težave, kjer je za vsak podproblem, kot je razvrščanje, potrebna rešitev.

V takšnih težavah z vadbo pohlepnega algoritma je metoda pohlepna napačna; v najslabšem primeru celo privedejo do neoptimalne rešitve.

Pomanjkljivost pohlepnih algoritmov je zato, ker ne vemo, kaj je pred trenutnim pohlepnim stanjem.

Spodaj je prikaz pomanjkljivosti pohlepne metode:

V pohlepnem skeniranju, ki je tukaj prikazano kot drevo (višja vrednost višja pohlep), bo stanje algoritma pri vrednosti: 40 verjetno vzelo 29 kot naslednjo vrednost. Nadalje se njegovo iskanje konča ob 12. To znaša 41.

Če pa je algoritem ubral neoptimalno pot ali sprejel osvajalsko strategijo. potem bi 25 sledilo 40, skupno izboljšanje stroškov pa bi bilo 65, kar je za 24 točk višje kot neoptimalna odločitev.

Primeri pohlepnih algoritmov

Večina mrežnih algoritmov uporablja pohlepni pristop. Tu je seznam nekaj primerov pohlepnega algoritma:

  • Primov algoritem minimalnega raztezajočega se drevesa
  • Problem potujočega prodajalca
  • Graf - Barvanje zemljevida
  • Kruskalov algoritem minimalnega raztezajočega se drevesa
  • Dijkstrin algoritem minimalnega raztezajočega se drevesa
  • Graf - Pokrov vrha
  • Nahrbtnik problem
  • Problem razporejanja delovnih mest

Povzetek:

Če povzamem, je članek opredelil pohlepno paradigmo, pokazal, kako pohlepna optimizacija in rekurzija vam lahko pomagata do najboljše rešitve do določene točke. Pohlepni algoritem se pogosto uporablja za reševanje problemov v mnogih jezikih, kot je pohlepni algoritem Python, C, C #, PHP, Java itd. Izbira dejavnosti primera Pohlepnega algoritma je bila opisana kot strateški problem, ki bi lahko dosegel največjo pretočnost z uporabo pohlepnih pristop. Na koncu so bile razložene pomanjkljivosti uporabe pohlepnega pristopa.