Hebzuchtig algoritme

Wat betekent een hebzuchtig algoritme?

Een hebzuchtig algortime is een algoritmische strategie die in elke kleine stap de beste optimale keuze maakt met als doel dat dit uiteindelijk leidt tot een globaal optimale oplossing. Dit betekent dat het algoritme de beste oplossing op dat moment kiest zonder rekening te houden met de gevolgen. Het kiest de beste onmiddellijke output, maar houdt geen rekening met het grote geheel.

Techopedia legt uit wat een hebzuchtig algoritme is

Een hebzuchtig algoritme werkt door in elke stap het best mogelijke antwoord te kiezen en dan door te gaan naar de volgende stap totdat het het einde bereikt. Hierbij houdt het algoritme geen rekening met de context van het grote plaatje. Het hoopt alleen dat het pad de optimale route kiest, maar zoals keer op keer wordt bewezen, levert deze methode niet vaak een globaal optimale oplossing op. In feite is het heel goed mogelijk dat de meest optimale kortetermijnoplossingen leiden tot de slechtst mogelijke globale uitkomst.

Zie het als het nemen van veel kortere wegen in een productiebedrijf: op de korte termijn worden grote bedragen bespaard op de productiekosten, maar dit leidt uiteindelijk tot achteruitgang omdat de kwaliteit in het gedrang komt, wat resulteert in productretouren en lage verkoopcijfers omdat klanten vertrouwd raken met het “goedkope” product. Maar dit is niet altijd het geval, er zijn veel toepassingen waarbij het hebzuchtige algoritme het beste werkt om de globaal optimale oplossing te vinden of te benaderen, zoals bij het construeren van een Huffman-boom.

Bijvoorbeeld: Neem het pad met de grootste totale som. Een hebzuchtig algoritme zou het blauwe pad nemen, als gevolg van kortzichtigheid, in plaats van het oranje pad, dat de grootste som oplevert.

Componenten:

• Een kandidaatfunctie in de vorm van complexe data dat een oplossing nodig heeft
• Een selectiefunctie die de beste bijdrage aan de uiteindelijke oplossing kiest
• Een haalbaarheidsfunctie die de selectiefunctie helpt door te bepalen of een kandidaat kan bijdragen aan de oplossing
• Een objectiefunctie die een waarde toekent aan een gedeeltelijke oplossing
• Een oplossingsfunctie die aangeeft dat de optimale oplossing is ontdekt