Hebzuchtig algoritme met voorbeelden: hebzuchtige methode & Nadering

Wat is een hebzuchtig algoritme?

In Greedy Algorithm wordt een set bronnen recursief verdeeld op basis van de maximale, onmiddellijke beschikbaarheid van die bron in elk stadium van uitvoering.

Om een ​​probleem op te lossen op basis van de hebzuchtige benadering, zijn er twee fasen

1. De lijst met items scannen
2. Optimalisatie

Deze fasen worden parallel behandeld in deze Greedy-algoritme-tutorial, tijdens het verdelen van de array.

Om de hebzuchtige benadering te begrijpen, moet u praktische kennis hebben van recursie en contextomschakeling. Dit helpt u te begrijpen hoe u de code kunt traceren. U kunt het hebzuchtige paradigma definiëren in termen van uw eigen noodzakelijke en voldoende verklaringen.

Twee voorwaarden bepalen het hebzuchtige paradigma.

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

Laten we, terwijl het theoretiseren voortgaat, de geschiedenis beschrijven die verband houdt met de Greedy-zoekbenadering.

In deze Greedy-algoritme-tutorial leer je:

• Geschiedenis van hebzuchtige algoritmen
• Hebzuchtige strategieën en beslissingen
• Kenmerken van de hebzuchtige benadering
• Waarom de hebzuchtige benadering gebruiken?
• Hoe u het probleem met de selectie van activiteiten kunt oplossen
• Architectuur van de hebzuchtige benadering
• Nadelen van hebzuchtige algoritmen

Geschiedenis van hebzuchtige algoritmen

Hier is een belangrijke mijlpaal van hebzuchtige algoritmen:

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

Hebzuchtige strategieën en beslissingen

Logica in zijn gemakkelijkste vorm kwam neer op "hebzuchtig" of "niet hebzuchtig". Deze uitspraken werden bepaald door de aanpak die werd gevolgd om vooruitgang te boeken in elke algoritmefase.

Het algoritme van Djikstra maakte bijvoorbeeld gebruik van een stapsgewijze hebzuchtige strategie om hosts op 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" is.

Kortom, een algoritme houdt op hebzuchtig te zijn als het op enig moment een stap zet die niet plaatselijk hebberig is. De Greedy-problemen stoppen zonder verdere hebzucht.

Kenmerken van de hebzuchtige benadering

De belangrijkste kenmerken van een Greedy-methode-algoritme zijn:

• Er is een geordende lijst met middelen, met kosten of waardetoekenningen. Deze kwantificeren beperkingen op een systeem.
• U neemt de maximale hoeveelheid resources in de tijd dat een beperking van toepassing is.
• Bij een probleem met activiteitenplanning zijn de resourcekosten bijvoorbeeld in uren en moeten de activiteiten in seriële volgorde worden uitgevoerd.

Waarom de hebzuchtige benadering gebruiken?

Hier zijn de redenen om de hebzuchtige aanpak te gebruiken:

• De hebzuchtige benadering heeft een paar afwegingen, die het geschikt kunnen maken voor optimalisatie.
• Een belangrijke reden is om direct tot de meest haalbare oplossing te komen. Als in 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 splitsen op basis van een conditie, zonder dat alle oplossingen gecombineerd hoeven te worden.
• In het activiteitsselectieprobleem wordt de stap "recursieve verdeling" bereikt door een lijst met items slechts één keer te scannen en bepaalde activiteiten in overweging te nemen.

Hoe u het probleem met de selectie van activiteiten kunt oplossen

In het voorbeeld van een activiteitsplanning is er voor elke activiteit een "start-" en "eindtijd". Elke activiteit wordt ter referentie geïndexeerd door een nummer. Er zijn twee activiteitscategorieën.

1. overwogen activiteit : is de activiteit, de referentie van waaruit de mogelijkheid om meer dan één resterende activiteit te doen, wordt geanalyseerd.
2. overige activiteiten: activiteiten op een of meer indexen voorafgaand aan de beschouwde activiteit.

De totale duur geeft de kosten van het uitvoeren van de activiteit weer. Dat wil zeggen (finish - start) geeft ons de duur als de kosten van een activiteit.

U zult leren dat de hebzuchtige mate het aantal resterende activiteiten is dat u kunt uitvoeren in de tijd van een weloverwogen activiteit.

Architectuur van de hebzuchtige benadering

STAP 1)

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

STAP 2)

