Hebzuchtig algoritme met voorbeeld: wat is, methode en aanpak

Om de hebzuchtige aanpak te begrijpen, moet je praktische kennis hebben van recursie en contextwisseling. Dit helpt u te begrijpen hoe u de code kunt traceren. Je kunt het hebzuchtige paradigma definiëren in termen van je eigen noodzakelijke en voldoende uitspraken.

Er zijn twee voorwaarden die het hebzuchtige paradigma definiëren.

• Elke stapsgewijze oplossing moet een probleem structureren in de richting van de meest geaccepteerde oplossing.
• Het is voldoende als de structurering van het probleem in een eindig aantal hebzuchtige stappen kan stoppen.

Laten we, terwijl we doorgaan met het theoretiseren, de geschiedenis beschrijven die verband houdt met de Greedy Search-aanpak.

Geschiedenis van hebzuchtig Algorithms

Dit is een belangrijk kenmerk van hebzuchtige algoritmen:

• Greedy-algoritmen werden in de jaren vijftig voor veel graafloopalgoritmen bedacht.
• Esdger Djikstra conceptualiseerde het algoritme om minimaal opspannende bomen te genereren. Hij wilde de reikwijdte van de routes binnen de Nederlandse hoofdstad Amsterdam verkorten.
• In hetzelfde decennium bereikten Prim en Kruskal optimalisatiestrategieën die waren gebaseerd op het minimaliseren van de padkosten langs gewogen routes.
• In de jaren '70 stelden de Amerikaanse onderzoekers Cormen, Rivest en Stein in hun klassieke inleiding tot algoritmen een recursieve substructurering van gulzige oplossingen voor.
• Het Greedy-zoekparadigma werd in 2005 geregistreerd als een ander type optimalisatiestrategie in de NIST-records.
• Tot nu toe gebruiken protocollen die het internet beheren, zoals het open-shortest-path-first (OSPF) en vele andere netwerkpakketschakelingsprotocollen, de hebzuchtige strategie om de tijd die aan een netwerk wordt besteed tot een minimum te beperken.

Hebzuchtige strategieën en beslissingen

Logica in zijn eenvoudigste vorm kwam neer op ‘hebzuchtig’ of ‘niet hebzuchtig’. Deze uitspraken werden gedefinieerd door de aanpak die werd gevolgd om vooruitgang te boeken in elke algoritmefase.

Djikstra's algoritme gebruikte bijvoorbeeld een stapsgewijze hebzuchtige strategie om hosts op het internet te identificeren door een kostenfunctie te berekenen. De waarde die door de kostenfunctie werd geretourneerd, bepaalde of het volgende pad "hebzuchtig" of "niet-hebzuchtig" was.

Kortom, een algoritme houdt op hebzuchtig te zijn als het op enig moment een stap zet die lokaal niet hebzuchtig is. De hebzuchtige problemen houden op zonder verdere hebzucht.

Kenmerken van het hebzuchtige algoritme

De belangrijke kenmerken van een Greedy-algoritme zijn:

• Er is een geordende lijst met bronnen, met kosten- of waardetoeschrijvingen. Deze kwantificeren de beperkingen van een systeem.
• U neemt de maximale hoeveelheid grondstoffen in de tijd dat er een beperking geldt.
• Bij een probleem met activiteitenplanning worden de resourcekosten bijvoorbeeld in uren weergegeven en moeten de activiteiten in seriële volgorde worden uitgevoerd.

Waarom de hebzuchtige aanpak gebruiken?

Hier zijn de redenen om de hebzuchtige aanpak te gebruiken:

