Pohlepni algoritam s primjerima: Pohlepna metoda & Pristup

Sadržaj:

Anonim

Što je pohlepni algoritam?

U pohlepnom algoritmu skup resursa se rekurzivno dijeli na temelju maksimalne, neposredne dostupnosti tog resursa u bilo kojoj fazi izvršenja.

Postoje dvije faze za rješavanje problema temeljenog na pohlepnom pristupu

  1. Skeniranje popisa stavki
  2. Optimizacija

Te su faze paralelno obrađene u ovom uputstvu za pohlepni algoritam, o toku podjele niza.

Da biste razumjeli pohlepni pristup, morat ćete imati radno znanje o rekurziji i prebacivanju konteksta. To vam pomaže da razumijete kako pronaći kod. Pohlepnu paradigmu možete definirati u smislu vlastitih potrebnih i dovoljnih izjava.

Dva uvjeta definiraju pohlepnu paradigmu.

  • Svako postepeno rješenje mora strukturirati problem prema svom najbolje prihvaćenom rješenju.
  • Dovoljno je ako se strukturiranje problema može zaustaviti u konačnom broju pohlepnih koraka.

Nastavkom teoretiziranja, opišimo povijest povezanu s pristupom pohlepnog pretraživanja.

U ovom uputstvu za pohlepni algoritam naučit ćete:

  • Povijest pohlepnih algoritama
  • Pohlepne strategije i odluke
  • Karakteristike pohlepnog pristupa
  • Zašto koristiti pohlepni pristup?
  • Kako riješiti problem odabira aktivnosti
  • Arhitektura pohlepnog pristupa
  • Mane pohlepnih algoritama

Povijest pohlepnih algoritama

Ovdje je važan orijentir pohlepnih algoritama:

  • Pohlepni algoritmi koncipirani su za mnoge algoritme šetnje grafom u 1950-ima.
  • Esdger Djikstra konceptualizirao je algoritam za generiranje minimalno rasprostranjenih stabala. Cilj mu je bio skratiti raspon ruta u nizozemskom glavnom gradu Amsterdamu.
  • U istom desetljeću Prim i Kruskal postigli su strategije optimizacije koje su se temeljile na umanjivanju troškova puta duž vaganih ruta.
  • Sedamdesetih godina američki istraživači, Cormen, Rivest i Stein predložili su rekurzivno potkonstruiranje pohlepnih rješenja u svom klasičnom uvodu u knjigu algoritama.
  • Paradigma pohlepnog pretraživanja registrirana je kao druga vrsta strategije optimizacije u evidencijama NIST-a 2005. godine.
  • Do danas, protokoli koji pokreću mrežu, poput otvorenog najkraćeg puta (OSPF) i mnogi drugi protokoli za prebacivanje mrežnih paketa koriste pohlepnu strategiju kako bi smanjili vrijeme provedeno na mreži.

Pohlepne strategije i odluke

Logika se u svom najlakšem obliku svodila na "pohlepno" ili "ne pohlepno". Te su izjave definirane pristupom za napredovanje u svakoj fazi algoritma.

Na primjer, Djikstrin algoritam koristio je postupno pohlepnu strategiju identificiranja hostova na Internetu izračunavanjem funkcije troškova. Vrijednost koju je vratila funkcija troškova odredila je je li sljedeći put "pohlepan" ili "nepohlepan".

Ukratko, algoritam prestaje biti pohlepan ako u bilo kojoj fazi poduzme korak koji nije lokalno pohlepan. Pohlepni problemi se zaustavljaju bez daljnjeg opsega pohlepe.

Karakteristike pohlepnog pristupa

Važne karakteristike algoritma pohlepne metode su:

  • Postoji poredani popis resursa s atributima troškova ili vrijednosti. To kvantificiraju ograničenja na sustavu.
  • Uzet ćete maksimalnu količinu resursa u vremenu kada se primjenjuje ograničenje.
  • Na primjer, u problemu zakazivanja aktivnosti, troškovi resursa izraženi su u satima, a aktivnosti se trebaju izvoditi serijskim redoslijedom.

