logo

TechCodeview

Hebzuchtige algoritmen

Hebzuchtige algoritmen zijn een klasse algoritmen die maken lokaal optimaal keuzes bij elke stap in de hoop een mondiaal optimaal oplossing. In deze algoritmen worden beslissingen genomen op basis van de informatie die op dit moment beschikbaar is, zonder rekening te houden met de gevolgen van deze beslissingen in de toekomst. Het kernidee is om bij elke stap de best mogelijke keuze te selecteren, wat leidt tot een oplossing die misschien niet altijd de meest optimale is, maar vaak goed genoeg is voor veel problemen.

In dit artikel zullen we hebzuchtige algoritmen begrijpen met voorbeelden. We zullen ook naar problemen en hun oplossingen kijken met behulp van de hebzuchtige aanpak.

Hebzuchtige algoritmen



Inhoudsopgave

Wat is hebzuchtig algoritme?

A hebzuchtig algoritme is een type optimalisatie-algoritme dat bij elke stap lokaal optimale keuzes maakt om een ​​globaal optimale oplossing te vinden. Het werkt volgens het principe om nu de beste optie te kiezen, zonder rekening te houden met de gevolgen op de lange termijn.

Om te leren wat de hebzuchtige methode is en hoe je de hebzuchtige aanpak kunt gebruiken, lees je de gegeven tutorial over het Greedy-algoritme:

Stappen voor het creëren van een hebzuchtig algoritme

De stappen om een ​​hebzuchtig algoritme te definiëren zijn:

  1. Definieer het probleem: Geef duidelijk aan welk probleem moet worden opgelost en welk doel moet worden geoptimaliseerd.
  2. Identificeer de hebzuchtige keuze: Bepaal bij elke stap de lokaal optimale keuze op basis van de huidige status.
  3. Maak de hebzuchtige keuze: Selecteer de hebzuchtige keuze en update de huidige status.
  4. Herhalen: Ga door met het maken van hebzuchtige keuzes totdat er een oplossing is bereikt.

Door de gegeven stappen te volgen, kun je leren hoe je hebzuchtige algoritmen kunt gebruiken om optimale oplossingen te vinden.

Voorbeelden van hebzuchtige algoritmen

Voorbeelden van hebzuchtige algoritmen zijn de beste manier om het algoritme te begrijpen. Enkele hebzuchtige voorbeelden uit de praktijk van algoritmen zijn:

  • Fractionele knapzak : Optimaliseert de waarde van items die fractioneel kunnen worden opgenomen in een knapzak met beperkte capaciteit.
  • Het algoritme van Dijkstra : Vindt het kortste pad van een bronhoekpunt naar alle andere hoekpunten in een gewogen grafiek.
  • Het algoritme van Kruskal : Vindt de minimaal opspannende boom van een gewogen grafiek.
  • Huffman-codering : Comprimeert gegevens door kortere codes toe te wijzen aan vaker voorkomende symbolen.

Toepassingen van het hebzuchtige algoritme

Er zijn veel toepassingen van de hebzuchtige methode in DAA . Enkele belangrijke toepassingen van hebzuchtige algoritmen zijn:

  • Taken toewijzen aan resources om de wachttijd te minimaliseren of de efficiëntie te maximaliseren.
  • Het selecteren van de meest waardevolle spullen die in een knapzak met beperkte capaciteit passen.
  • Een afbeelding verdelen in gebieden met vergelijkbare kenmerken.
  • De omvang van gegevens verkleinen door overtollige informatie te verwijderen.

Nadelen/beperkingen van het gebruik van een hebzuchtig algoritme

Hieronder staan ​​enkele nadelen van het Greedy Algorithm:

  • Hebzuchtige algoritmen vinden misschien niet altijd de best mogelijke oplossing.
  • De volgorde waarin de elementen worden overwogen, kan de uitkomst aanzienlijk beïnvloeden.
  • Hebzuchtige algoritmen richten zich op lokale optimalisaties en missen mogelijk betere oplossingen waarvoor een bredere context moet worden overwogen.
  • Greedy-algoritmen zijn niet toepasbaar op problemen waarbij de hebzuchtige keuze niet tot een optimale oplossing leidt.

Basisprincipes van het hebzuchtige algoritme:

  • Hebzuchtige algoritmen (algemene structuur en toepassingen)
  • Verschil tussen hebzuchtig algoritme en verdeel en heers algoritme
  • Hebzuchtige aanpak versus dynamisch programmeren
  • Vergelijking tussen Greedy, Divide and Conquer en Dynamic Programming-algoritmen

Standaard hebzuchtige algoritmen:

  • Probleem met activiteitselectie
  • Probleem met taakvolgorde
  • Huffman-codering
  • Huffman-decodering
  • Probleem met wateraansluiting
  • Minimale swaps voor beugelbalancering
  • Egyptische fractie
  • Politieagenten vangen dieven
  • Probleem met het plaatsen van planken
  • Wijs muizen toe aan gaten

