Girig algoritm med exempel: Vad är, metod och tillvägagångssätt

För att förstå det giriga tillvägagångssättet måste du ha praktisk 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ästa accepterade lösning.
• Det räcker om struktureringen av problemet kan stanna i ett begränsat antal giriga steg.

Med fortsatt teoretisering, låt oss beskriva historien förknippad med den giriga sökmetoden.

Greedys historia Algorithms

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

• Giriga algoritmer konceptualiserades för många grafgångsalgoritmer på 1950-talet.
• Esdger Djikstra konceptualiserade algoritmen för att generera minimala spännträd. Han siktade på att förkorta rutter i den holländska huvudstaden Amsterdam.
• Under samma decennium uppnådde Prim och Kruskal optimeringsstrategier som var baserade 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.
• Hittills använder protokoll som kör webben, såsom open-shorttest-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 gå vidare 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. Värdet som returnerades av kostnadsfunktionen avgjorde om nästa vä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 omfattning av girighet.

Egenskaper hos den giriga algoritmen

De viktiga egenskaperna hos en girig algoritm är:

• Det finns en ordnad lista över resurser, med kostnader eller värdetillskrivningar. Dessa kvantifierar begränsningar på ett system.
• Du kommer att ta 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 skälen till att använda den giriga metoden:

• Det giriga tillvägagångssättet har några avvägningar, vilket kan göra det lämpligt för optimering.
• Ett framträdande skäl ä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.
• Ett annat skäl ä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 aktivitetsvalsproblemet

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

1. betraktas som 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 vid ett eller flera index före den aktuella aktiviteten.

Den totala varaktigheten anger kostnaden för att utföra aktiviteten. Det vill säga (slut – 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.

ArchiTecture of the Greedy approach

STEG 1) Skanna listan över aktivitetskostnader, börja med index 0 som index.

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

STEG 3) Om det inte finns fler kvarvarande aktiviteter blir den aktuella kvarvarande 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 föreningen av övervägda index. Det här är aktivitetsindexen som kommer att användas för att maximera genomströmningen.

Kodförklaring

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Förklaring av kod:

1. Inkluderade rubrikfiler/klasser
2. Ett max 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. Namnutrymmet för streamingoperationer.
2. En klassdefinition för TID
3. En timmes tidsstämpel.
4. En TIME-standardkonstruktor
5. Timmarna varierar.

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 standardkonstruktorn

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äggarens klassdefinition.
2. Anses Index är utgångspunkten för att skanna array.
3. Initieringsindexet används för att tilldela slumpmässiga tidsstämplar.
4. En uppsättning 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. Schemaläggarens konstruktor – del 2 av schemaläggarklassdefinitionen.
2. Det övervägda indexet definierar den aktuella starten av 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[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. En för-loop för att initiera start- och sluttimmar för var och en av de aktiviteter som för närvarande är schemalagda.
2. Initiering av starttid.
3. Sluttidsinitiering alltid efter eller exakt vid starttimmen.
4. En felsökningssats för att skriva ut tilldelade varaktigheter.

	public:
   		 Activity * activity_select(int);
};

Förklaring av kod:

1. Del 4 – den sista delen av schemaläggarens klassdefinition.
2. Aktivitetsvalsfunktionen tar ett startpunktsindex 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 det index som kallas av värde. Greedy_extent är den initialiserade 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. Starttimmarna för den aktuella aktiviteten kontrolleras som schemalagda innan den övervägda aktiviteten (given av det övervägda indexet) skulle avslutas.
3. Så länge detta är möjligt skrivs en valfri felsökningssats 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 villkorade kontrollerna om alla aktiviteter har täckts.
2. Om inte, kan du starta om din giriga med det ansedda indexet som aktuell punkt. Detta är ett rekursivt steg som girigt delar upp problemformuleringen.
3. Om ja, återgår den till den som ringer utan utrymme för att utöka girigheten.

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. Aktivitetsvalsfunktionen, som returnerar en pekare av typen aktivitet, kommer tillbaka till den som ringer efter att det giriga uppdraget är över.

Produktion:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

Begränsningar av girig teknik

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 Greedy-algoritmövningsproblem kan Greedy-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 ä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 vid värde: 40 sannolikt att ta 29 som nästa värde. Vidare slutar uppdraget vid 12. Detta uppgår till ett värde av 41.

Men om algoritmen tog en suboptimal väg eller antog en erövrande strategi. 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 Algorithms

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

• Prims Minimal Spanning Tree Algorithm
• Resande säljare Problem
• Graf – Kartfärgning
• Kruskals Minimal Spanning Tree Algorithm
• Dijkstras Minimal Spanning Tree Algorithm
• Graf – Vertex Cover
• Knapsäcksproblem
• Jobbschemaläggningsproblem

Sammanfattning

För att sammanfatta, definierade artikeln det giriga paradigmet, visade hur girig optimering och rekursion kan hjälpa dig att få den bästa lösningen till en viss punkt. Den giriga algoritmen används allmänt för problemlösning på många språk som girig algoritm Python, C, C#, PHP, Java, etc. Aktivitetsvalet av Greedy-algoritmexemplet beskrevs som ett strategiskt problem som kunde uppnå maximal genomströmning med den giriga metoden. Till slut förklarades nackdelarna med användningen av den giriga metoden.