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

Innholdsfortegnelse:

Anonim

Hva er en grådig algoritme?

I Grådig algoritme deles et sett ressurser rekursivt basert på den maksimale, umiddelbare tilgjengeligheten av den ressursen på et hvilket som helst trinn i utførelsen.

For å løse et problem basert på den grådige tilnærmingen, er det to trinn

  1. Skanner listen over elementer
  2. Optimalisering

Disse trinnene blir dekket parallelt i denne grådige algoritmeopplæringen, i løpet av oppdelingen av matrisen.

For å forstå den grådige tilnærmingen, må du ha kunnskap om rekursjon og kontekstbytte. Dette hjelper deg å forstå hvordan du kan spore koden. Du kan definere det grådige paradigmet i form av dine egne nødvendige og tilstrekkelige uttalelser.

To forhold definerer det grådige paradigmet.

  • Hver trinnvise løsning må strukturere et problem mot sin best aksepterte løsning.
  • Det er tilstrekkelig hvis struktureringen av problemet kan stoppe i et endelig antall grådige trinn.

Med teoretiseringen videre, la oss beskrive historien knyttet til den grådige søkemetoden.

I denne grådige algoritmeopplæringen lærer du:

  • Historie av grådige algoritmer
  • Grådige strategier og beslutninger
  • Kjennetegn ved den grådige tilnærmingen
  • Hvorfor bruke den grådige tilnærmingen?
  • Hvordan løse problemet med aktivitetsvalg
  • Arkitektur av den grådige tilnærmingen
  • Ulemper med grådige algoritmer

Historie av grådige algoritmer

Her er et viktig landemerke for grådige algoritmer:

  • Grådige algoritmer ble konseptualisert for mange grafgangalgoritmer på 1950-tallet.
  • Esdger Djikstra konseptualiserte algoritmen for å generere minimale spennende trær. Han hadde som mål å forkorte rutetiden i den nederlandske hovedstaden Amsterdam.
  • I samme tiår oppnådde Prim og Kruskal optimaliseringsstrategier som var basert på å minimere stiutgifter langs veide ruter.
  • På 70-tallet foreslo amerikanske forskere, Cormen, Rivest og Stein en rekursiv underkonstruksjon av grådige løsninger i sin klassiske introduksjon til algoritmeboken.
  • Det grådige søkeparadigmet ble registrert som en annen type optimaliseringsstrategi i NIST-postene i 2005.
  • Til dags dato bruker protokoller som kjører Internett, for eksempel OSPF (open-shortest-path-first) og mange andre protokoller for nettverkspakkeveksling, den grådige strategien for å minimere tiden som brukes i et nettverk.

Grådige strategier og beslutninger

Logikken i sin enkleste form ble kokt ned til "grådig" eller "ikke grådig". Disse uttalelsene ble definert av tilnærmingen som ble benyttet for å komme videre i hvert algoritmetrinn.

For eksempel brukte Djikstras algoritme en trinnvis grådig strategi som identifiserte verter på Internett ved å beregne en kostnadsfunksjon. Verdien som returneres av kostnadsfunksjonen bestemte om neste bane er "grådig" eller "ikke-grådig".

Kort sagt, en algoritme slutter å være grådig hvis den på noe tidspunkt tar et skritt som ikke er lokalt grådig. De grådige problemene stopper uten ytterligere omfang av grådighet.

Kjennetegn ved den grådige tilnærmingen

De viktige egenskapene til en grådig metodealgoritme er:

  • Det er en ordnet liste over ressurser, med kostnader eller verditilskrivninger. Disse kvantifiserer begrensninger på et system.
  • Du vil ta maksimalt antall ressurser i den tiden en begrensning gjelder.
  • For eksempel, i et aktivitetsplanleggingsproblem, er ressurskostnadene i timer, og aktivitetene må utføres i serierekkefølge.

Hvorfor bruke den grådige tilnærmingen?

