De hebzuchtige methode is een van de strategieën zoals Verdeel en heers die wordt gebruikt om de problemen op te lossen. Deze methode wordt gebruikt voor het oplossen van optimalisatieproblemen. Een optimalisatieprobleem is een probleem dat maximale of minimale resultaten vereist. Laten we het door middel van enkele termen begrijpen.
De Greedy-methode is de eenvoudigste en duidelijkste aanpak. Het is geen algoritme, maar het is een techniek. De belangrijkste functie van deze aanpak is dat de beslissing wordt genomen op basis van de momenteel beschikbare informatie. Wat de huidige informatie ook is, de beslissing wordt genomen zonder dat u zich zorgen hoeft te maken over het effect van de huidige beslissing in de toekomst.
Actrice Rakul Preet Singh
Deze techniek wordt in principe gebruikt om de haalbare oplossing te bepalen die al dan niet optimaal is. De haalbare oplossing is een subset die aan de gegeven criteria voldoet. De optimale oplossing is de oplossing die de beste en meest gunstige oplossing is in de deelverzameling. Als in het geval van haalbaarheid meer dan één oplossing aan de gegeven criteria voldoet, worden die oplossingen als haalbaar beschouwd, terwijl de optimale oplossing de beste oplossing is van alle oplossingen.
Kenmerken van de Greedy-methode
Hier volgen de kenmerken van een hebzuchtige methode:
- Om de oplossing op een optimale manier te construeren, creëert dit algoritme twee sets waarbij één set alle gekozen items bevat en een andere set de afgewezen items bevat.
- Een Greedy-algoritme maakt goede lokale keuzes in de hoop dat de oplossing haalbaar of optimaal is.
Onderdelen van het hebzuchtige algoritme
De componenten die kunnen worden gebruikt in het hebzuchtige algoritme zijn:
gimp van kleur veranderen
Toepassingen van het hebzuchtige algoritme
- Het wordt gebruikt bij het vinden van het kortste pad.
- Het wordt gebruikt om de minimaal opspannende boom te vinden met behulp van het prim-algoritme of het Kruskal-algoritme.
- Het wordt gebruikt bij taakvolgorde met een deadline.
- Dit algoritme wordt ook gebruikt om het fractionele knapzakprobleem op te lossen.
Pseudocode van hebzuchtig algoritme
Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } Het bovenstaande is het hebzuchtige algoritme. In eerste instantie wordt aan de oplossing een nulwaarde toegekend. We geven de array en het aantal elementen door in het hebzuchtige algoritme. Binnen de for-lus selecteren we het element één voor één en controleren of de oplossing haalbaar is of niet. Als de oplossing haalbaar is, voeren we de unie uit.
Laten we het begrijpen aan de hand van een voorbeeld.
Stel dat er een probleem 'P' is. Ik wil van A naar B reizen, zoals hieronder weergegeven:
P: EEN → B
Het probleem is dat we deze reis van A naar B moeten afleggen. Er zijn verschillende oplossingen om van A naar B te gaan. We kunnen van A naar B gaan door lopen, auto, fiets, trein, vliegtuig , enz. Er is een beperking in de reis dat we deze reis binnen 12 uur moeten afleggen. Als ik alleen met de trein of het vliegtuig ga, kan ik deze afstand binnen 12 uur overbruggen. Er zijn veel oplossingen voor dit probleem, maar er zijn slechts twee oplossingen die aan de beperking voldoen.
Als we zeggen dat we de reis tegen de minimale kosten moeten afleggen. Dit betekent dat we deze afstand zo minimaal mogelijk moeten afleggen. Dit probleem staat daarom bekend als een minimalisatieprobleem. Tot nu toe hebben we twee haalbare oplossingen, namelijk één per trein en één per vliegtuig. Omdat reizen met de trein tot minimale kosten leidt, is het een optimale oplossing. Een optimale oplossing is ook de haalbare oplossing, maar met het beste resultaat, zodat de oplossing de optimale oplossing is tegen de minimale kosten. Er zou maar één optimale oplossing zijn.
Het probleem dat een minimaal of maximaal resultaat vereist, staat bekend als een optimalisatieprobleem. De hebzuchtige methode is een van de strategieën die worden gebruikt om de optimalisatieproblemen op te lossen.
object van array in Java
Nadelen van het gebruik van het Greedy-algoritme
Het hebzuchtige algoritme neemt beslissingen op basis van de informatie die in elke fase beschikbaar is, zonder rekening te houden met het bredere probleem. Er kan dus een mogelijkheid zijn dat de hebzuchtige oplossing niet voor elk probleem de beste oplossing biedt.
Het volgt de lokale optimale keuze in elke fase met de bedoeling het mondiale optimale te vinden. Laten we het begrijpen aan de hand van een voorbeeld.
Beschouw de grafiek die hieronder wordt gegeven:
We moeten tegen minimale kosten van de bron naar de bestemming reizen. Omdat we drie haalbare oplossingen hebben met kostenpaden als 10, 20 en 5. 5 is het minimale kostenpad en is dus de optimale oplossing. Dit is het lokale optimale, en op deze manier vinden we in elke fase het lokale optimale om de globale optimale oplossing te berekenen.
wat zit er in python