• De hebzuchtige benadering heeft enkele nadelen, waardoor deze geschikt kan zijn voor optimalisatie.
• Een prominente reden is om onmiddellijk tot de meest haalbare oplossing te komen. Als er bij het activiteitselectieprobleem (hieronder uitgelegd) meer activiteiten kunnen worden gedaan voordat de huidige activiteit is voltooid, kunnen deze activiteiten binnen dezelfde tijd worden uitgevoerd.
• Een andere reden is om een ​​probleem recursief op te delen op basis van een voorwaarde, zonder dat alle oplossingen hoeven te worden gecombineerd.
• Bij het activiteitselectieprobleem wordt de stap ‘recursieve deling’ bereikt door een lijst met items slechts één keer te scannen en bepaalde activiteiten in overweging te nemen.

Hoe het activiteitselectieprobleem op te lossen

In het voorbeeld van de activiteitenplanning is er voor elke activiteit een start- en eindtijd. Elke activiteit wordt ter referentie geïndexeerd met een nummer. Er zijn twee categorieën activiteiten.

1. beschouwde activiteit: is de activiteit, de referentie op basis waarvan het vermogen om meer dan één resterende activiteit uit te voeren, wordt geanalyseerd.
2. overige activiteiten: activiteiten op een of meer indexen vóór de beschouwde activiteit.

De totale duur geeft de kosten weer van het uitvoeren van de activiteit. Dat wil zeggen (eind – begin) geeft ons de duur als de kosten van een activiteit.

Je zult leren dat de hebzuchtige omvang het aantal resterende activiteiten is dat je kunt uitvoeren in de tijd van een overwogen activiteit.

Architectie van de Greedy-aanpak

STAP 1) Scan de lijst met activiteitskosten, beginnend met index 0 als de beschouwde index.

STAP 2) Wanneer er meer activiteiten kunnen worden afgerond tegen de tijd dat de betreffende activiteit is afgelopen, kunt u beginnen met zoeken naar een of meer resterende activiteiten.

STAP 3) Als er geen resterende activiteiten meer zijn, wordt de huidige resterende activiteit de volgende beschouwde activiteit. Herhaal stap 1 en stap 2, met de nieuw overwogen activiteit. Als er geen activiteiten meer over zijn, ga dan naar stap 4.

STAP 4 ) Retourneert de unie van beschouwde indices. Dit zijn de activiteitsindices die zullen worden gebruikt om de doorvoer te maximaliseren.

Code Uitleg

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

#define MAX_ACTIVITIES 12

Toelichting code:

1. Inbegrepen headerbestanden/klassen
2. Een maximaal aantal activiteiten aangeboden door de gebruiker.

using namespace std;

class TIME
{
    public:
    int hours;

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

Toelichting code:

1. De naamruimte voor streamingbewerkingen.
2. Een klassedefinitie voor TIME
3. Een tijdstempel van een uur.
4. Een TIME-standaardconstructor
5. De uren zijn variabel.

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

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

Toelichting code:

1. Een klassedefinitie uit activiteit
2. Tijdstempels die een duur definiëren
3. Alle tijdstempels worden in de standaardconstructor op 0 geïnitialiseerd

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

Toelichting code:

1. Deel 1 van de definitie van de plannerklasse.
2. Considered Index is het startpunt voor het scannen van de reeks.
3. De initialisatie-index wordt gebruikt om willekeurige tijdstempels toe te wijzen.
4. Een reeks activiteitsobjecten wordt dynamisch toegewezen met behulp van de operator new.
5. De geplande aanwijzer definieert de huidige basislocatie voor hebzucht.

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

Toelichting code:

1. De plannerconstructor – deel 2 van de definitie van de plannerklasse.
2. De beschouwde index definieert het huidige begin van de huidige scan.
3. De huidige hebzuchtige omvang is aanvankelijk ongedefinieerd.

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

Toelichting code:

1. Een for-lus om de begin- en eindtijden van elk van de momenteel geplande activiteiten te initialiseren.
2. Initialisatie van de starttijd.
3. Initialisatie van de eindtijd altijd na of precies op het startuur.
4. Een debug-instructie om de toegewezen duur af te drukken.

	public:
   		 Activity * activity_select(int);
};

Toelichting code:

