Grådig algoritme med eksempel: Hvad er, metode og tilgang

Hvad er en grådig algoritme?

A Grådig algoritme opdeler rekursivt et sæt ressourcer baseret på den maksimale umiddelbare tilgængelighed af den pågældende ressource på ethvert trin i udførelsen.

Løsning af et problem med den grådige tilgang har to faser:

1. Scanner listen over elementer
2. Optimering

Begge trin kører parallelt, da input-arrayet progressivt opdeles.

For at følge den grådige tilgang hjælper et praktisk kendskab til rekursion og kontekstskift dig. trace koden. Det grådige paradigme kan beskrives med et par nødvendige og tilstrækkelige udsagn.

To forhold definerer det grådige paradigme.

• Hvert trinvis valg skal styre problemet mod dets bedst accepterede løsning.
• Problemstrukturen skal stoppe i et endeligt antal grådige trin.

Med teorien på plads, lad os se på historien bag den grådige søgemetode.

Grådigheds historie Algorithms

Her er de vigtige milepæle i historien om grådige algoritmer:

• Grådige algoritmer blev først konceptualiseret som grafvandringsalgoritmer i 1950'erne.
• Edsger Dijkstra udviklede sin korteste-vej-algoritme til at forkorte ruter gennem den hollandske hovedstad, Amsterdam.
• I samme årti udviklede Prim og Kruskal optimeringsstrategier, der minimerer stiomkostninger langs vægtede ruter for at bygge minimalt udspændende træer.
• I 70'erne beskrev de amerikanske forskere Cormen, Leiserson, Rivest og Stein rekursiv substrukturering af grådige løsninger i deres klassiske ... Introduction to Algorithms lærebog.
• Det grådige søgeparadigme blev katalogiseret som en særskilt optimeringsstrategi i NIST-optegnelserne i 2005.
• Den dag i dag bruger webprotokoller som Open Shortest Path First (OSPF) og mange pakkekoblingsprotokoller den grådige strategi til at minimere transittiden på et netværk.

Grådige strategier og beslutninger

Logikken reduceres til et binært valg i hvert trin — "grådig" eller "ikke grådig" — baseret på den retning, algoritmen tager for at fremskride.

For eksempel identificerer Dijkstras algoritme værter på internettet ved at evaluere en omkostningsfunktion i hvert trin. Den værdi, som omkostningsfunktionen returnerer, afgør, om den næste sti er "grådig" eller "ikke-grådig".

Kort sagt holder en algoritme op med at være grådig i det øjeblik, den tager et skridt, der ikke er lokalt optimalt, og grådige problemer ophører, når intet yderligere grådigt skridt er muligt.

Karakteristika for den grådige algoritme

De vigtige egenskaber ved en grådig algoritme er:

• En ordnet liste over ressourcer bærer omkostnings- eller værdiattributioner, der kvantificerer begrænsningerne på systemet.
• Algoritmen bruger den maksimale mængde ressourcer inden for den tid, en begrænsning gælder.
• For eksempel måles ressourceomkostningerne i et aktivitetsplanlægningsproblem i timer, og aktiviteterne skal udføres i seriel rækkefølge.

Hvorfor bruge den grådige tilgang?

Her er grundene til at bruge den grådige tilgang:

• Den grådige tilgang har afvejninger, der gør den velegnet til optimering.
• Den mest oplagte grund er at kunne producere en brugbar løsning med det samme. I aktivitetsudvælgelsesproblemet, der diskuteres nedenfor, kan flere aktiviteter planlægges i samme vindue, hvis de passer ind, før den aktuelle aktivitet slutter.
• En anden grund er, at den opdeler et problem rekursivt baseret på en betingelse, uden behov for at flette delløsninger.
• I aktivitetsudvælgelsesproblemet opnås det rekursive divisionstrinn ved at scanne listen én gang og kun tage de berettigede aktiviteter i betragtning.

Sådan løser du problemet med aktivitetsudvælgelse

I eksemplet med aktivitetsplanlægning har hver aktivitet et start- og sluttidspunkt og er indekseret med et tal som reference. Der er to aktivitetskategorier:

1. Overvejet aktivitet: referenceaktiviteten, hvorfra evnen til at passe flere resterende aktiviteter måles.
2. Resterende aktiviteter: aktiviteter på et eller flere indekser forud for den betragtede aktivitet.

Omkostningerne ved at udføre en aktivitet er dens varighed, beregnet som (slut - start).

Det grådige omfang er simpelthen antallet af resterende aktiviteter, der kan udføres inden for tidsrummet for en betragtet aktivitet.

ArchiTecture of the Greedy Approach

Trin 1) Scan listen over aktivitetsomkostninger startende med indeks 0 som det betragtede indeks.

Trin 2) Når flere aktiviteter kan afsluttes, inden den pågældende aktivitet slutter, skal du søge efter de resterende aktiviteter.