Zašto koristiti pohlepni pristup?

Evo razloga za pohlepni pristup:

  • Pohlepni pristup ima nekoliko kompromisa, što ga može učiniti prikladnim za optimizaciju.
  • Jedan od istaknutih razloga je hitno postizanje najprovodivijeg rješenja. U problemu odabira aktivnosti (Objašnjeno u nastavku), ako se prije završetka trenutne aktivnosti može obaviti više aktivnosti, te se aktivnosti mogu obaviti u isto vrijeme.
  • Drugi je razlog rekurzivno dijeljenje problema na temelju stanja, bez potrebe za kombiniranjem svih rješenja.
  • U problemu odabira aktivnosti, korak "rekurzivna podjela" postiže se skeniranjem popisa stavki samo jednom i uzimanjem u obzir određenih aktivnosti.

Kako riješiti problem odabira aktivnosti

U primjeru zakazivanja aktivnosti postoji vrijeme "početka" i "završetka" za svaku aktivnost. Svaka je aktivnost indeksirana brojem za referencu. Postoje dvije kategorije aktivnosti.

  1. razmatrana aktivnost : je aktivnost, koja je referenca iz koje se analizira sposobnost obavljanja više od jedne preostale aktivnosti.
  2. preostale aktivnosti: aktivnosti s jednim ili više indeksa ispred razmatrane aktivnosti.

Ukupno trajanje daje troškove obavljanja djelatnosti. To jest (završi - započni) daje nam trajanje kao trošak aktivnosti.

Naučit ćete da je pohlepni opseg broj preostalih aktivnosti koje možete obavljati u vrijeme razmatrane aktivnosti.

Arhitektura pohlepnog pristupa

KORAK 1)

Skenirajte popis troškova aktivnosti, počevši s indeksom 0 kao razmatranim indeksom.

KORAK 2)

Kada se do trenutka može završiti više aktivnosti, razmatrana aktivnost završi, započnite s traženjem jedne ili više preostalih aktivnosti.

KORAK 3)

Ako više nema preostalih aktivnosti, trenutna preostala aktivnost postaje sljedeća razmatrana aktivnost. Ponovite 1. i 2. korak s novom razmatranom aktivnošću. Ako nema preostalih aktivnosti, prijeđite na korak 4.

KORAK 4)

Vrati uniju razmatranih indeksa. To su indeksi aktivnosti koji će se koristiti za maksimaliziranje protoka.

Arhitektura pohlepnog pristupa

Objašnjenje koda

#include#include#include#define MAX_ACTIVITIES 12

Objašnjenje koda:

  1. Uključene datoteke / klase zaglavlja
  2. Maksimalan broj aktivnosti koje pruža korisnik.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Objašnjenje koda:

  1. Prostor imena za streaming operacije.
  2. Definicija klase za VRIJEME
  3. Oznaka sata.
  4. TIME zadani konstruktor
  5. Promjenjiva sati.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Objašnjenje koda:

  1. Definicija razreda iz aktivnosti
  2. Vremenske oznake koje definiraju trajanje
  3. Sve vremenske oznake inicijaliziraju se na 0 u zadanom konstruktoru
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Objašnjenje koda:

  1. Dio 1 definicije klase planera.
  2. Smatrani indeks početna je točka za skeniranje niza.
  3. Indeks inicijalizacije koristi se za dodjeljivanje slučajnih vremenskih oznaka.
  4. Niz objekata aktivnosti dinamički se dodjeljuje pomoću novog operatora.
  5. Zakazani pokazivač definira trenutno osnovno mjesto za pohlepu.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Objašnjenje koda:

  1. Konstruktor planera - dio 2 definicije klase planera.
  2. Razmatrani indeks definira trenutni početak trenutnog skeniranja.
  3. Trenutni pohlepni opseg na početku nije definiran.
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);}… …

Objašnjenje koda:

  1. Petlja for za inicijalizaciju početnog i završnog vremena svake od trenutno planiranih aktivnosti.
  2. Inicijalizacija vremena početka.
  3. Inicijalizacija vremena završetka uvijek nakon ili točno na početnom satu.
  4. Izjava o otklanjanju pogrešaka za ispis dodijeljenih trajanja.
