Grådig algoritme med eksempel: Hvad er, metode og tilgang

For at forstå den grådige tilgang skal du have et praktisk kendskab til rekursion og kontekstskifte. Dette hjælper dig med at forstå, hvordan du sporer koden. Du kan definere det grådige paradigme ud fra dine egne nødvendige og tilstrækkelige udsagn.

To forhold definerer det grådige paradigme.

• Hver trinvis løsning skal strukturere et problem hen imod den bedst accepterede løsning.
• Det er tilstrækkeligt, hvis struktureringen af ​​problemet kan stoppe i et begrænset antal grådige trin.

Med teoretiseringen fortsat, lad os beskrive historien forbundet med den grådige søgetilgang.

Grådigheds historie Algorithms

Her er et vigtigt vartegn for grådige algoritmer:

• Grådige algoritmer blev konceptualiseret for mange grafgangalgoritmer i 1950'erne.
• Esdger Djikstra konceptualiserede algoritmen til at generere minimale spændingstræer. Han havde til formål at forkorte spændvidden af ​​ruter inden for den hollandske hovedstad, Amsterdam.
• I samme årti opnåede Prim og Kruskal optimeringsstrategier, der var baseret på at minimere stiomkostninger langs vejede ruter.
• I 70'erne foreslog amerikanske forskere, Cormen, Rivest og Stein en rekursiv substrukturering af grådige løsninger i deres klassiske introduktion til algoritmer.
• Det grådige søgeparadigme blev registreret som en anden type optimeringsstrategi i NIST-posterne i 2005.
• Indtil nu bruger protokoller, der kører på nettet, såsom open-shortest-path-first (OSPF) og mange andre netværkspakkeskifteprotokoller den grådige strategi til at minimere tid brugt på et netværk.

Grådige strategier og beslutninger

Logik i sin nemmeste form blev kogt ned til "grådig" eller "ikke grådig". Disse udsagn blev defineret af den tilgang, der blev taget for at komme videre i hvert algoritmetrin.

For eksempel brugte Djikstras algoritme en trinvis grådig strategi, der identificerede værter på internettet ved at beregne en omkostningsfunktion. Den værdi, som omkostningsfunktionen returnerede, bestemte, om den næste sti er "grådig" eller "ikke-grådig".

Kort sagt ophører en algoritme med at være grådig, hvis den på noget tidspunkt tager et skridt, der ikke er lokalt grådig. De grådige problemer stopper uden yderligere omfang af grådighed.

Karakteristika for den grådige algoritme

De vigtige egenskaber ved en grådig algoritme er:

• Der er en ordnet liste over ressourcer med omkostninger eller værditilskrivninger. Disse kvantificerer begrænsninger på et system.
• Du vil tage den maksimale mængde ressourcer i den tid, en begrænsning gælder.
• For eksempel i et aktivitetsplanlægningsproblem er ressourceomkostningerne i timer, og aktiviteterne skal udføres i seriel rækkefølge.

Hvorfor bruge den grådige tilgang?

Her er grundene til at bruge den grådige tilgang:

• Den grådige tilgang har et par afvejninger, som kan gøre den velegnet til optimering.
• En fremtrædende årsag er at opnå den mest gennemførlige løsning med det samme. I aktivitetsudvælgelsesproblemet (forklaret nedenfor), hvis flere aktiviteter kan udføres, før den aktuelle aktivitet afsluttes, kan disse aktiviteter udføres inden for samme tid.
• En anden grund er at opdele et problem rekursivt baseret på en tilstand uden behov for at kombinere alle løsninger.
• I aktivitetsudvælgelsesproblemet opnås trinnet "rekursiv opdeling" ved kun at scanne en liste over elementer én gang og overveje bestemte aktiviteter.

Sådan løses problemet med valg af aktivitet

I eksemplet med aktivitetsplanlægning er der en "start" og "sluttid" for hver aktivitet. Hver aktivitet er indekseret med et nummer til reference. Der er to aktivitetskategorier.

1. betragtes som aktivitet: er aktiviteten, som er referencen, hvorfra evnen til at udføre mere end én resterende aktivitet analyseres.
2. resterende aktiviteter: aktiviteter på et eller flere indekser forud for den betragtede aktivitet.

Den samlede varighed angiver omkostningerne ved at udføre aktiviteten. Det vil sige (afslut – start) giver os varigheden som omkostningerne ved en aktivitet.

Du vil lære, at det grådige omfang er antallet af resterende aktiviteter, du kan udføre på tidspunktet for en overvejet aktivitet.

Architeori om den grådige tilgang

TRIN 1) Scan listen over aktivitetsomkostninger, startende med indeks 0 som det betragtede indeks.

TRIN 2) Når flere aktiviteter kan afsluttes til tiden, afsluttes den betragtede aktivitet. Begynd at søge efter en eller flere resterende aktiviteter.

TRIN 3) Hvis der ikke er flere resterende aktiviteter, bliver den aktuelle resterende aktivitet den næste betragtede aktivitet. Gentag trin 1 og trin 2 med den nye overvejede aktivitet. Hvis der ikke er nogen resterende aktiviteter tilbage, skal du gå til trin 4.

TRIN 4) Returner foreningen af ​​betragtede indekser. Dette er de aktivitetsindeks, der vil blive brugt til at maksimere gennemløbet.

Kode Forklaring

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

#define MAX_ACTIVITIES 12

Forklaring af kode:

1. Inkluderede header-filer/klasser
2. Et maks. antal aktiviteter leveret af brugeren.

using namespace std;

class TIME
{
    public:
    int hours;

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

Forklaring af kode:

1. Navneområdet for streaminghandlinger.
2. En klassedefinition for TID
3. Et times tidsstempel.
4. En TIME standard konstruktør
5. Timerne varierer.

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

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

Forklaring af kode:

1. En klassedefinition fra aktivitet
2. Tidsstempler, der definerer en varighed
3. Alle tidsstempler initialiseres til 0 i standardkonstruktøren

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Forklaring af kode:

1. Del 1 af planlægningsklassens definition.
2. Betragtet indeks er udgangspunktet for scanning af matrix.
3. Initialiseringsindekset bruges til at tildele tilfældige tidsstempler.
4. En række aktivitetsobjekter allokeres dynamisk ved hjælp af den nye operator.
5. Den planlagte markør definerer den aktuelle basisplacering for grådighed.

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

Forklaring af kode:

1. Schedulægger-konstruktøren – del 2 af skemalæggerklassens definition.
2. Det betragtede indeks definerer den aktuelle start af den aktuelle scanning.
3. Det nuværende grådige omfang er udefineret i starten.

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);
 }
…
…

Forklaring af kode:

1. En for-løkke for at initialisere start- og sluttimer for hver af de aktiviteter, der aktuelt er planlagt.
2. Starttidsinitialisering.
3. Initialisering af sluttidspunkt altid efter eller nøjagtigt ved starttimen.
4. En fejlretningserklæring til at udskrive tildelte varigheder.

	public:
   		 Activity * activity_select(int);
};

Forklaring af kode:

1. Del 4 – den sidste del af planlægningsklassens definition.
2. Aktivitetsvalgsfunktionen tager udgangspunkt i et startpunktsindeks og opdeler den grådige mission i grådige underproblemer.

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

1. Ved at bruge scope resolution operatoren (::) er funktionsdefinitionen tilvejebragt.
2. Det betragtede indeks er det indeks, der kaldes efter værdi. Greedy_extent er den initialiserede blot et indeks efter det betragtede indeks.

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++;
    	}
…
...

Forklaring af kode:

1. Kernelogikken- Det grådige omfang er begrænset til antallet af aktiviteter.
2. Starttimerne for den aktuelle aktivitet kontrolleres som planlagt, før den betragtede aktivitet (givet af det betragtede indeks) ville afslutte.
3. Så længe dette er muligt, udskrives en valgfri debug-sætning.
4. Gå videre til næste indeks på aktivitetsarrayet

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Forklaring af kode:

1. Den betingede kontrollerer, om alle aktiviteterne er dækket.
2. Hvis ikke, kan du genstarte din grådige med det betragtede indeks som det aktuelle punkt. Dette er et rekursivt skridt, der grådigt deler problemformuleringen.
3. Hvis ja, vender den tilbage til den, der ringer, uden mulighed for at udvide grådighed.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Forklaring af kode:

1. Hovedfunktionen, der bruges til at kalde skemalæggeren.
2. En ny Scheduler er instantieret.
3. Aktivitetsvalgsfunktionen, som returnerer en pointer af typen aktivitet, vender tilbage til den, der ringer, efter at den grådige mission er slut.

Output:

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

Begrænsninger af Greedy Technique

Det er ikke egnet til grådige problemer, hvor der kræves en løsning for hvert delproblem som sortering.

I sådanne Greedy-algoritmeøvelsesproblemer kan Greedy-metoden være forkert; i værste fald endda føre til en ikke-optimal løsning.

Derfor er ulempen ved grådige algoritmer at bruge ikke at vide, hvad der ligger forud for den nuværende grådige tilstand.

Nedenfor er en skildring af ulempen ved den grådige metode:

I den grådige scanning vist her som et træ (højere værdi højere grådighed), vil en algoritmetilstand ved værdi: 40 sandsynligvis tage 29 som den næste værdi. Ydermere slutter dens mission ved 12. Dette svarer til en værdi på 41.

Men hvis algoritmen tog en suboptimal vej eller vedtog en erobringsstrategi. så ville 25 blive efterfulgt af 40, og den samlede omkostningsforbedring ville være 65, hvilket vurderes 24 point højere som en suboptimal beslutning.

Eksempler på Greedy Algorithms

De fleste netværksalgoritmer bruger den grådige tilgang. Her er en liste over nogle eksempler på grådige algoritmer:

• Prims Minimal Spanning Tree Algorithm
• Rejsende sælgerproblem
• Graf – Kortfarvelægning
• Kruskals Minimal Spanning Tree Algorithm
• Dijkstras Minimal Spanning Tree Algorithm
• Graf – Vertex Cover
• Rullesæk problem
• Jobplanlægningsproblem

Resumé

For at opsummere, definerede artiklen det grådige paradigme, viste hvordan grådig optimering og rekursion kan hjælpe dig med at opnå den bedste løsning indtil et punkt. Den grådige algoritme er almindeligt anvendt til problemløsning på mange sprog som grådig algoritme Python, C, C#, PHP, Javaosv. Aktivitetsvalget af Greedy-algoritmeeksemplet blev beskrevet som et strategisk problem, der kunne opnå maksimal gennemstrømning ved at bruge den grådige tilgang. Til sidst blev ulemperne ved brugen af ​​den grådige tilgang forklaret.