Trin 3) Hvis der ikke kan planlægges flere aktiviteter, bliver den nuværende resterende aktivitet den næste aktivitet, der overvejes. Gentag trin 1 og trin 2 med den nye aktivitet. Hvis der ikke er flere aktiviteter tilbage, skal du gå til trin 4.

Trin 4) Returner foreningen af ​​​​betragtede indeks — dette er de aktivitetsindekser, der maksimerer gennemløbshastigheden.

ArchiTecture of the Greedy Approach

Code Forklaring

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

#define MAX_ACTIVITIES 12

Forklaring af kode:

1. Inkluderede header-filer/klasser
2. Det maksimale antal aktiviteter, som brugeren kan konfigurere.

using namespace std;

class TIME
{
    public:
    int hours;

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

Forklaring af kode:

1. Deklarerer standardnavneområdet for streaminghandlinger.
2. En klassedefinition for TID
3. Et times tidsstempel.
4. En TIME standard konstruktør
5. Timerne varierer.

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

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

Forklaring af kode:

1. En klassedefinition for Aktivitet.
2. Tidsstempler, der tilsammen definerer en varighed.
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 af kode:

1. Del 1 af planlægningsklassens definition.
2. considered_index er udgangspunktet for scanning af arrayet.
3. init_index bruges til at tildele tilfældige tidsstempler under opsætningen.
4. En matrix af aktivitetsobjekter allokeres dynamisk med den nye operator.
5. Den planlagte pointer indeholder det aktuelle grådige resultat.

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

Forklaring af kode:

1. Scheduler-konstruktøren — del 2 af klassedefinitionen.
2. considered_index markerer starten på den aktuelle scanning.
3. Det grådige omfang er udefineret 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 af kode:

1. En for-løkke initialiserer start- og sluttidspunkterne for hver planlagt aktivitet.
2. Initialiserer starttidspunktet.
3. Initialiserer sluttidspunktet til at være på eller efter starttimen.
4. En debug-sætning udskriver de tildelte varigheder.

	public:
   		 Activity * activity_select(int);
};

Forklaring af kode:

1. Del 4 — den sidste del af definitionen af ​​Scheduler-klassen.
2. activity_select() tager et startindeks som basis og opdeler den grådige mission i delproblemer.

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

1. Scope-opløsningsoperatoren (::) forbinder funktionsdefinitionen med Scheduler-klassen.
2. considered_index sendes med værdi, og greedy_extent initialiseres til indekset umiddelbart efter 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 af kode:

1. Kernelogikken — det grådige omfang er begrænset til MAX_ACTIVITIES.
2. Starttidspunktet for den aktuelle aktivitet sammenlignes med sluttidspunktet for den pågældende aktivitet.
3. Så længe betingelsen er gældende, udskrives en valgfri fejlfindingssætning.
4. Den grådige grad går derefter videre til det næste indeks i aktivitetsarrayet.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Forklaring af kode:

1. Betingelsen kontrollerer, om alle aktiviteter er dækket.
2. Hvis ikke, genstarter algoritmen den grådige mission fra det aktuelle indeks - et rekursivt trin, der opdeler problemet grådigt.
3. Hvis ja, vender kontrollen tilbage til den, der ringer, uden mulighed for at udvide grådighed.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Forklaring af kode:

1. Hovedfunktionen aktiverer Scheduler.
2. Et nyt Scheduler-objekt instantieres.
3. Funktionen activity_select() returnerer en aktivitetspointer til den, der kalder, når den grådige mission er afsluttet.

Output:

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ænsninger af Greedy Technique

Den grådige tilgang er ikke egnet til problemer, der kræver en optimal løsning for hvert delproblem, såsom sortering.

I sådanne tilfælde kan den grådige metode være forkert – i værste fald producerer den en ikke-optimal løsning.

Den væsentligste ulempe ved grådige algoritmer er, at de vælger uden at vide, hvad der ligger forude i den nuværende grådige tilstand.

Diagrammet nedenfor illustrerer denne ulempe ved den grådige metode.

I den grådige scanning vist her som et træ (højere værdi betyder højere grådighed), ville en algoritme med værdien 40 vælge 29 som det næste og derefter ende ved 12, for i alt 41.

I modsætning hertil ville en del-og-hersk-strategi følge 25 med 40 for i alt 65, hvilket er 24 point højere end det lokalt grådige valg.

Eksempler på Greedy Algorithms

De fleste netværksalgoritmer er afhængige af en grådig tilgang. Almindelige eksempler på grådige algoritmer inkluderer:

• Prims Minimum Spanning Tree-algoritme
• Problem med den rejsende sælger (omtrentlig)
• Farvelægning af grafkort
• Kruskals Minimum Spanning Tree-algoritme
• Dijkstras korteste vej-algoritme
• Graf-toppunktdæksel
• Rullesæk problem
• Jobsekvensering med deadlines

Ofte Stillede Spørgsmål