Inleiding tot hebzuchtig algoritme
Een strategie om problemen op te lossen. Greedy Algorithm wordt beschouwd als een van de benaderingen die worden gebruikt om problemen op te lossen. Deze probleemoplossende ketter hoort bij het maken van een keuze die op dat moment het beste lijkt. Deze aanpak wordt het best gebruikt om optimalisatieproblemen op te lossen. Optimalisatieproblemen kunnen worden gedefinieerd als problemen die minimale of maximale resultaten vereisen. Een hebzuchtig algoritme is een eenvoudigste en meest eenvoudige aanpak die kan worden gebruikt om een optimale oplossing te bereiken.
Wat is hebzuchtig algoritme?
Greedy Algorithm is een algoritmische strategie die wordt gebruikt om in een zeer klein stadium de beste optionele keuze te maken en uiteindelijk een wereldwijd optimale oplossing uit te voeren. Dit algoritme kiest de best haalbare oplossing op dat moment zonder rekening te houden met de gevolgen. Hebzuchtige methode zegt dat het probleem moet worden opgelost in fasen waarin elke invoer wordt overwogen, aangezien deze invoer haalbaar is. Omdat deze benadering alleen gericht is op een onmiddellijk resultaat zonder rekening te houden met het grotere geheel, wordt dit als hebzuchtig beschouwd.
Het kernconcept definiëren
Tot nu toe weten we wat een hebzuchtig algoritme is en waarom het zo wordt genoemd. De onderstaande aanwijzingen zullen u het hebzuchtige algoritme op een betere manier laten begrijpen. Inmiddels is het heel duidelijk dat het hebzuchtige algoritme alleen werkt als er een probleem is; deze benadering is echter alleen van toepassing als we een voorwaarde of beperking voor dat probleem hebben.
Soorten problemen
- Minimalisatieprobleem: het is eenvoudig om een oplossing voor een probleem te vinden, aangezien aan alle voorwaarden is voldaan. Wanneer dit probleem echter een minimaal resultaat vereist, wordt dit een minimalisatieprobleem genoemd.
- Maximalisatieprobleem: een probleem dat het maximale resultaat vereist, wordt het maximalisatieprobleem genoemd.
- Optimalisatieprobleem: een probleem wordt optimalisatieprobleem genoemd wanneer het minimale of maximale resultaten vereist.
Soorten oplossingen
- Haalbare oplossing: wanneer er zich een probleem voordoet, hebben we veel plausibele oplossingen voor dit probleem. Maar rekening houdend met de voorwaarde die aan dat probleem is gesteld, kiezen we oplossingen die aan de gegeven voorwaarde voldoen. Dergelijke oplossingen die ons helpen resultaten te behalen die aan de gegeven voorwaarde voldoen, worden een haalbare oplossing genoemd .
- Optimale oplossing: een oplossing wordt optimaal genoemd wanneer deze al mogelijk is en de doelstelling van het probleem bereikt; het beste resultaat. Deze doelstelling kan het minimale of maximale resultaat zijn. Het punt dat hier moet worden opgemerkt, is dat elk probleem slechts één optimale oplossing heeft.
In het volgende voorbeeld begrijp je de hebzuchtige methode gemakkelijk. Stel, men wil de beste auto kopen die er op de markt is. Een van de methoden om deze auto te kiezen, is door alle auto's op de markt te analyseren. Nu, omdat dit een tijdrovende zaak is, selecteert u om gemakkelijk te zijn de auto van de specifieke merken waarin ze geïnteresseerd zijn. Als u dit verder categoriseert, zou u opnieuw de gewenste modellen kiezen met de kenmerken ervan. Daarom is de hier gebruikte aanpak hebzuchtig, omdat deze oplossing de optimale oplossing voor u was, terwijl alle factoren voor u in aanmerking kwamen.
Kerncomponenten van een hebzuchtig algoritme
Laten we nu, wanneer we dit mechanisme beter begrijpen, de kerncomponenten van een hebzuchtig algoritme onderzoeken dat het onderscheidt van andere processen:
- Kandidaatset: uit deze set wordt een antwoord gemaakt.
- Selectiefunctie: het selecteert de beste kandidaat die in de oplossing moet worden opgenomen.
- Haalbaarheidsfunctie: deze sectie berekent of een kandidaat kan worden gebruikt om bij te dragen aan de oplossing.
- Een objectieve functie: het kent een waarde toe aan een volledige of gedeeltelijke oplossing.
- Een oplossingsfunctie: deze wordt gebruikt om aan te geven of aan een juiste oplossing is voldaan.
Waar werkt het hebzuchtige algoritme het beste?
Greedy Algorithm kan worden toegepast op de onderstaande problemen.
- De Greedy-aanpak kan worden gebruikt om de minimale overspannende boomgrafiek te vinden met behulp van het algoritme van Prim of Kruskal
- Het vinden van het kortste pad tussen twee hoekpunten is nog een ander probleem dat kan worden opgelost met behulp van een hebzuchtig algoritme. Het toepassen van het algoritme van de Dijkstra samen met het hebzuchtige algoritme geeft je een optimale oplossing.
- Huffman-codering
voordelen
Het grootste voordeel dat het Greedy-algoritme ten opzichte van anderen heeft, is dat het in de meeste gevallen gemakkelijk te implementeren en zeer efficiënt is.
nadelen
Greedy Algorithm bouwt in feite een oplossing deel voor deel en kiest het volgende deel zodanig dat het onmiddellijk de beste oplossing voor het huidige probleem oplevert. Als gevolg hiervan is er geen aandacht of zorg over de gevolgen van de huidige beslissing. Nooit de eerder gemaakte keuzes heroverwegen, levert Greedy Algorithm geen optimale oplossing op, hoewel het een bijna optimale oplossing geeft . Knapzakprobleem en handelsreizigerprobleem zijn voorbeelden van problemen waarbij het hebzuchtige algoritme er niet in slaagt een optimale oplossing te produceren.
- Knapzakprobleem: Meestal bekend onder de naam rugzakprobleem, is een alledaags probleem waar veel mensen mee te maken hebben. Stel, we hebben items en elk heeft een andere weging en waarde (winst) om in een container te vullen of moet zo worden verzameld dat het totale gewicht kleiner is dan of gelijk aan dat van de container terwijl de totale winst wordt gemaximaliseerd .
Conclusie
Greedy Algorithm is het best toepasbaar wanneer men in realtime een oplossing nodig heeft en antwoorden bij benadering "goed genoeg" zijn. Het is duidelijk dat een hebzuchtig algoritme de tijd minimaliseert en ervoor zorgt dat een optimale oplossing wordt geproduceerd, daarom is het beter toepasbaar in een situatie waarin minder tijd nodig is. Na het lezen van dit artikel kan men een goed idee hebben van hebzuchtige algoritmen. Bovendien wordt in dit bericht uitgelegd waarom het wordt beschouwd als de beste frameworks die bijna alle programmeeruitdagingen beantwoorden en u helpen om op een bepaald tijdstip de meest optimale oplossing te kiezen.
Aan de ruwe kant, voor de toepassing van de theorie van hebzuchtige algoritme moet men echter harder werken om de juiste problemen te kennen. Hoewel het een wetenschappelijk concept is dat logica heeft, heeft het ook een essentie van creativiteit.
Aanbevolen artikelen
Dit is een gids geweest voor What is a Greedy Algorithm. Hier hebben we het kernconcept, de componenten, het voordeel en het nadeel van hebzuchtig algoritme besproken. U kunt ook onze andere voorgestelde artikelen doornemen voor meer informatie -
- Algoritme in programmeren
- Wat is Perl?
- Inleiding tot algoritme
- Wat is Agile Sprint?