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

Što je pohlepni algoritam?

A Pohlepni algoritam rekurzivno dijeli skup resursa na temelju maksimalne neposredne dostupnosti tog resursa u bilo kojoj fazi izvršavanja.

Rješavanje problema pohlepnim pristupom ima dvije faze:

1. Skeniranje popisa stavki
2. Optimizacija

Obje faze rade paralelno jer se ulazni niz progresivno dijeli.

Za praćenje pohlepnog pristupa, radno znanje o rekurziji i promjeni konteksta pomaže vam trace kod. Pohlepna paradigma može se opisati s parom nužnih i dovoljnih izjava.

Dva uvjeta definiraju pohlepnu paradigmu.

• Svaki postupni izbor mora usmjeriti problem prema njegovom najbolje prihvaćenom rješenju.
• Struktura problema mora se zaustaviti u konačnom broju pohlepnih koraka.

S obzirom na teoriju, pogledajmo povijest koja stoji iza pristupa pohlepnog pretraživanja.

Povijest Greedyja Algorithms

Evo važnih prekretnica u povijesti pohlepnih algoritama:

• Pohlepni algoritmi prvi su put konceptualizirani za algoritme hoda grafom 1950-ih.
• Edsger Dijkstra razvio je svoj algoritam najkraćeg puta kako bi skratio rute kroz nizozemski glavni grad Amsterdam.
• U istom desetljeću, Prim i Kruskal razvili su optimizacijske strategije koje minimiziraju troškove puta duž ponderiranih ruta kako bi izgradili minimalna razapinjujuća stabla.
• Sedamdesetih godina prošlog stoljeća, američki istraživači Cormen, Leiserson, Rivest i Stein opisali su rekurzivno substrukturiranje pohlepnih rješenja u svojim klasičnim Introduction to Algorithms udžbenik.
• Paradigma pohlepnog pretraživanja katalogizirana je kao zasebna strategija optimizacije u NIST zapisima 2005. godine.
• Do danas, web protokoli poput Open Shortest Path First (OSPF) i mnogi protokoli za komutaciju paketa koriste pohlepnu strategiju kako bi smanjili vrijeme tranzita kroz mrežu.

Pohlepne strategije i odluke

Logika se svodi na binarni izbor u svakoj fazi - "pohlepno" ili "nepohlepno" - na temelju smjera u kojem algoritam napreduje.

Na primjer, Dijkstrin algoritam identificira hostove na internetu procjenjujući funkciju troška u svakom koraku. Vrijednost koju funkcija troška vraća odlučuje je li sljedeći put „pohlepni“ ili „nepohlepni“.

Ukratko, algoritam prestaje biti pohlepni u trenutku kada napravi korak koji nije lokalno optimalan, a pohlepni problemi se zaustavljaju kada nijedan daljnji pohlepni korak nije moguć.

Karakteristike pohlepnog algoritma

Važne karakteristike Greedy algoritma su:

• Uređeni popis resursa nosi atribucije troškova ili vrijednosti koje kvantificiraju ograničenja sustava.
• Algoritam uzima maksimalnu količinu resursa unutar vremena za koje se primjenjuje ograničenje.
• Na primjer, u problemu raspoređivanja aktivnosti troškovi resursa mjere se u satima, a aktivnosti se moraju izvršavati serijskim redoslijedom.

Zašto koristiti pohlepni pristup?

Evo razloga za korištenje pohlepnog pristupa:

• Pohlepni pristup ima kompromise koji ga čine pogodnim za optimizaciju.
• Najočitiji razlog je odmah pronaći izvedivo rješenje. U problemu odabira aktivnosti o kojem će se raspravljati u nastavku, ako se prije završetka trenutne aktivnosti uklopi više aktivnosti, one se mogu zakazati u istom prozoru.
• Drugi razlog je taj što rekurzivno dijeli problem na temelju uvjeta, bez potrebe za spajanjem podrješenja.
• U problemu odabira aktivnosti, korak rekurzivnog dijeljenja postiže se jednim skeniranjem popisa i razmatranjem samo prihvatljivih aktivnosti.

Kako riješiti problem odabira aktivnosti

U primjeru raspoređivanja aktivnosti, svaka aktivnost ima vrijeme početka i završetka te je indeksirana brojem za referencu. Postoje dvije kategorije aktivnosti:

1. Razmatrana aktivnost: referentna aktivnost iz koje se mjeri sposobnost prilagođavanja preostalih aktivnosti.
2. Preostale aktivnosti: aktivnosti na jednom ili više indeksa ispred razmatrane aktivnosti.

Trošak obavljanja aktivnosti je njezino trajanje, izračunato kao (kraj - početak).

Pohlepni opseg je jednostavno broj preostalih aktivnosti koje se mogu izvršiti unutar vremena razmatrane aktivnosti.

Architektura pohlepnog pristupa

