Grådig algoritme med eksempler: grådig metode & tilgang

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

to betingelser definerer det grådige paradigme.

• hver trinvis løsning skal strukturere et problem mod sin bedst accepterede løsning.
• det er tilstrækkeligt, hvis struktureringen af problemet kan standse i et begrænset antal grådige trin.

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

i denne grådige algoritme tutorial, vil du lære:

• historie af grådige algoritmer
• grådige strategier og beslutninger
• karakteristika for den grådige tilgang
• Hvorfor bruge den grådige tilgang?
• Sådan løses aktivitetsudvælgelsesproblemet
• arkitektur af den grådige tilgang
• ulemper ved grådige algoritmer

historie af grådige algoritmer

her er et vigtigt vartegn for grådige algoritmer:

• grådige algoritmer blev konceptualiseret for mange grafvandringsalgoritmer i 1950 ‘ erne.
• Esdger Djikstra konceptualiserede algoritmen for at generere minimale spændende træer. Han havde til formål at forkorte rutespændet 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, skarmen, Rivest og Stein en rekursiv understruktur af grådige løsninger i deres klassiske introduktion til algoritmebog.
• det grådige søgeparadigme blev registreret som en anden type optimeringsstrategi i NIST records i 2005.
• indtil dato bruger protokoller, der kører internettet, såsom OSPF (open-shortest-path-first) og mange andre netværkspakkeomskiftningsprotokoller den grådige strategi for at minimere den tid, der bruges 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 anvendte Djikstras algoritme en trinvis grådig strategi, der identificerede værter på internettet ved at beregne en omkostningsfunktion. Værdien, der returneres af omkostningsfunktionen, 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 tilgang

de vigtige egenskaber ved en grådig metodealgoritme er:

• der er en ordnet liste over ressourcer med omkostninger eller værditildelinger. Disse kvantificerer begrænsninger på et system.
• du tager 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, hvilket kan gøre den velegnet til optimering.
• en fremtrædende grund er at opnå den mest gennemførlige løsning med det samme. I problemet med valg af aktivitet (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 problemet med valg af aktivitet opnås trinnet “rekursiv opdeling” ved kun at scanne en liste over emner en gang og overveje visse aktiviteter.

Sådan løses problemet med valg af aktivitet

i aktivitetsplanlægningseksemplet er der en “start” og “afslut” tid for hver aktivitet. Hver aktivitet er indekseret af et tal til reference. Der er to aktivitetskategorier.

1. overvejet aktivitet: er aktiviteten, som er referencen, hvorfra evnen til at udføre mere end en resterende aktivitet analyseres.
2. resterende aktiviteter: aktiviteter i et eller flere indekser forud for den betragtede aktivitet.

den samlede varighed giver omkostningerne ved at udføre aktiviteten. Det er (finish – 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 i tiden for en overvejet aktivitet.

arkitektur af 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, når den betragtede aktivitet er afsluttet, skal du begynde 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 betragtede 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 aktivitetsindekser, der vil blive brugt til at maksimere gennemstrømningen.

kode forklaring

#include<iostream>#include<stdio.h>#include<stdlib.h>#define MAX_ACTIVITIES 12

forklaring af kode:

1. inkluderet header filer / klasser
2. et maksimalt antal aktiviteter, som brugeren.

using namespace std;class TIME{ public: int hours; public: TIME() { hours = 0; }};

forklaring af kode:

1. navneområdet for streaming operationer.
2. en klasse definition for tid
3. en time tidsstempel.
4. en standardkonstruktør
5. variablen timer.

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; Activity *scheduled;

forklaring af kode:

1. Del 1 af definitionen af planlægningsklasse.
2. overvejet indeks er udgangspunktet for scanning af arrayet.
3. initialiseringsindekset bruges til at tildele tilfældige tidsstempler.
4. en række aktivitetsobjekter tildeles dynamisk ved hjælp af den nye operatør.
5. den planlagte markør definerer den aktuelle basisplacering for grådighed.

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

forklaring af kode:

1. scheduler constructor-del 2 af scheduler klasse 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.start.hours = rand() % 12; current_activities.finish.hours = current_activities.start.hours + (rand() % 2); printf("\nSTART:%d END %d\n", current_activities.start.hours ,current_activities.finish.hours); }……

forklaring af kode:

1. A for loop til initialisering af start-og sluttimer for hver af de aktiviteter, der aktuelt er planlagt.
2. starttid initialisering.
3. initialisering af sluttidspunkt altid efter eller nøjagtigt i starttiden.
4. en debug erklæring til at udskrive tildelte varigheder.

public: Activity * activity_select(int);};