1. Deel 4 – het laatste deel van de definitie van de plannerklasse.
2. De activiteitsselectiefunctie neemt een startpuntindex als basis en verdeelt de hebzuchtige zoektocht in hebzuchtige subproblemen.

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

1. Met behulp van de scope-resolutieoperator (::) wordt de functiedefinitie opgegeven.
2. De beschouwde Index is de Index die op basis van waarde wordt genoemd. De greedy_extent is de geïnitialiseerde index na de beschouwde index.

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

Toelichting code:

1. De kernlogica: de hebzuchtige omvang is beperkt tot het aantal activiteiten.
2. De starturen van de huidige activiteit worden gecontroleerd als planbaar voordat de overwogen activiteit (gegeven door de overwogen index) zou eindigen.
3. Zolang dit mogelijk is, wordt een optionele debug-instructie afgedrukt.
4. Ga naar de volgende index op de activiteitenarray

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Toelichting code:

1. De voorwaardelijke controles controleren of alle activiteiten gedekt zijn.
2. Als dit niet het geval is, kunt u uw hebzuchtige herstart maken met de beschouwde Index als het huidige punt. Dit is een recursieve stap die de probleemstelling gretig verdeelt.
3. Zo ja, dan keert het terug naar de beller zonder enige ruimte voor hebzucht.

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

Toelichting code:

1. De hoofdfunctie die wordt gebruikt om de planner aan te roepen.
2. Er wordt een nieuwe planner gemaakt.
3. De activiteitselectiefunctie, die een aanwijzer van het type activiteit retourneert, komt terug naar de beller nadat de hebzuchtige zoektocht voorbij is.

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

Beperkingen van hebzuchtige techniek

Het is niet geschikt voor Greedy-problemen waarbij voor elk subprobleem, zoals sorteren, een oplossing nodig is.

Bij dergelijke oefenproblemen met Greedy-algoritmen kan de Greedy-methode verkeerd zijn; in het ergste geval zelfs tot een niet-optimale oplossing leiden.

Het nadeel van hebzuchtige algoritmen is dat men niet weet wat er in de toekomst gaat gebeuren in de huidige hebzuchtige staat.

Hieronder ziet u een weergave van het nadeel van de Greedy-methode:

In de hebzuchtige scan die hier wordt weergegeven als een boom (hogere waarde, hogere hebzucht), zal een algoritmestatus op waarde: 40 waarschijnlijk 29 als de volgende waarde aannemen. Verder eindigt zijn zoektocht op 12. Dit komt neer op een waarde van 41.

Als het algoritme echter een suboptimaal pad insloeg of een veroveringsstrategie hanteerde. dan zou 25 worden gevolgd door 40, en de algehele kostenverbetering zou 65 zijn, wat 24 punten hoger wordt gewaardeerd als een suboptimale beslissing.

Voorbeelden van hebzuchtig Algorithms

De meeste netwerkalgoritmen gebruiken de greedy-benadering. Hier is een lijst met enkele Greedy-algoritmevoorbeelden:

• Prim's Minimal Spanning Tree-algoritme
• Handelsreiziger probleem
• Grafiek – Kaartkleuren
• Het Minimal Spanning Tree-algoritme van Kruskal
• Het minimaal overspannende boomalgoritme van Dijkstra
• Grafiek – Hoekpuntdekking
• Knapzak probleem
• Probleem met taakplanning

Samenvatting

Samenvattend, het artikel definieerde het hebzuchtige paradigma, liet zien hoe hebzuchtige optimalisatie en recursie u kunnen helpen de beste oplossing tot op zekere hoogte te verkrijgen. Het hebzuchtige algoritme wordt in veel talen breed toegepast voor probleemoplossing als hebzuchtig algoritme Python, C, C#, PHP, Java, enz. De activiteitenselectie van het Greedy-algoritme werd beschreven als een strategisch probleem dat maximale doorvoer zou kunnen bereiken met behulp van de hebzuchtige aanpak. Uiteindelijk werden de nadelen van het gebruik van de hebzuchtige benadering uitgelegd.