Hebzuchtige problemen met array:

  • Minimale productsubset van een array
  • Maximaliseer de arraysom na K-ontkenningen met behulp van sorteren
  • Minimale som van het product van twee arrays
  • Minimale som van het absolute verschil tussen paren van twee arrays
  • Minimale verhoging/verlaging om de array niet-toenemend te maken
  • Sorteerarray met omgekeerde rond het midden
  • Som van gebieden van rechthoeken mogelijk voor een array
  • Grootste lexicografische array met maximaal K opeenvolgende swaps
  • Verdeel het in twee subarrays met de lengten k en (N – k), zodat het verschil tussen de sommen maximaal is

Hebzuchtige problemen met het besturingssysteem:

  • First Fit-algoritme in geheugenbeheer
  • Best Fit-algoritme in geheugenbeheer
  • Slechtste Fit-algoritme in geheugenbeheer
  • Kortste taak eerste planning
  • Taakplanning waarbij twee taken tegelijk zijn toegestaan
  • Programma voor optimaal paginavervangingsalgoritme

Hebzuchtige problemen in de grafiek:

  • Kruskal's minimale spanningsboom
  • Prim's minimale spanningsboom
  • Boruvka's minimale spanningsboom
  • Het kortste pad-algoritme van Dijkastra
  • Het algoritme van Dial
  • Minimale kosten om alle steden met elkaar te verbinden
  • Introductie van probleem met maximale stroom
  • Aantal componenten van één cyclus in een ongerichte grafiek

Geschatte hebzuchtige algoritme voor NP Complete:

  • Probleem met dekking instellen
  • Probleem met het inpakken van bakken
  • Grafiek kleuren
  • K-centra probleem
  • Kortste supersnaarprobleem
  • Geschatte oplossing voor het handelsreizigersprobleem bij gebruik van MST

Hebzuchtig voor speciale gevallen van DP:

  • Fractioneel knapzakprobleem
  • Minimaal aantal vereiste munten

Gemakkelijke problemen op Greedy Algoritme :

  • Splits n in maximale samengestelde getallen
  • Koop maximale aandelen als er op de i-de dag aandelen kunnen worden gekocht
  • Vind het minimum- en maximumbedrag om alle N-snoepjes te kopen
  • Maximaal mogelijke som gelijk aan de som van drie stapels
  • Verdeel de kubus in kubussen, zodat de som van de volumes maximaal is
  • Maximaal aantal klanten dat tevreden kan zijn met een bepaalde hoeveelheid
  • Minimale rotaties om een ​​rond slot te ontgrendelen
  • Minimale ruimten voor m evenementen van n batches met een bepaald schema
  • Minimale kosten om arraygrootte 1 te maken door grotere paren te verwijderen
  • Minimale kosten voor het verwerven van alle munten, waarbij bij elke munt k extra munten zijn toegestaan
  • Minimale verhoging met k bewerkingen om alle elementen gelijk te maken
  • Zoek het minimumaantal bankbiljetten en waarden die optellen tot een bepaald bedrag
  • Kleinste deelverzameling waarvan de som groter is dan alle andere elementen

Middelgrote problemen bij hebzuchtig Algoritme :

  • Maximaal aantal treinen waarvoor stopzetting kan worden voorzien
  • Minimale Fibonacci-termen met een som gelijk aan K
  • Verdeel 1 tot n in twee groepen met een minimaal somverschil
  • Papier gesneden in een minimaal aantal vierkanten
  • Minimaal verschil tussen groepen van maat twee
  • Verbind n touwen met minimale kosten
  • Minimumaantal perrons vereist voor een trein-/busstation
  • Minimale initiële hoekpunten om de hele matrix te doorkruisen met gegeven voorwaarden
  • Grootste palindroomgetal door cijfers te verwisselen
  • Vind het kleinste getal met een bepaald aantal cijfers en de som van de cijfers
  • Lexicografisch grootste deelreeks, zodat elk teken minstens k keer voorkomt

Moeilijke problemen bij Greedy Algoritme :

  • Maximaal aantal elementen dat gelijk kan worden gemaakt met k updates
  • Minimaliseer de cashflow onder vrienden
  • Minimale kosten om een ​​bord in vierkanten te snijden
  • Minimale kosten voor het verwerken van m taken met overstapkosten
  • Minimale tijd om alle taken met bepaalde beperkingen te voltooien
  • Minimaliseer het maximale verschil tussen de hoogtes van torens
  • Minimale randen die moeten worden omgedraaid om een ​​pad te maken van een bron naar een bestemming
  • Vind de grootste kubus gevormd door het verwijderen van minimale cijfers uit een getal
  • Herschik de tekens in een tekenreeks zodanig dat geen twee aangrenzende tekens hetzelfde zijn
  • Herschik een string zodat alle dezelfde karakters op een afstand van elkaar verwijderd worden
  • Leer datastructuur en algoritmen | DSA-zelfstudie
  • Top 20 interviewvragen over hebzuchtige algoritmen
  • ‘Oefenproblemen’ met hebzuchtige algoritmen
  • ‘Quiz’ over hebzuchtige algoritmen