Greedy algoritm med exempel: Greedy metod & tillvägagångssätt

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 när det gäller 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 stoppa i ett begränsat antal giriga steg.

med teoretiseringen fortsatt, låt oss beskriva historien i samband med den giriga sökmetoden.

i denna giriga algoritmhandledning lär du dig:

• historia av giriga algoritmer
• giriga strategier och beslut
• egenskaper hos den giriga metoden
• varför använda den giriga metoden?
• hur man löser problemet med aktivitetsval
• arkitektur för det giriga tillvägagångssättet
• nackdelar med giriga algoritmer

historia av giriga algoritmer

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

• giriga algoritmer konceptualiserades för många grafvandringsalgoritmer på 1950-talet.
• Esdger Djikstra konceptualiserade algoritmen för att generera minimala spännträd. Han syftade till att förkorta sträckan av rutter inom den nederländska huvudstaden, Amsterdam.
• under samma årtionde uppnådde Prim och Kruskal optimeringsstrategier som baserades på att minimera vägkostnader längs vägda vägar.
• på 70-talet föreslog amerikanska forskare, Cormen, Rivest och Stein en rekursiv substrukturering av giriga lösningar i sin klassiska introduktion till algoritmbok.
• det giriga sökparadigmet registrerades som en annan typ av optimeringsstrategi i NIST-posterna 2005.
• till datum använder protokoll som kör webben, till exempel open-shortest-path-first (OSPF) och många andra nätverkspaketväxlingsprotokoll den giriga strategin för att minimera tiden som spenderas på ett nätverk.

giriga strategier och beslut

logik i sin enklaste form kokades ner till” girig ”eller”inte girig”. Dessa uttalanden definierades av tillvägagångssättet för att avancera i varje algoritmstadium.

till exempel använde Djikstras algoritm en stegvis girig strategi som identifierade värdar på Internet genom att beräkna en kostnadsfunktion. Värdet 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 stannar utan ytterligare omfattning av girighet.

egenskaper hos den giriga metoden

de viktiga egenskaperna hos en girig metodalgoritm är:

• det finns en ordnad lista över resurser, med kostnader eller värdeattribut. 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 seriell ordning.

Varför använda den giriga metoden?

här är anledningarna till att använda den giriga metoden:

• den giriga metoden har några kompromisser, 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 du avslutar den aktuella aktiviteten, 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 skanna en lista med objekt endast en gång och överväga vissa aktiviteter.

hur man löser aktivitetsvalsproblemet

i aktivitetsschemaläggningsexemplet finns det en” start ”och” finish ” – tid för varje aktivitet. Varje aktivitet indexeras med ett nummer som referens. Det finns två aktivitetskategorier.

1. betraktad aktivitet: är aktiviteten, som ä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 (finish-start) Ger Oss varaktigheten som kostnaden för en aktivitet.

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

arkitektur för den giriga metoden

steg 1)

skanna listan över aktivitetskostnader, börja med index 0 som det betraktade indexet.

steg 2)

när fler aktiviteter kan slutföras när den aktuella aktiviteten avslutas, börja söka efter en eller flera återstående aktiviteter.

steg 3)

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

steg 4)

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

kod förklaring

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

förklaring av kod:

1. inkluderade huvudfiler / 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. namnrymden för streamingoperationer.
2. en klass definition för tid
3. en timme tidsstämpel.
4. en tid standard konstruktör
5. timmar 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 initieras till 0 i standardkonstruktören

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

förklaring av kod:

1. Del 1 av schemaläggningsklassdefinitionen.
2. betraktat Index är utgångspunkten för att skanna arrayen.
3. initialiseringsindexet används för att tilldela slumpmässiga tidsstämplar.
4. en rad aktivitetsobjekt tilldelas dynamiskt med den nya operatorn.
5. den schemalagda pekaren definierar den aktuella basplatsen för girighet.

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

förklaring av kod:

1. scheduler constructor-del 2 av definitionen schemaläggare klass.
2. det övervägda indexet definierar den aktuella starten på den aktuella skanningen.
3. den nuvarande giriga omfattningen är odefinierad i början.

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

förklaring av kod:

1. A för loop för att initiera starttimmar och sluttimmar för var och en av de aktiviteter som för närvarande är schemalagda.
2. starttid initiering.
3. initiering av sluttid alltid efter eller exakt vid starttiden.
4. ett felsökningsuttalande för att skriva ut tilldelade varaktigheter.

public: Activity * activity_select(int);};

förklaring av kod:

1. Del 4-den sista delen av scheduler-klassdefinitionen.
2. Activity select-funktionen tar ett utgångspunktindex som bas och delar upp det giriga uppdraget 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 scope resolution operator (::) tillhandahålls funktionsdefinitionen.
2. det betraktade indexet är indexet som kallas efter värde. Greedy_extent är det initialiserade bara ett index efter det betraktade indexet.

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

förklaring av kod:

1. kärnlogiken-den giriga omfattningen är begränsad till antalet aktiviteter.
2. starttimmarna för den aktuella aktiviteten kontrolleras som schemaläggbara innan den betraktade aktiviteten (ges av betraktat index) skulle slutföras.
3. så länge det är möjligt skrivs ett valfritt felsökningsuttalande ut.
4. gå vidare till nästa index på aktivitetsmatrisen

...if ( greedy_extent <= MAX_ACTIVITIES ) { return activity_select(greedy_extent); } else { return NULL; }}

förklaring av kod:

1. de villkorliga kontrollerna 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 problemförklaringen.
3. om ja, återgår den till den som ringer utan utrymme för att utvidga 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 anropa Schemaläggaren.
2. en ny schemaläggare instansieras.
3. funktionen activity select, som returnerar en pekare av typaktivitet, kommer tillbaka till den som ringer efter att greedy quest är över.

utgång:

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

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 giriga algoritmövningsproblem kan den giriga metoden vara fel; i värsta fall även leda till en icke-optimal lösning.

därför nackdelen med giriga algoritmer använder inte veta vad som ligger framför den nuvarande giriga tillstånd.

nedan är 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 till värde: 40, sannolikt att ta 29 som nästa värde. Vidare slutar dess uppdrag vid 12. Detta uppgår till ett värde av 41.

men om algoritmen tog en suboptimal väg eller antog en erövringsstrategi. sedan 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 giriga algoritmexempel:

• Prims minimal Spanning Tree algoritm
• resande säljare Problem
• Graph – Map Coloring
• Kruskal s Minimal Spanning Tree algoritm
• Dijkstra s Minimal Spanning Tree algoritm
• Graph – Vertex Cover
• ryggsäck problem
• jobb schemaläggning problem

sammanfattning:

för att sammanfatta, artikeln definierade giriga Paradigm, visade hur girig optimering och rekursion, kan hjälpa dig att få den bästa lösningen upp till en punkt. Den giriga algoritmen är allmänt tas i ansökan för problemlösning på många språk som giriga algoritm Python, C, C#, PHP, Java, etc. Aktivitetsvalet av Greedy algorithm-exemplet beskrevs som ett strategiskt problem som kunde uppnå maximal genomströmning med hjälp av greedy-metoden. I slutändan förklarades demeriterna av användningen av den giriga metoden.