Pohlepni algoritam s primjerom: što je, metoda i pristup

Da biste razumjeli pohlepni pristup, morat ćete imati radno znanje o rekurziji i prebacivanju konteksta. Ovo vam pomaže da razumijete kako pratiti kod. Možete definirati pohlepnu paradigmu u smislu vlastitih nužnih i dovoljnih izjava.

Dva uvjeta definiraju pohlepnu paradigmu.

• Svako postupno 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.

Uz nastavak teoretiziranja, opišimo povijest povezanu s Greedy search pristupom.

Povijest Greedyja Algorithms

Ovdje je važan orijentir pohlepnih algoritama:

• Pohlepni algoritmi su konceptualizirani za mnoge algoritme hodanja po grafovima 1950-ih.
• Esdger Djikstra konceptualizirao je algoritam za generiranje minimalnih razapinjućih stabala. Namjeravao je skratiti raspon ruta unutar nizozemske prijestolnice Amsterdama.
• U istom desetljeću, Prim i Kruskal postigli su strategije optimizacije koje su se temeljile na minimiziranju troškova puta duž izvaganih ruta.
• U 70-ima su američki istraživači Cormen, Rivest i Stein predložili rekurzivno substrukturiranje pohlepnih rješenja u svojoj klasičnoj knjizi Uvod u algoritme.
• Paradigma pohlepnog pretraživanja registrirana je kao drugačija vrsta optimizacijske strategije u zapisima NIST-a 2005.
• Do danas, protokoli koji pokreću web, kao što je open-shortest-path-first (OSPF) i mnogi drugi protokoli za prebacivanje mrežnih paketa koriste pohlepnu strategiju za smanjenje vremena provedenog na mreži.

Pohlepne strategije i odluke

Logika se u svom najlakšem obliku svela na "pohlepan" ili "nepohlepan". Ove izjave definirane su pristupom poduzetim za napredovanje u svakoj fazi algoritma.

Na primjer, Djikstrin algoritam koristio je postupnu pohlepnu strategiju identificiranja hostova na Internetu izračunavanjem troškovne funkcije. Vrijednost koju je vratila funkcija troška odredila 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 prestaju bez daljnjeg opsega pohlepe.

Karakteristike pohlepnog algoritma

Važne karakteristike Greedy algoritma su:

• Postoji poredani popis resursa, s pripisivanjem troškova ili vrijednosti. Oni kvantificiraju ograničenja sustava.
• Uzet ćete maksimalnu količinu resursa u vremenu na koje se primjenjuje ograničenje.
• Na primjer, u problemu raspoređivanja aktivnosti, troškovi resursa su u satima, a aktivnosti se moraju izvoditi u nizu.

Zašto koristiti pohlepni pristup?

Evo razloga za korištenje pohlepnog pristupa:

• Pohlepni pristup ima nekoliko nedostataka, koji ga mogu učiniti prikladnim za optimizaciju.
• Jedan od istaknutih razloga je postizanje najizvedivijeg rješenja odmah. U problemu odabira aktivnosti (objašnjeno u nastavku), ako se više aktivnosti može obaviti prije završetka trenutne aktivnosti, te se aktivnosti mogu izvesti unutar istog vremena.
• Drugi razlog je rekurzivna podjela problema na temelju uvjeta, bez potrebe za kombiniranjem svih rješenja.
• U problemu odabira aktivnosti, korak "rekurzivne podjele" postiže se skeniranjem popisa stavki samo jednom i razmatranjem određenih aktivnosti.

Kako riješiti problem odabira aktivnosti

U primjeru rasporeda aktivnosti postoji vrijeme "početka" i "završetka" za svaku aktivnost. Svaka aktivnost je 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 na jednom ili više indeksa ispred razmatrane aktivnosti.

Ukupno trajanje daje trošak obavljanja aktivnosti. To jest (završiti – započeti) daje nam trajanje kao trošak aktivnosti.

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

Archistruktura Greedy pristupa

KORAK 1) Skenirajte popis troškova aktivnosti, počevši od indeksa 0 kao razmatranog indeksa.

KORAK 2) Kada se više aktivnosti može završiti do vremena kada razmatrana aktivnost završi, počnite tražiti jednu ili više preostalih aktivnosti.

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

KORAK 4) Vrati uniju razmatranih indeksa. Ovo su indeksi aktivnosti koji će se koristiti za maksimiziranje propusnosti.