forklaring af kode:

1. en del 4 – den sidste del af scheduler klasse definition.
2. aktivitet Vælg funktion tager et udgangspunkt indeks som base og opdeler grådige søgen i grådige delproblemer.

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

1. ved hjælp af omfangsopløsningsoperatøren (::) leveres funktionsdefinitionen.
2. det betragtede indeks er indekset kaldet af værdi. Den greedy_ekstent er initialiseret blot et indeks efter den betragtede indeks.

Activity * Scheduler :: activity_select(int considered_index){ while( (greedy_extent < MAX_ACTIVITIES ) && ((this->current_activities).start.hours < (this->current_activities).finish.hours )) { printf("\nSchedule start:%d \nfinish%d\n activity:%d\n", (this->current_activities).start.hours, (this->current_activities).finish.hours, greedy_extent + 1); greedy_extent++; }…...

forklaring af kode:

1. kernelogikken – det grådige omfang er begrænset til antallet af aktiviteter.
2. starttiderne for den aktuelle aktivitet kontrolleres som planlagte, før den betragtede aktivitet (givet af det betragtede indeks) ville afslutte.
3. så længe dette er muligt, udskrives en valgfri debug-erklæring.
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 kontrol, hvis alle aktiviteter er omfattet.
2. hvis ikke, kan du genstarte din grådige med det betragtede indeks som det aktuelle punkt. Dette er et rekursivt trin, der grådigt deler problemstillingen.
3. Hvis ja, vender den tilbage til den, der ringer op, 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 bruges til at påberåbe planlæggeren.
2. en ny planlægger er instantieret.
3. funktionen aktivitetsvælg, som returnerer en markør af type aktivitet, vender tilbage til den, der ringer op, efter at den grådige søgen er forbi.

udgang:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5 finish6 activity:3Schedule start:9 finish10 activity:5

ulemper ved grådige algoritmer

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

i sådanne grådige algoritmepraksisproblemer kan den grådige metode være forkert; i værste fald endda føre til en ikke-optimal løsning.

derfor bruger ulempen ved grådige algoritmer ikke at vide, hvad der ligger foran den nuværende grådige tilstand.

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

i den grådige scanning, der vises 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. Endvidere slutter dens søgen ved 12. Dette svarer til en værdi på 41.

men hvis algoritmen tog en suboptimal sti eller vedtog en erobrende strategi. derefter 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å grådige algoritmer

de fleste netværksalgoritmer bruger den grådige tilgang. Her er en liste over få grådige algoritmeeksempler:

• Prim ‘s Minimal Spanning Tree Algorithm
• Travelling Salesman Problem
• Graph – map Coloring
• Kruskal’ s Minimal Spanning Tree Algorithm
• Dijkstra ‘ s Minimal Spanning Tree Algorithm
• Graph – toppunkt Cover
• knapsack problem
• Jobplanlægningsproblem

Resume:

for at opsummere definerede artiklen Det grådige paradigme, viste, hvordan grådig optimering og rekursion kan hjælpe dig med at få den bedste løsning op til et punkt. Den grådige algoritme er bredt taget i anvendelse til problemløsning på mange sprog som grådige algoritme Python, C, C#, PHP, Java, etc. Aktivitetsvalget af grådige algoritmeeksempel blev beskrevet som et strategisk problem, der kunne opnå maksimal gennemstrømning ved hjælp af den grådige tilgang. I sidste ende blev nedbrydelserne af brugen af den grådige tilgang forklaret.