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

Vad är en girig algoritm?

A Girig algoritm delar rekursivt en uppsättning resurser baserat på den maximala omedelbara tillgängligheten för den resursen i vilket skede som helst av exekveringen.

Att lösa ett problem med den giriga metoden har två steg:

1. Skannar listan med objekt
2. Optimering

Båda stegen löper parallellt medan inmatningsmatrisen progressivt delas upp.

För att följa den giriga metoden hjälper praktisk kunskap om rekursion och kontextväxling dig. trace koden. Det giriga paradigmet kan beskrivas med ett par nödvändiga och tillräckliga påståenden.

Två villkor definierar det giriga paradigmet.

• Varje stegvis val måste styra problemet mot dess bäst accepterade lösning.
• Problemstrukturen måste stanna i ett ändligt antal giriga steg.

Med teorin på plats, låt oss titta på historien bakom den giriga sökmetoden.

Greedys historia Algorithms

Här är de viktiga milstolparna i de giriga algoritmernas historia:

• Giriga algoritmer konceptualiserades först för grafvandringsalgoritmer på 1950-talet.
• Edsger Dijkstra utvecklade sin algoritm för kortaste vägen för att förkorta rutter genom den holländska huvudstaden Amsterdam.
• Under samma decennium utvecklade Prim och Kruskal optimeringsstrategier som minimerar vägkostnader längs viktade rutter för att bygga minimalt uppspannande träd.
• På 70-talet beskrev de amerikanska forskarna Cormen, Leiserson, Rivest och Stein rekursiv substrukturering av giriga lösningar i sin klassiska bok Introduction to Algorithms lärobok.
• Det giriga sökparadigmet katalogiserades som en distinkt optimeringsstrategi i NIST-registret år 2005.
• Än idag använder webbprotokoll som Open Shortest Path First (OSPF) och många paketväxlande protokoll den giriga strategin för att minimera transittiden i ett nätverk.

Giriga strategier och beslut

Logiken reduceras till ett binärt val i varje steg – ”girig” eller ”inte girig” – baserat på den riktning algoritmen tar för att avancera.

Till exempel identifierar Dijkstras algoritm värdar på internet genom att utvärdera en kostnadsfunktion i varje steg. Värdet som kostnadsfunktionen returnerar avgör om nästa väg är "girig" eller "icke-girig".

Kort sagt, en algoritm slutar vara girig i det ögonblick den tar ett steg som inte är lokalt optimalt, och giriga problem upphör när inget ytterligare girigt steg är möjligt.

Egenskaper hos den giriga algoritmen

De viktiga egenskaperna hos en girig algoritm är:

• En ordnad lista över resurser bär kostnads- eller värdeattributioner som kvantifierar begränsningarna för systemet.
• Algoritmen tar den maximala mängden resurser inom den tid som en begränsning gäller.
• Till exempel, i ett aktivitetsplaneringsproblem mäts 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:

• Den giriga metoden har avvägningar som gör den väl lämpad för optimering.
• Den mest uppenbara anledningen är att omedelbart ta fram en genomförbar lösning. I aktivitetsvalsproblemet som diskuteras nedan, om fler aktiviteter får plats innan den aktuella aktiviteten avslutas, kan de schemaläggas i samma fönster.
• En annan anledning är att den delar upp ett problem rekursivt baserat på ett villkor, utan behov av att slå samman dellösningar.
• I problemet med aktivitetsurval uppnås det rekursiva divisionssteget genom att skanna listan en gång och endast beakta de lämpliga aktiviteterna.

Hur man löser problemet med aktivitetsval

I exemplet med aktivitetsschemaläggning har varje aktivitet en start- och sluttid och är indexerad med ett nummer som referens. Det finns två aktivitetskategorier:

1. Övervägd aktivitet: referensaktiviteten från vilken förmågan att passa fler återstående aktiviteter mäts.
2. Återstående aktiviteter: aktiviteter vid ett eller flera index före den aktuella aktiviteten.

Kostnaden för att utföra en aktivitet är dess varaktighet, beräknad som (mål – start).

Den giriga omfattningen är helt enkelt antalet återstående aktiviteter som kan utföras inom tiden för en betraktad aktivitet.

ArchiTecture of the Greedy Approach

Steg 1) Skanna listan över aktivitetskostnader som börjar med index 0 som det övervägda indexet.