Objašnjenje koda

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Objašnjenje koda:

1. Uključene datoteke zaglavlja/klase
2. Maksimalan broj aktivnosti koje korisnik nudi.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Objašnjenje koda:

1. Prostor imena za operacije strujanja.
2. Definicija klase za TIME
3. Vremenska oznaka od sat vremena.
4. TIME zadani konstruktor
5. Varijabla sati.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Objašnjenje koda:

1. Definicija klase iz aktivnosti
2. Vremenske oznake koje definiraju trajanje
3. Sve vremenske oznake inicijalizirane su 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. Razmatrani indeks je početna točka za skeniranje poredak.
3. Indeks inicijalizacije koristi se za dodjeljivanje nasumičnih vremenskih oznaka.
4. Niz objekata aktivnosti dinamički se dodjeljuje pomoću novog operatora.
5. Zakazani pokazivač definira trenutnu baznu lokaciju za pohlepu.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Objašnjenje koda:

1. Konstruktor planera – 2. dio definicije klase planera.
2. Razmatrani indeks definira trenutni početak trenutnog skeniranja.
3. Trenutačni pohlepni opseg je nedefiniran na početku.

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četnih i završnih sati svake od trenutno planiranih aktivnosti.
2. Inicijalizacija vremena početka.
3. Inicijalizacija vremena završetka uvijek nakon ili točno u sat početka.
4. Debug izjava za ispis dodijeljenih trajanja.

	public:
   		 Activity * activity_select(int);
};

Objašnjenje koda:

1. Dio 4 – zadnji dio definicije klase planera.
2. Funkcija odabira aktivnosti uzima indeks početne točke kao bazu i dijeli pohlepnu potragu na pohlepne podprobleme.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
… 

1. Korištenjem operatora rezolucije opsega (::), daje se definicija funkcije.
2. Razmatrani indeks je indeks pozvan prema vrijednosti. Greedy_extent je inicijaliziran samo indeks nakon razmatranog indeksa.

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. Temeljna logika - Pohlepni opseg ograničen je na broj aktivnosti.
2. Početni sati trenutne aktivnosti provjeravaju se kao planirani prije nego što razmatrana aktivnost (navedena razmatranim indeksom) završi.
3. Sve dok je to moguće, ispisuje se neobavezna izjava o otklanjanju pogrešaka.
4. Prijeđi na sljedeći indeks u nizu aktivnosti

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Objašnjenje koda:

1. Kondicional provjerava jesu li obuhvaćene sve aktivnosti.
2. Ako ne, možete ponovno pokrenuti svoj greedy s razmatranim indeksom kao trenutnom točkom. Ovo je rekurzivan korak koji pohlepno dijeli iskaz problema.
3. Ako da, vraća se pozivatelju bez mogućnosti š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. Instancira se novi planer.
3. Funkcija odabira aktivnosti, koja vraća pokazivač tipa, aktivnost se vraća pozivatelju nakon završetka pohlepne potrage.

Izlaz:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

Ograničenja pohlepne tehnike

Nije prikladan za pohlepne probleme gdje je potrebno rješenje za svaki podproblem poput sortiranja.

U takvim praktičnim problemima Greedy algoritma, Greedy metoda može biti pogrešna; u najgorem slučaju dovesti do neoptimalnog rješenja.

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

Ispod je prikaz nedostataka Greedy metode:

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

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

Primjeri za Greedy Algorithms

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

• Primov algoritam minimalnog razapinjućeg stabla
• Problem putujućeg trgovca
• Grafikon – Bojanje karte
• Kruskalov algoritam minimalnog razapinjućeg stabla
• Dijkstrin algoritam minimalnog razapinjućeg stabla
• Graf – Vertex Cover
• Problem s naprtnjačom
• Problem s rasporedom poslova

Rezime

Ukratko, članak je definirao pohlepnu paradigmu, pokazao kako vam pohlepna optimizacija i rekurzija mogu pomoći da dobijete najbolje rješenje do određene točke. Greedy algoritam široko se primjenjuje za rješavanje problema u mnogim jezicima kao Greedy algoritam Python, C, C#, PHP, Java, itd. Primjer odabira aktivnosti Greedy algoritma opisan je kao strateški problem koji bi mogao postići maksimalnu propusnost koristeći greedy pristup. Na kraju su objašnjeni nedostaci korištenja pohlepnog pristupa.