Girig algoritm med exempel: girig metod & Närma sig

Innehållsförteckning:

Anonim

Vad är en girig algoritm?

I girig algoritm delas en uppsättning resurser rekursivt baserat på den maximala, omedelbara tillgängligheten för den resursen vid ett visst stadium av utförandet.

För att lösa ett problem baserat på den giriga metoden finns det två steg

  1. Skannar listan med objekt
  2. Optimering

Dessa steg behandlas parallellt i den här giriga algoritmhandledningen på grund av uppdelningen av matrisen.

För att förstå det giriga tillvägagångssättet måste du ha en fungerande kunskap om rekursion och kontextbyte. Detta hjälper dig att förstå hur du spårar koden. Du kan definiera det giriga paradigmet i termer av dina egna nödvändiga och tillräckliga uttalanden.

Två villkor definierar det giriga paradigmet.

  • Varje stegvis lösning måste strukturera ett problem mot sin bäst accepterade lösning.
  • Det räcker om struktureringen av problemet kan stoppas i ett begränsat antal giriga steg.

Med teoretiseringen fortsätter, låt oss beskriva historien i samband med den giriga sökmetoden.

I den här giriga algoritmhandledningen lär du dig:

  • Historien om giriga algoritmer
  • Giriga strategier och beslut
  • Kännetecken för den giriga metoden
  • Varför använda den giriga metoden?
  • Hur man löser problemet med aktivitetsval
  • Arkitektur av det giriga tillvägagångssättet
  • Nackdelar med giriga algoritmer

Historien om giriga algoritmer

Här är ett viktigt landmärke för giriga algoritmer:

  • Giriga algoritmer konceptualiserades för många diagrampromenader på 1950-talet.
  • Esdger Djikstra konceptualiserade algoritmen för att generera minimala spännande träd. Han syftade till att förkorta sträckan inom den holländska huvudstaden Amsterdam.
  • Under samma årtionde uppnådde Prim och Kruskal optimeringsstrategier som baserades på att minimera vägkostnader längs vägda rutter.
  • På 70-talet föreslog amerikanska forskare, Cormen, Rivest och Stein en rekursiv underkonstruktion av giriga lösningar i sin klassiska introduktion till algoritmboken.
  • Det giriga sökparadigmet registrerades som en annan typ av optimeringsstrategi i NIST-posterna 2005.
  • Till dags dato använder protokoll som kör webben, som OSPF (open-shortest-path-first) och många andra nätverkspaketväxlingsprotokoll, den giriga strategin för att minimera den tid som spenderas i ett nätverk.

Giriga strategier och beslut

Logiken i sin enklaste form kokades ner till "girig" eller "inte girig". Dessa uttalanden definierades av den metod som användes för att avancera i varje algoritmsteg.

Till exempel använde Djikstras algoritm en stegvis girig strategi för att identifiera värdar på Internet genom att beräkna en kostnadsfunktion. Det värde som returneras av kostnadsfunktionen bestämde om nästa sökväg är "girig" eller "icke-girig".

Kort sagt, en algoritm upphör att vara girig om den i något skede tar ett steg som inte är lokalt girigt. De giriga problemen upphör utan ytterligare girighet.

Kännetecken för den giriga metoden

De viktiga egenskaperna hos en girig metodalgoritm är:

  • Det finns en ordnad lista över resurser med kostnader eller värdetillskrivningar. Dessa kvantifierar begränsningar för ett system.
  • Du tar den maximala mängden resurser under den tid en begränsning gäller.
  • Till exempel, i ett aktivitetsschemaläggningsproblem, är resurskostnaderna i timmar och aktiviteterna måste utföras i serieordning.

Varför använda den giriga metoden?

Här är skälen till att använda den giriga metoden:

  • Den giriga metoden har några avvägningar, vilket kan göra den lämplig för optimering.
  • En framträdande anledning är att uppnå den mest genomförbara lösningen omedelbart. I aktivitetsvalsproblemet (förklaras nedan), om fler aktiviteter kan göras innan den aktuella aktiviteten avslutas, kan dessa aktiviteter utföras inom samma tid.
  • En annan anledning är att dela upp ett problem rekursivt baserat på ett tillstånd, utan att behöva kombinera alla lösningar.
  • I aktivitetsvalsproblemet uppnås steget "rekursiv uppdelning" genom att bara skanna en lista med objekt en gång och överväga vissa aktiviteter.

Hur man löser problemet med aktivitetsval

I aktivitetsschemaläggningsexemplet finns det en start- och sluttid för varje aktivitet. Varje aktivitet indexeras med ett nummer som referens. Det finns två aktivitetskategorier.

  1. betraktad aktivitet : är aktiviteten, vilket är referensen från vilken förmågan att göra mer än en återstående aktivitet analyseras.
  2. återstående aktiviteter: aktiviteter på ett eller flera index före den aktuella aktiviteten.

Den totala varaktigheten ger kostnaden för att utföra aktiviteten. Det är (slut - start) ger oss den längd som kostnaden för en aktivitet.

Du kommer att lära dig att den giriga omfattningen är antalet återstående aktiviteter som du kan utföra under tiden för en övervägande aktivitet.

Arkitektur av det giriga tillvägagångssättet

STEG 1)

Skanna listan över aktivitetskostnader och börja med index 0 som det betraktade indexet.

STEG 2)

När fler aktiviteter kan avslutas med tiden slutar den aktuella aktiviteten, börja söka efter en eller flera återstående aktiviteter.

STEG 3)

Om det inte finns fler återstående aktiviteter blir den aktuella återstående aktiviteten nästa aktivitet. Upprepa steg 1 och steg 2 med den nya övervägda aktiviteten. Om det inte finns några kvarvarande aktiviteter kvar, gå till steg 4.

