Grådig algoritme med eksempler: Grådig metode & Nærme sig

Indholdsfortegnelse:

Anonim

Hvad er en grådig algoritme?

I Grådig algoritme opdeles et sæt ressourcer rekursivt baseret på den maksimale, øjeblikkelige tilgængelighed af den ressource på et hvilket som helst tidspunkt i udførelsen.

For at løse et problem baseret på den grådige tilgang er der to faser

  1. Scanning af listen over emner
  2. Optimering

Disse faser er dækket parallelt i denne grådige algoritme tutorial, i løbet af opdelingen af ​​arrayet.

For at forstå den grådige tilgang skal du have en fungerende viden om rekursion og kontekstskift. Dette hjælper dig med at forstå, hvordan du sporer koden. Du kan definere det grådige paradigme i form af dine egne nødvendige og tilstrækkelige udsagn.

To betingelser definerer det grådige paradigme.

  • Hver trinvis løsning skal strukturere et problem i retning af sin bedst accepterede løsning.
  • Det er tilstrækkeligt, hvis strukturering 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øgningstilgang.

I denne grådige algoritmevejledning lærer du:

  • Historie af grådige algoritmer
  • Grådige strategier og beslutninger
  • Karakteristik af den grådige tilgang
  • Hvorfor bruge den grådige tilgang?
  • Sådan løses problemet med aktivitetsvalg
  • 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 grafgangalgoritmer i 1950'erne.
  • Esdger Djikstra konceptualiserede algoritmen for at generere minimale spændende træer. Han havde til formål at forkorte ruten i 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 underkonstruktion af grådige løsninger i deres klassiske introduktion til algoritmebogen.
  • Det grådige søgningsparadigme blev registreret som en anden type optimeringsstrategi i NIST-posterne i 2005.
  • Indtil dato bruger protokoller, der kører internettet, såsom OSPF (open-shortest-path-first) og mange andre protokoller til netværkspakning, den grådige strategi for at minimere tiden 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 anvendte Djikstras algoritme en trinvis grådig strategi, der identificerede værter på Internettet ved at beregne en omkostningsfunktion. Den værdi, der returneres af omkostningsfunktionen, bestemmer, 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å et hvilket som helst tidspunkt tager et skridt, der ikke er lokalt grådigt. De grådige problemer standser uden yderligere omfang af grådighed.

Karakteristik af den grådige tilgang

De vigtige egenskaber ved en grådig metodealgoritme er:

  • Der er en ordnet liste over ressourcer med omkostninger eller værditilskrivninger. Disse kvantificerer begrænsninger for 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 det egnet til optimering.
  • En fremtrædende grund er at nå den mest gennemførlige løsning med det samme. I problemet med aktivitetsvalg (forklaret nedenfor), hvis flere aktiviteter kan udføres inden afslutningen af ​​den aktuelle aktivitet, 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 med emner en gang og overveje bestemte aktiviteter.

Sådan løses problemet med aktivitetsvalg

I aktivitetsplanlægningseksemplet er der en "start" og "slut" -tid for hver aktivitet. Hver aktivitet er indekseret med et tal til reference. Der er to aktivitetskategorier.

  1. betragtet aktivitet : er aktiviteten, som er den reference, hvorfra evnen til at udføre mere end en tilbageværende 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 (slut - 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 betragtet 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 være afsluttet inden den tid, afslutter 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 sammenslutningen af ​​betragtede indekser. Dette er aktivitetsindekserne, der vil blive brugt til at maksimere kapaciteten.

Arkitektur af den grådige tilgang

Kode Forklaring

#include#include#include#define MAX_ACTIVITIES 12

Forklaring af kode:

  1. Inkluderede headerfiler / klasser
  2. Et maksimalt antal aktiviteter leveret af brugeren.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Forklaring af kode:

  1. Navneområdet til streamingoperationer.
  2. En klassedefinition for TIME
  3. En times tidsstempel.
  4. En TIME-standardkonstruktør
  5. Timevariablen.
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 definitionen af ​​planlægningsklassen.
  2. Overvejet indeks er udgangspunktet for scanning af arrayet.
  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. Planlægningskonstruktøren - del 2 af definitionen af ​​planlægningsklassen.
  2. Det betragtede indeks definerer den aktuelle start af den aktuelle scanning.
  3. Den nuværende grådige udstrækning 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-sløjfe til initialisering af start- og sluttid for hver af de aktiviteter, der aktuelt er planlagt.
  2. Initialisering af starttid.
  3. Initialisering af sluttid altid efter eller nøjagtigt i starttiden.
  4. En fejlretningserklæring for at udskrive tildelte varigheder.
public:Activity * activity_select(int);};

Forklaring af kode:

  1. Del 4 - den sidste del af definitionen af ​​planlægningsklassen.
  2. Aktivitetsvalgfunktion tager udgangspunkt i indeks som base og deler den 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 operatøren for omfangsopløsning (: :) gives funktionsdefinitionen.
  2. Det betragtede indeks er det indeks, der kaldes værdi. Den grådige_extent er initialiseret bare 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 planlægbare, inden den betragtede aktivitet (givet af betragtet indeks) er afsluttet.
  3. Så længe dette er muligt, udskrives en valgfri fejlretningserklæring.
  4. Gå videre til næste indeks på aktivitetsmatrixen
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Forklaring af kode:

  1. Betinget kontrollerer, om alle aktiviteter er dækket.
  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 det 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, der bruges til at påkalde planlæggeren.
  2. En ny planlægger iværksættes.
  3. Aktivitetsvalgfunktionen, som returnerer en markør af typen aktivitet, vender tilbage til den, der ringer op, når den grådige søgen er slut.

Produktion:

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

Ulemper ved grådige algoritmer

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

I sådanne grådige algoritmeproblemer kan den grådige metode 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 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. Yderligere afsluttes søgen klokken 12. Dette svarer til en værdi på 41.

Men hvis algoritmen tog en suboptimal vej 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 med få eksempler på grådige algoritmer:

  • Prims minimale spændende træalgoritme
  • Rejsende sælgerproblem
  • Graf - Kortfarvning
  • Kruskals minimale spændende træalgoritme
  • Dijkstras minimale spændende træalgoritme
  • Graf - Vertex Cover
  • Rygsækproblem
  • 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 op til et punkt. Den grådige algoritme er bredt taget i anvendelse til problemløsning på mange sprog som Grådig algoritme Python, C, C #, PHP, Java osv. Aktivitetsvalget af eksemplet med grådige algoritmer blev beskrevet som et strategisk problem, der kunne opnå maksimal gennemstrømning ved hjælp af den grådige nærme sig. I sidste ende blev ulemperne ved brugen af ​​den grådige tilgang forklaret.