Grådig algoritme med eksempel: Hva er, metode og tilnærming

Hva er en grådig algoritme?

A Grådig algoritme deler rekursivt et sett med ressurser basert på den maksimale umiddelbare tilgjengeligheten av ressursen på ethvert trinn i utførelsen.

Å løse et problem med den grådige tilnærmingen har to trinn:

1. Skanner listen over elementer
2. Optimalisering

Begge trinnene kjører parallelt ettersom inngangsmatrisen deles progressivt.

For å følge den grådige tilnærmingen, hjelper det deg med praktisk kunnskap om rekursjon og kontekstbytte. trace koden. Det grådige paradigmet kan beskrives med et par nødvendige og tilstrekkelige utsagn.

To forhold definerer det grådige paradigmet.

• Hvert trinnvise valg må styre problemet mot den best aksepterte løsningen.
• Problemstrukturen må stoppe i et endelig antall grådige trinn.

Med teorien på plass, la oss se på historien bak den grådige søkemetoden.

Greedys historie Algorithms

Her er de viktige landemerkene i historien til grådige algoritmer:

• Grådige algoritmer ble først konseptualisert for grafvandringsalgoritmer på 1950-tallet.
• Edsger Dijkstra utviklet sin korteste-vei-algoritme for å forkorte ruter gjennom den nederlandske hovedstaden Amsterdam.
• I samme tiår utviklet Prim og Kruskal optimaliseringsstrategier som minimerer stikostnader langs vektede ruter for å bygge minimale spenntrær.
• På 70-tallet beskrev de amerikanske forskerne Cormen, Leiserson, Rivest og Stein rekursiv substrukturering av grådige løsninger i sin klassiske ... Introduction to Algorithms lærebok.
• Det grådige søkeparadigmet ble katalogisert som en distinkt optimaliseringsstrategi i NIST-registrene i 2005.
• Den dag i dag bruker webprotokoller som Open Shortest Path First (OSPF) og mange pakkesvitsjeprotokoller den grådige strategien for å minimere transitttiden på et nettverk.

Grådige strategier og beslutninger

Logikken reduseres til et binært valg på hvert trinn – «grådig» eller «ikke grådig» – basert på retningen algoritmen tar for å avansere.

For eksempel identifiserer Dijkstras algoritme verter på Internett ved å evaluere en kostnadsfunksjon i hvert trinn. Verdien kostnadsfunksjonen returnerer avgjør om den neste banen er «grådig» eller «ikke-grådig».

Kort sagt, en algoritme slutter å være grådig i det øyeblikket den tar et skritt som ikke er lokalt optimalt, og grådige problemer stopper når ingen ytterligere grådige skritt er mulig.

Kjennetegn på den grådige algoritmen

De viktige egenskapene til en grådig algoritme er:

• En ordnet liste over ressurser har kostnads- eller verdiattributsjoner som kvantifiserer begrensningene på systemet.
• Algoritmen tar den maksimale mengden ressurser innenfor den tiden en begrensning gjelder.
• For eksempel, i et aktivitetsplanleggingsproblem måles ressurskostnadene i timer, og aktivitetene må utføres i seriell rekkefølge.

Hvorfor bruke den grådige tilnærmingen?

Her er grunnene til å bruke den grådige tilnærmingen:

• Den grådige tilnærmingen har avveininger som gjør den godt egnet for optimalisering.
• Den mest åpenbare grunnen er å kunne produsere en gjennomførbar løsning umiddelbart. I aktivitetsutvelgelsesproblemet som diskuteres nedenfor, kan flere aktiviteter planlegges i samme vindu hvis de får plass før den gjeldende aktiviteten er ferdig.
• En annen grunn er at den deler et problem rekursivt basert på en betingelse, uten behov for å slå sammen delløsninger.
• I aktivitetsutvalgsproblemet oppnås det rekursive divisjonstrinnet ved å skanne listen én gang og kun vurdere de kvalifiserte aktivitetene.

Slik løser du problemet med aktivitetsvalg

I eksempelet med aktivitetsplanlegging har hver aktivitet en start- og sluttid og er indeksert med et tall som referanse. Det finnes to aktivitetskategorier:

1. Vurdert aktivitet: referanseaktiviteten som evnen til å få plass til flere gjenværende aktiviteter måles ut fra.
2. Gjenværende aktiviteter: aktiviteter på en eller flere indekser foran den betraktede aktiviteten.

Kostnaden ved å utføre en aktivitet er dens varighet, beregnet som (slutt – start).

Den grådige omfanget er rett og slett antallet gjenværende aktiviteter som kan utføres innenfor tiden for en vurdert aktivitet.

ArchiTecture of the Greedy Approach

Trinn 1) Skann listen over aktivitetskostnader som starter med indeks 0 som den vurderte indeksen.

Trinn 2) Når flere aktiviteter kan fullføres innen den aktuelle aktiviteten er ferdig, søk etter de gjenværende aktivitetene.