STEG 4)

Återför unionen av betraktade index. Dessa är aktivitetsindex som kommer att användas för att maximera genomströmningen.

Arkitekturen för den giriga metoden

Kodförklaring

#include#include#include#define MAX_ACTIVITIES 12

Förklaring av kod:

  1. Ingår rubrikfiler / klasser
  2. Ett maximalt antal aktiviteter som tillhandahålls av användaren.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Förklaring av kod:

  1. Namnområdet för direktuppspelning.
  2. En klassdefinition för TIME
  3. En timmas tidsstämpel.
  4. En TIME-standardkonstruktör
  5. Timmens variabel.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Förklaring av kod:

  1. En klassdefinition från aktivitet
  2. Tidsstämplar som definierar en varaktighet
  3. Alla tidsstämplar initialiseras till 0 i standardkonstruktören
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Förklaring av kod:

  1. Del 1 av schemaläggarklassdefinitionen.
  2. Betraktat index är utgångspunkten för skanning av matrisen.
  3. Initialiseringsindex används för att tilldela slumpmässiga tidsstämplar.
  4. En rad aktivitetsobjekt allokeras dynamiskt med den nya operatören.
  5. Den schemalagda pekaren definierar den aktuella basplatsen för girighet.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Förklaring av kod:

  1. Schemaläggarkonstruktören - del 2 av schemaläggarklassdefinitionen.
  2. Det betraktade indexet definierar den aktuella början på den aktuella genomsökningen.
  3. Den nuvarande giriga omfattningen är odefinierad i början.
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);}… …

Förklaring av kod:

  1. A for loop för att initialisera start- och sluttider för var och en av de aktiviteter som för närvarande är schemalagda.
  2. Initiering av starttid.
  3. Initiering av sluttid alltid efter eller exakt vid starttiden.
  4. En felsökning för att skriva ut tilldelade varaktigheter.
public:Activity * activity_select(int);};

Förklaring av kod:

  1. Del 4 - den sista delen av schemaläggarklassdefinitionen.
  2. Aktivitetsvalfunktionen tar utgångspunktindex som bas och delar upp den giriga strävan i giriga delproblem.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Med hjälp av operatören scope resolution (: :) tillhandahålls funktionsdefinitionen.
  2. Det betraktade indexet är det index som kallas efter värde. Den giriga_extenten är initialiserad bara ett index efter det betraktade indexet.
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++;}… …

Förklaring av kod:

  1. Kärnlogiken - Den giriga omfattningen är begränsad till antalet aktiviteter.
  2. Starttiderna för den aktuella aktiviteten kontrolleras som schemaläggbara innan den betraktade aktiviteten (ges av betraktat index) slutar.
  3. Så länge det är möjligt skrivs ett valfritt felsökningsuttalande ut.
  4. Gå vidare till nästa index i aktivitetsmatrisen
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Förklaring av kod:

  1. Villkorliga kontroller om alla aktiviteter har täckts.
  2. Om inte, kan du starta om din giriga med det betraktade indexet som aktuell punkt. Detta är ett rekursivt steg som girigt delar upp problemet.
  3. Om ja, återgår den till den som ringer utan utrymme för att utöka girighet.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Förklaring av kod:

  1. Huvudfunktionen som används för att åberopa schemaläggaren.
  2. En ny schemaläggare startas.
  3. Aktivitetsvalfunktionen, som returnerar en pekare av typaktivitet, kommer tillbaka till den som ringer efter att den giriga sökningen är över.

Produktion:

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

Nackdelar med giriga algoritmer

Det är inte lämpligt för giriga problem där en lösning krävs för varje delproblem som sortering.

I sådana problem med giriga algoritmer kan den giriga metoden vara fel; i värsta fall till och med leda till en icke-optimal lösning.

Därför är nackdelen med giriga algoritmer att man inte vet vad som ligger framför det nuvarande giriga tillståndet.

Nedan följer en skildring av nackdelen med den giriga metoden:

I den giriga skanningen som visas här som ett träd (högre värde högre girighet) kommer ett algoritmtillstånd vid värde: 40 sannolikt att ta 29 som nästa värde. Vidare avslutas uppdraget vid 12. Detta uppgår till ett värde av 41.

Men om algoritmen tog en suboptimal väg eller antog en erövringsstrategi. då skulle 25 följas av 40, och den totala kostnadsförbättringen skulle vara 65, vilket värderas 24 poäng högre som ett suboptimalt beslut.

Exempel på giriga algoritmer

De flesta nätverksalgoritmer använder den giriga metoden. Här är en lista med några exempel på giriga algoritmer:

  • Prim's Minimal Spanning Tree Algorithm
  • Resande säljare Problem
  • Graf - Kartfärgning
  • Kruskals minimala spännande trädalgoritm
  • Dijkstras minimala spännande trädalgoritm
  • Diagram - Vertex Cover
  • Ryggsäck Problem
  • Problem med jobbplanering

Sammanfattning:

Sammanfattningsvis definierade artikeln det giriga paradigmet, visade hur girig optimering och rekursion kan hjälpa dig att få den bästa lösningen upp till en punkt. Den giriga algoritmen används i stor utsträckning i applikation för problemlösning på många språk som giriga algoritmen Python, C, C #, PHP, Java, etc. Aktivitetsvalet av exemplet med giriga algoritmer beskrivs som ett strategiskt problem som skulle kunna uppnå maximal genomströmning med den giriga närma sig. I slutändan förklarades nackdelarna med att använda det giriga tillvägagångssättet.