Korak 1) Pregledajte popis troškova aktivnosti počevši od indeksa 0 kao razmatranog indeksa.

Korak 2) Kada se do završetka razmatrane aktivnosti može završiti više aktivnosti, potražite preostale aktivnosti.

Korak 3) Ako se ne mogu zakazati daljnje aktivnosti, trenutna preostala aktivnost postaje sljedeća razmatrana aktivnost. Ponovite 1. i 2. korak s novom razmatranom aktivnošću. Ako ne preostane nijedna aktivnost, prijeđite na 4. korak.

Korak 4) Vrati uniju razmatranih indeksa - to su indeksi aktivnosti koji maksimiziraju propusnost.

Architektura pohlepnog pristupa

Code Objašnjenje

#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 može konfigurirati.

using namespace std;

class TIME
{
    public:
    int hours;

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

Objašnjenje koda:

1. Deklarira standardni imenski prostor 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 za aktivnost.
2. Vremenske oznake koje zajedno definiraju trajanje.
3. Sve vremenske oznake su inicijalizirane 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. considered_index je početna točka za skeniranje niza.
3. init_index se koristi za dodjeljivanje nasumičnih vremenskih oznaka tijekom postavljanja.
4. Niz objekata Activity dinamički se dodjeljuje s operatorom new.
5. Planirani pokazivač sadrži trenutni pohlepni rezultat.

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

Objašnjenje koda:

1. Konstruktor raspoređivača — 2. dio definicije klase.
2. considered_index označava početak trenutnog skeniranja.
3. Pohlepni opseg je na početku nedefiniran.

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);
 }
&#8230;
&#8230;

Objašnjenje koda:

1. Petlja for inicijalizira početne i završne sate svake planirane aktivnosti.
2. Inicijalizira vrijeme početka.
3. Inicijalizira vrijeme završetka tako da bude u ili nakon sata početka.
4. Debug naredba ispisuje dodijeljena trajanja.

	public:
   		 Activity * activity_select(int);
};

Objašnjenje koda:

1. Dio 4 — završni dio definicije klase Scheduler.
2. activity_select() uzima početni indeks kao bazu i dijeli pohlepni zadatak na podprobleme.

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

1. Operator razlučivanja opsega (::) povezuje definiciju funkcije s klasom Scheduler.
2. considered_index se prosljeđuje po vrijednosti, a greedy_extent se inicijalizira na indeks odmah nakon njega.

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++;
    	}
&#8230;
...

Objašnjenje koda:

1. Osnovna logika — pohlepni opseg je ograničen na MAX_ACTIVITIES.
2. Početni sat trenutne aktivnosti uspoređuje se sa završnim satom razmatrane aktivnosti.
3. Dok je uvjet zadovoljen, ispisuje se opcionalna naredba za otklanjanje grešaka.
4. Pohlepni opseg zatim prelazi na sljedeći indeks u nizu aktivnosti.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Objašnjenje koda:

1. Uvjet provjerava jesu li sve aktivnosti obuhvaćene.
2. Ako ne, algoritam ponovno pokreće pohlepnu potragu od trenutnog indeksa - rekurzivni korak koji pohlepno dijeli problem.
3. Ako je odgovor da, kontrola se vraća 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 poziva Planer.
2. Stvara se instanca novog objekta Scheduler.
3. Funkcija activity_select() vraća pokazivač aktivnosti pozivatelju nakon što pohlepni zadatak završi.

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

Pohlepni pristup nije prikladan za probleme koji zahtijevaju optimalno rješenje za svaki podproblem, kao što je sortiranje.

U takvim slučajevima pohlepna metoda može biti pogrešna - u najgorem slučaju daje neoptimalno rješenje.

Osnovni nedostatak pohlepnih algoritama je taj što biraju bez znanja što ih čeka u trenutnom pohlepnom stanju.

Donji dijagram ilustrira ovaj nedostatak pohlepne metode.

U pohlepnom skeniranju prikazanom ovdje kao stablo (viša vrijednost znači veću pohlepnost), algoritam s vrijednosti 40 bi sljedeće odabrao 29, a zatim završio na 12, za ukupno 41.

Nasuprot tome, strategija "zavadi pa vladaj" slijedila bi 25 s 40 za ukupno 65, što je 24 boda više od lokalno pohlepnog izbora.

Primjeri za Greedy Algorithms

Većina mrežnih algoritama oslanja se na pohlepni pristup. Uobičajeni primjeri pohlepnih algoritama uključuju:

• Primov algoritam minimalnog rasponskog stabla
• Problem trgovačkog putnika (približno)
• Bojanje grafova i mapa
• Kruskalov algoritam minimalnog rasponskog stabla
• Dijkstrin algoritam najkraćeg puta
• Pokriće vrha grafa
• Problem s naprtnjačom
• Redoslijed poslova s ​​rokovima

Pitanja i odgovori