public:Activity * activity_select(int);};

Objašnjenje koda:

  1. Dio 4 - posljednji dio definicije klase planera.
  2. Funkcija odabira aktivnosti uzima indeks početne točke kao osnovu i dijeli pohlepnu potragu u pohlepne potprobleme.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Koristeći operator razlučivosti opsega (: :), pružena je definicija funkcije.
  2. Razmatrani indeks je indeks koji se naziva vrijednošću. Greedy_extent je inicijalizirani samo indeks nakon razmatranog Indexa.
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++;}… …

Objašnjenje koda:

  1. Osnovna logika - Pohlepni opseg ograničen je na broj aktivnosti.
  2. Početni sati trenutne Aktivnosti provjeravaju se kao planirani prije nego što će razmatrana Aktivnost (dana razmatranim indeksom) završiti.
  3. Sve dok je to moguće, ispisuje se neobavezna izjava za otklanjanje pogrešaka.
  4. Prelazak na sljedeći indeks na polju aktivnosti
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Objašnjenje koda:

  1. Uvjetna provjera jesu li obuhvaćene sve aktivnosti.
  2. Ako ne, možete ponovno pokrenuti svog pohlepnika s razmatranim indeksom kao trenutnom točkom. Ovo je rekurzivni korak koji pohlepno dijeli stav o problemu.
  3. Ako je odgovor da, vraća se pozivatelju bez mogućnosti proširenja pohlepe.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Objašnjenje koda:

  1. Glavna funkcija koja se koristi za pozivanje planera.
  2. Instanciran je novi rokovnik.
  3. Funkcija odabira aktivnosti, koja vraća pokazivač na aktivnost tipa, vraća se pozivatelju nakon završetka pohlepne potrage.

Izlaz:

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

Mane pohlepnih algoritama

Nije prikladno za pohlepne probleme gdje je rješenje potrebno za svaki potproblem poput sortiranja.

U takvim problemima prakse pohlepnog algoritma, pohlepna metoda može biti pogrešna; u najgorem slučaju čak dovesti do neoptimalnog rješenja.

Stoga je nedostatak pohlepnih algoritama korištenje neznanja što je ispred trenutnog pohlepnog stanja.

Ispod je prikaz nedostatka pohlepne metode:

U pohlepnom skeniranju prikazanom ovdje kao stablo (veća pohlepa veće vrijednosti), stanje algoritma na vrijednosti: 40, vjerojatno će uzeti 29 kao sljedeću vrijednost. Dalje, njegova potraga završava u 12. To iznosi vrijednost 41.

Međutim, ako je algoritam krenuo neoptimalno ili je usvojio strategiju osvajanja. tada bi 25 slijedilo 40, a ukupno poboljšanje troškova bilo bi 65, što se procjenjuje za 24 boda kao neoptimalna odluka.

Primjeri pohlepnih algoritama

Većina mrežnih algoritama koristi pohlepni pristup. Evo popisa nekoliko primjera pohlepnog algoritma:

  • Primov algoritam minimalnog raspona stabla
  • Problem putujućeg trgovca
  • Grafikon - bojanje karte
  • Kruskalov algoritam minimalnog raspona stabala
  • Dijkstrin algoritam minimalnog raspona stabala
  • Grafikon - Vertex Cover
  • Ruksak problem
  • Problem raspoređivanja poslova

Sažetak:

Da rezimiramo, članak je definirao pohlepnu paradigmu, pokazao kako pohlepna optimizacija i rekurzija mogu vam pomoći da dobijete najbolje rješenje do određene točke. Pohlepni algoritam široko je primijenjen na rješavanju problema na mnogim jezicima kao Pohlepni algoritam Python, C, C #, PHP, Java itd. Odabir aktivnosti primjera Pohlepnog algoritma opisan je kao strateški problem koji može postići maksimalnu propusnost koristeći pohlepne pristup. Na kraju su objašnjene mane upotrebe pohlepnog pristupa.