Her er årsakene til at du bruker den grådige tilnærmingen:

  • Den grådige tilnærmingen har noen kompromisser, noe som kan gjøre den egnet for optimalisering.
  • En fremtredende grunn er å oppnå den mest gjennomførbare løsningen umiddelbart. I problemet med aktivitetsvalg (forklart nedenfor), hvis flere aktiviteter kan gjøres før du fullfører den nåværende aktiviteten, kan disse aktivitetene utføres innen samme tid.
  • En annen grunn er å dele et problem rekursivt basert på en tilstand, uten behov for å kombinere alle løsningene.
  • I aktivitetsvalgsproblemet oppnås trinnet "rekursiv inndeling" ved å skanne en liste med elementer bare en gang og vurdere bestemte aktiviteter.

Hvordan løse problemet med aktivitetsvalg

I aktivitetsplanleggingseksemplet er det en start- og sluttid for hver aktivitet. Hver aktivitet indekseres av et tall som referanse. Det er to aktivitetskategorier.

  1. ansett aktivitet : er aktiviteten, som er referansen som evnen til å gjøre mer enn en gjenværende aktivitet analyseres fra.
  2. gjenværende aktiviteter: aktiviteter på en eller flere indekser før den vurderte aktiviteten.

Den totale varigheten gir kostnadene ved å utføre aktiviteten. Det vil si (slutt - start) gir oss varigheten som kostnaden for en aktivitet.

Du vil lære at den grådige omfanget er antall gjenværende aktiviteter du kan utføre i løpet av en vurdert aktivitet.

Arkitektur av den grådige tilnærmingen

TRINN 1)

Skann listen over aktivitetskostnader, og start med indeks 0 som regnet som indeks.

STEG 2)

Når flere aktiviteter kan være ferdig innen tiden, avsluttes den vurderte aktiviteten, begynn å søke etter en eller flere gjenværende aktiviteter.

TRINN 3)

Hvis det ikke er flere gjenværende aktiviteter, blir den gjeldende gjenværende aktiviteten den neste vurderte aktiviteten. Gjenta trinn 1 og trinn 2, med den nye vurderte aktiviteten. Hvis det ikke er noen gjenværende aktiviteter igjen, går du til trinn 4.

TRINN 4)

Returner unionen av vurderte indekser. Dette er aktivitetsindeksene som skal brukes til å maksimere gjennomstrømningen.

Architecture of the Greedy Approach

Kode Forklaring

#include#include#include#define MAX_ACTIVITIES 12

Forklaring av kode:

  1. Inkluderte headerfiler / klasser
  2. Et maksimalt antall aktiviteter levert av brukeren.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Forklaring av kode:

  1. Navneområdet for streamingoperasjoner.
  2. En klassedefinisjon for TIME
  3. En times tidsstempel.
  4. EN TIME standardkonstruktør
  5. Timevariabelen.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Forklaring av kode:

  1. En klassedefinisjon fra aktivitet
  2. Tidsstempler som definerer en varighet
  3. Alle tidsstemplene initialiseres til 0 i standardkonstruktøren
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Forklaring av kode:

  1. Del 1 av definisjonen av planleggerklassen.
  2. Betraktet indeks er utgangspunktet for skanning av matrisen.
  3. Initialiseringsindeksen brukes til å tildele tilfeldige tidsstempler.
  4. En rekke aktivitetsobjekter tildeles dynamisk ved hjelp av den nye operatøren.
  5. Den planlagte pekeren definerer den nåværende baseplasseringen for grådighet.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Forklaring av kode:

  1. Planleggerkonstruktøren - del 2 av definisjonen av planleggerklassen.
  2. Den vurderte indeksen definerer den gjeldende starten på gjeldende skanning.
  3. Den nåværende grådige omfanget er udefinert 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 av kode:

  1. En for loop for å initialisere starttid og sluttid for hver av aktivitetene som er planlagt.
  2. Initialisering av starttid.
  3. Initialisering av sluttid alltid etter eller nøyaktig i starttiden.
  4. En feilsøking for å skrive ut tildelte varigheter.