Trinn 3) Hvis det ikke kan planlegges flere aktiviteter, blir den gjeldende gjenværende aktiviteten den neste aktiviteten som vurderes. Gjenta trinn 1 og trinn 2 med den nye aktiviteten som vurderes. Hvis det ikke er noen aktiviteter igjen, gå til trinn 4.

Trinn 4) Returner foreningen av vurderte indekser – dette er aktivitetsindeksene som maksimerer gjennomstrømningen.

ArchiTecture of the Greedy Approach

Code Forklaring

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

#define MAX_ACTIVITIES 12

Forklaring av kode:

1. Inkludert header-filer/klasser
2. Maksimalt antall aktiviteter som kan konfigureres av brukeren.

using namespace std;

class TIME
{
    public:
    int hours;

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

Forklaring av kode:

1. Deklarerer standard navneområde for strømmeoperasjoner.
2. En klassedefinisjon for TID
3. Et times tidsstempel.
4. En TIME standard konstruktør
5. Timene varierer.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Forklaring av kode:

1. En klassedefinisjon for Aktivitet.
2. Tidsstempler som til sammen definerer en varighet.
3. Alle tidsstempler 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 planleggingsklassens definisjon.
2. considered_index er utgangspunktet for å skanne arrayet.
3. init_index brukes til å tilordne tilfeldige tidsstempler under oppsettet.
4. En matrise med aktivitetsobjekter tildeles dynamisk med den nye operatoren.
5. Den planlagte pekeren inneholder det gjeldende grådige resultatet.

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

Forklaring av kode:

1. Planleggerkonstruktøren – del 2 av klassedefinisjonen.
2. considered_index markerer starten på gjeldende skanning.
3. Det 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);
 }
&#8230;
&#8230;

Forklaring av kode:

1. En for-løkke initialiserer start- og sluttidspunktet for hver planlagte aktivitet.
2. Initialiserer starttidspunktet.
3. Initialiserer sluttidspunktet til å være på eller etter starttimen.
4. En feilsøkingssetning skriver ut de tildelte varighetene.

	public:
   		 Activity * activity_select(int);
};

Forklaring av kode:

1. Del 4 – den siste delen av definisjonen av Scheduler-klassen.
2. activity_select() tar en startindeks som base og deler det grådige oppdraget inn i delproblemer.

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

1. Omfangsoppløsningsoperatoren (::) kobler funksjonsdefinisjonen til Scheduler-klassen.
2. considered_index sendes med verdi, og greedy_extent initialiseres til indeksen rett etter den.

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;
...

Forklaring av kode:

1. Kjernelogikken – den grådige omfanget er begrenset til MAX_ACTIVITIES.
2. Starttidspunktet for den gjeldende aktiviteten kontrolleres mot sluttidspunktet for den aktuelle aktiviteten.
3. Så lenge betingelsen er oppfylt, skrives det ut en valgfri feilsøkingssetning.
4. Den grådige graden går deretter videre til neste indeks i aktivitetsmatrisen.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Forklaring av kode:

1. Betingelsen sjekker om alle aktiviteter er dekket.
2. Hvis ikke, starter algoritmen det grådige oppdraget på nytt fra gjeldende indeks – et rekursivt trinn som deler problemet grådig.
3. Hvis ja, returnerer kontrollen til den som ringer uten rom for å 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 aktiverer planleggeren.
2. Et nytt Scheduler-objekt instansieres.
3. Funksjonen activity_select() returnerer en aktivitetspeker til den som ringer når det grådige oppdraget er avsluttet.

Utgang:

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

Begrensninger av Greedy Technique

Den grådige tilnærmingen er ikke egnet for problemer som krever en optimal løsning for hvert delproblem, for eksempel sortering.

I slike tilfeller kan den grådige metoden være feil – i verste fall produserer den en ikke-optimal løsning.

Den viktigste ulempen med grådige algoritmer er at de velger uten å vite hva som ligger foran den nåværende grådige tilstanden.

Diagrammet nedenfor illustrerer denne ulempen med den grådige metoden.

I den grådige skanningen vist her som et tre (høyere verdi betyr høyere grådighet), ville en algoritme med verdi 40 velge 29 neste, og deretter ende på 12, for totalt 41.

I motsetning til dette ville en splitt-og-hersk-strategi følge 25 med 40 for totalt 65, som er 24 poeng høyere enn det lokalt grådige valget.

Eksempler på Greedy Algorithms

De fleste nettverksalgoritmer er avhengige av en grådig tilnærming. Vanlige eksempler på grådige algoritmer inkluderer:

• Prims minimumsspenntrealgoritme
• Problem med reisende selger (omtrentlig)
• Fargelegging av grafkart
• Kruskals Minimum Spanning Tree-algoritme
• Dijkstras korteste vei-algoritme
• Graf-node-deksel
• Rullesekk problem
• Jobbsekvensering med tidsfrister

Spørsmål og svar