Wanneer meer activiteiten tegen de tijd kunnen worden voltooid, is de betreffende activiteit afgelopen, begin dan met zoeken naar een of meer resterende activiteiten.

STAP 3)

Als er geen resterende activiteiten meer zijn, wordt de huidige resterende activiteit de volgende overwogen activiteit. Herhaal stap 1 en stap 2 met de nieuw overwogen activiteit. Ga naar stap 4 als er geen activiteiten meer zijn.

STAP 4 )

Retourneer de unie van overwogen indices. Dit zijn de activiteitsindices die zullen worden gebruikt om de doorvoer te maximaliseren.

Code Verklaring

#include#include#include#define MAX_ACTIVITIES 12

Toelichting code:

1. Opgenomen header-bestanden / klassen
2. Een max. Aantal activiteiten geleverd door de gebruiker.

using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Toelichting code:

1. De naamruimte voor streaming-bewerkingen.
2. Een klassendefinitie voor TIJD
3. Een uur tijdstempel.
4. Een TIME-standaardconstructor
5. De uren variabel.

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

Toelichting code:

1. Een klassendefinitie van 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 schedulerklasse.
2. Overwogen Index is het startpunt voor het scannen van de array.
3. De initialisatie-index wordt gebruikt om willekeurige tijdstempels toe te wijzen.
4. Een reeks activiteitsobjecten wordt dynamisch toegewezen met behulp van de nieuwe operator.
5. De geplande aanwijzer definieert de huidige basislocatie voor hebzucht.

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

Toelichting code:

1. De planner-constructor - deel 2 van de scheduler-klassedefinitie.
2. De beschouwde index bepaalt de huidige start van de huidige scan.
3. De huidige hebzuchtige omvang is in het begin niet gedefinieerd.

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 einduren van elk van de momenteel geplande activiteiten te initialiseren.
2. Starttijdinitialisatie.
3. Eindtijdinitialisatie altijd na of precies op het startuur.
4. Een foutopsporingsinstructie 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 schedulerklasse.
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 scoopresolutie-operator (: :) wordt de functiedefinitie gegeven.
2. De beschouwde index is de index die wordt aangeroepen op basis van waarde. De greedy_extent is de geïnitialiseerde slechts een 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 beschouwde activiteit (gegeven door overwogen index) zou eindigen.
3. Zolang dit mogelijk is, wordt een optionele debug-instructie afgedrukt.
4. Ga door naar de volgende index in de activiteitenmatrix

… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Toelichting code:

1. De voorwaardelijke controleert of alle activiteiten zijn gedekt.
2. Als dit niet het geval is, kunt u uw hebzucht opnieuw starten met de overwogen 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 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 belangrijkste functie die wordt gebruikt om de planner aan te roepen.
2. Een nieuwe Scheduler wordt geïnstantieerd.
3. De activiteitselectiefunctie, die een aanwijzer van het type activiteit retourneert, komt terug naar de beller nadat de hebzuchtige zoektocht voorbij is.

Uitgang:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Nadelen van hebzuchtige algoritmen

Het is niet geschikt voor Greedy-problemen waar voor elk deelprobleem een ​​oplossing nodig is, zoals sorteren.

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

Daarom is het nadeel van hebzuchtige algoritmen dat ze niet weten wat de huidige hebzuchtige staat te wachten staat.

Hieronder ziet u een afbeelding 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 heeft gekozen of een veroveringsstrategie heeft aangenomen. 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 hebzuchtige algoritmen

De meeste netwerkalgoritmen gebruiken de hebzuchtige benadering. Hier is een lijst met enkele voorbeelden van Greedy-algoritmen:

• Prim's Minimal Spanning Tree-algoritme
• Handelsreiziger probleem
• Grafiek - Kaartkleuring
• Kruskal's Minimal Spanning Tree-algoritme
• Dijkstra's Minimal Spanning Tree-algoritme
• Grafiek - Vertex Cover
• Knapzak probleem
• Probleem met taakplanning

Overzicht:

Samenvattend, het artikel definieerde het hebzuchtige paradigma, liet zien hoe hebzuchtige optimalisatie en recursie u tot op zekere hoogte kunnen helpen de beste oplossing te vinden. Het Greedy-algoritme wordt op grote schaal toegepast voor het oplossen van problemen in vele talen, zoals het Greedy-algoritme Python, C, C #, PHP, Java, enz. nadering. Uiteindelijk werden de nadelen van het gebruik van de hebzuchtige benadering uitgelegd.