Steg 2) När fler aktiviteter kan slutföras när den aktuella aktiviteten är slut, sök efter de återstående aktiviteterna.

Steg 3) Om inga fler aktiviteter kan schemaläggas blir den nuvarande återstående aktiviteten nästa aktivitet som beaktas. Upprepa steg 1 och steg 2 med den nya aktiviteten. Om inga aktiviteter återstår, gå till steg 4.

Steg 4) Returnera unionen av betraktade index — det här är de aktivitetsindex som maximerar genomströmningen.

ArchiTecture of the Greedy Approach

Code Förklaring

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

#define MAX_ACTIVITIES 12

Förklaring av kod:

1. Inkluderade rubrikfiler/klasser
2. Det maximala antalet aktiviteter som kan konfigureras av användaren.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Förklaring av kod:

1. Deklarerar standardnamnrymden för strömmande åtgärder.
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 för Aktivitet.
2. Tidsstämplar som tillsammans 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. considered_index är startpunkten för att skanna arrayen.
3. init_index används för att tilldela slumpmässiga tidsstämplar under installationen.
4. En array med aktivitetsobjekt allokeras dynamiskt med den nya operatorn.
5. Den schemalagda pekaren innehåller det aktuella giriga resultatet.

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

Förklaring av kod:

1. Scheduler-konstruktorn — del 2 av klassdefinitionen.
2. considered_index markerar starten av den aktuella skanningen.
3. Den 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);
 }
&#8230;
&#8230;

Förklaring av kod:

1. En for-loop initierar start- och sluttiderna för varje schemalagd aktivitet.
2. Initierar starttiden.
3. Initierar sluttiden till att vara vid eller efter starttimmen.
4. En debug-sats skriver ut de allokerade varaktigheterna.

	public:
   		 Activity * activity_select(int);
};

Förklaring av kod:

1. Del 4 — den sista delen av definitionen av Scheduler-klassen.
2. activity_select() tar ett startindex som bas och delar upp den giriga uppgiften i delproblem.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. Scope-upplösningsoperatorn (::) länkar funktionsdefinitionen till Scheduler-klassen.
2. considered_index skickas med värde, och greedy_extent initieras till indexet omedelbart efter det.

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++;
    	}
&#8230;
...

Förklaring av kod:

1. Kärnlogiken — den giriga omfattningen är begränsad till MAX_ACTIVITIES.
2. Starttiden för den aktuella aktiviteten jämförs med sluttiden för den aktuella aktiviteten.
3. Så länge villkoret gäller skrivs en valfri felsökningssats ut.
4. Den giriga omfattningen går sedan 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. Villkoret kontrollerar om alla aktiviteter har täckts.
2. Om inte, startar algoritmen om den giriga uppdraget från det aktuella indexet – ett rekursivt steg som delar upp problemet girigt.
3. Om ja, återgår kontrollen 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 anropar schemaläggaren.
2. Ett nytt Scheduler-objekt instansieras.
3. Funktionen activity_select() returnerar en aktivitetspekare till anroparen när den giriga uppdraget är avslutat.

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

Den giriga metoden är inte lämplig för problem som kräver en optimal lösning för varje delproblem, såsom sortering.

I sådana fall kan den giriga metoden vara fel – i värsta fall producerar den en icke-optimal lösning.

Den största nackdelen med giriga algoritmer är att de väljer utan att veta vad som ligger framför det nuvarande giriga tillståndet.

Diagrammet nedan illustrerar denna nackdel med den giriga metoden.

I den giriga skanningen som visas här som ett träd (högre värde betyder högre girighet), skulle en algoritm vid värdet 40 välja 29 härnäst och sedan sluta på 12, för totalt 41.

Däremot skulle en söndra-och-härska-strategi följa 25 med 40 för totalt 65, vilket är 24 poäng högre än det lokalt giriga valet.

Exempel på giriga Algorithms

De flesta nätverksalgoritmer förlitar sig på en girig metod. Vanliga exempel på giriga algoritmer inkluderar:

• Prims minimala spannande trädalgoritm
• Problem med den resande säljaren (ungefärligt)
• Färgläggning av grafkarta
• Kruskals minimala spannande trädalgoritm
• Dijkstras kortaste vägalgoritm
• Grafhörnskydd
• Knapsäcksproblem
• Jobbsekvensering med deadlines

Vanliga frågor