public:Activity * activity_select(int);};

Forklaring av kode:

  1. Del 4 - den siste delen av definisjonen av planleggerklassen.
  2. Aktivitetsvalgfunksjon tar utgangspunkt i indeksen som base og deler den grådige søken 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 å bruke operatøren for oppløsningsområde (: :), er funksjonsdefinisjonen gitt.
  2. Den vurderte indeksen er indeksen kalt etter verdi. Greedy_extent er initialisert bare en indeks etter den vurderte indeksen.
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 av kode:

  1. Kjernelogikken - Den grådige omfanget er begrenset til antall aktiviteter.
  2. Starttiden for den gjeldende aktiviteten blir sjekket som planlegbar før den vurderte aktiviteten (gitt av vurdert indeks) vil fullføres.
  3. Så lenge dette er mulig, skrives det ut en valgfri feilsøking.
  4. Gå videre til neste indeks på aktivitetsmatrisen
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Forklaring av kode:

  1. Betinget sjekker om alle aktivitetene er dekket.
  2. Hvis ikke, kan du starte din grådige på nytt med den betraktede indeksen som gjeldende punkt. Dette er et rekursivt trinn som grådig deler problemstillingen.
  3. Hvis ja, kommer den tilbake til den som ringer, uten mulighet til å utvide grådighet.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Forklaring av kode:

  1. Hovedfunksjonen som brukes til å påkalle planleggeren.
  2. En ny planlegger blir instantiert.
  3. Aktivitetsvalgfunksjonen, som returnerer en peker av typen aktivitet, kommer tilbake til innringeren etter at den grådige søken er over.

Produksjon:

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

Ulemper med grådige algoritmer

Det er ikke egnet for grådige problemer der det kreves en løsning for hvert delproblem som sortering.

I slike problemer med grådige algoritmer kan den grådige metoden være feil; i verste fall til og med føre til en ikke-optimal løsning.

Derfor er ulempen med grådige algoritmer å ikke vite hva som ligger foran den nåværende grådige tilstanden.

Nedenfor er en skildring av ulempen med den grådige metoden:

I den grådige skanningen som vises her som et tre (høyere verdi høyere grådighet), vil en algoritmestatus på verdi: 40 sannsynligvis ta 29 som neste verdi. Videre slutter søken klokka 12. Dette utgjør en verdi på 41.

Imidlertid hvis algoritmen tok en suboptimal vei eller vedtok en erobringsstrategi. da ville 25 bli fulgt av 40, og den totale kostnadsforbedringen ville være 65, som er verdsatt 24 poeng høyere som en suboptimal beslutning.

Eksempler på grådige algoritmer

De fleste nettverksalgoritmer bruker den grådige tilnærmingen. Her er en liste over få grådige algoritmeeksempler:

  • Prim's Minimal Spanning Tree Algorithm
  • Reisende selgerproblem
  • Graf - Kartfarging
  • Kruskals Minimal Spanning Tree Algorithm
  • Dijkstra's Minimal Spanning Tree Algorithm
  • Graf - Vertex Cover
  • Ryggsekkproblem
  • Jobbplanlegging Problem

Sammendrag:

For å oppsummere definerte artikkelen det grådige paradigmet, viste hvordan grådig optimalisering og rekursjon kan hjelpe deg med å oppnå den beste løsningen opp til et punkt. Den grådige algoritmen er mye tatt i bruk for problemløsning på mange språk som grådig algoritme Python, C, C #, PHP, Java, etc. Aktivitetsvalget av grådig algoritmeeksempel ble beskrevet som et strategisk problem som kunne oppnå maksimal gjennomstrømning ved hjelp av den grådige nærme seg. Til slutt ble ulempene ved bruken av den grådige tilnærmingen forklart.