logo

TechCodeview

Grådige algoritmer

Grådige algoritmer er en klasse af algoritmer, der laver lokalt optimalt valg på hvert trin med håbet om at finde en globalt optimum løsning. I disse algoritmer træffes beslutninger baseret på den information, der er tilgængelig på nuværende tidspunkt, uden at overveje konsekvenserne af disse beslutninger i fremtiden. Nøgleideen er at vælge det bedst mulige valg på hvert trin, hvilket fører til en løsning, der måske ikke altid er den mest optimale, men som ofte er god nok til mange problemer.

I denne artikel vil vi forstå grådige algoritmer med eksempler. Vi vil også se på problemer og deres løsninger ved at bruge den grådige tilgang.

Grådige algoritmer



Indholdsfortegnelse

datastrukturer java

Hvad er Greedy Algorithm?

EN grådig algoritme er en type optimeringsalgoritme, der træffer lokalt optimale valg ved hvert trin for at finde en globalt optimal løsning. Det fungerer ud fra princippet om at vælge den bedste løsning nu uden at overveje de langsigtede konsekvenser.

For at lære, hvad der er grådig metode, og hvordan man bruger den grådige tilgang, læs den givne vejledning om den grådige algoritme:

Trin til at skabe en grådig algoritme

Trinene til at definere en grådig algoritme er:

c++ gui
  1. Definer problemet: Angiv klart det problem, der skal løses, og målet, der skal optimeres.
  2. Identificer det grådige valg: Bestem det lokalt optimale valg ved hvert trin baseret på den aktuelle tilstand.
  3. Træf det grådige valg: Vælg det grådige valg, og opdater den aktuelle tilstand.
  4. Gentage: Fortsæt med at træffe grådige valg, indtil en løsning er nået.

Ved at følge de givne trin kan man lære at bruge grådige algoritmer til at finde optimale løsninger.

Eksempler på grådige algoritmer

Eksempler på grådige algoritmer er den bedste måde at forstå algoritmen på. Nogle eksempler på grådige algoritmer fra det virkelige liv er:

cobol programmering
  • Fractional Rugsæk : Optimerer værdien af ​​genstande, der kan indgå i en rygsæk med begrænset kapacitet.
  • Dijkstras algoritme : Finder den korteste vej fra et kildepunkt til alle andre hjørner i en vægtet graf.
  • Kruskals algoritme : Finder minimumspændingstræet i en vægtet graf.
  • Huffman kodning : Komprimerer data ved at tildele kortere koder til hyppigere symboler.

Anvendelser af Greedy Algorithm

Der er mange anvendelser af den grådige metode i DAA . Nogle vigtige grådige algoritmeapplikationer er:

  • Tildeling af opgaver til ressourcer for at minimere ventetiden eller maksimere effektiviteten.
  • Udvælgelse af de mest værdifulde genstande til at passe ind i en rygsæk med begrænset kapacitet.
  • Opdeling af et billede i områder med lignende egenskaber.
  • Reduktion af datastørrelsen ved at fjerne overflødige oplysninger.

Ulemper/begrænsninger ved at bruge en grådig algoritme

Nedenfor er nogle ulemper ved Greedy Algorithm:

  • Grådige algoritmer finder måske ikke altid den bedst mulige løsning.
  • Den rækkefølge, som elementerne betragtes i, kan have en væsentlig indflydelse på resultatet.
  • Grådige algoritmer fokuserer på lokale optimeringer og går måske glip af bedre løsninger, der kræver overvejelse af en bredere kontekst.
  • Grådige algoritmer er ikke anvendelige på problemer, hvor det grådige valg ikke fører til en optimal løsning.

Grundlæggende om Greedy Algorithm:

  • Grådige algoritmer (generel struktur og applikationer)
  • Forskellen mellem Greedy Algorithm og Divide and Conquer Algorithm
  • Grådig tilgang vs dynamisk programmering
  • Sammenligning mellem Greedy, Divide and Conquer og Dynamic Programming algoritme

Standard grådige algoritmer:

  • Aktivitetsvalgsproblem
  • Jobsekvensproblem
  • Huffman kodning
  • Huffman afkodning
  • Vandtilslutningsproblem
  • Minimumsswaps for beslagsbalancering
  • Egyptisk fraktion
  • Politifolk fanger tyve
  • Problem med montering af hylder
  • Tildel mus til huller

Grådige problemer på Array:

  • Minimumsproduktundersæt af et array
  • Maksimer matrixsummen efter K negationer ved hjælp af sortering
  • Minimumsummen af ​​produktet af to arrays
  • Minimumsummen af ​​den absolutte forskel mellem par af to arrays
  • Minimum stigning/reduktion for at gøre array ikke-stigende
  • Sorteringsarray med revers omkring midten
  • Summen af ​​arealer af rektangler muligt for en matrix
  • Største leksikografiske array med højst K på hinanden følgende swaps
  • Opdel i to subarrays med længderne k og (N – k), således at forskellen mellem summer er maksimal

Grådige problemer på operativsystemet:

  • First Fit-algoritme i Memory Management
  • Bedste tilpasningsalgoritme i hukommelsesstyring
  • Worst Fit-algoritme i Memory Management
  • Korteste job først planlægning
  • Jobplanlægning med to job tilladt ad gangen
  • Program for optimal sideerstatningsalgoritme

Grådige problemer på graf:

  • Kruskal's Minimum Spanning Tree
  • Prim's Minimum Spanning Tree
  • Boruvkas minimumsspændende træ
  • Dijkastra's Shortest Path Algorithm
  • Urets algoritme
  • Minimumsomkostninger for at forbinde alle byer
  • Max Flow Problem Introduktion
  • Antal enkeltcykluskomponenter i en urettet graf

Omtrentlig grådig algoritme for NP fuldført:

  • Sæt dækslet problem
  • Problem med beholderpakning
  • Graffarvning
  • K-centre problem
  • Korteste superstreng problem
  • Omtrentlig løsning for rejsende sælgerproblem ved brug af MST

Grådig efter særlige tilfælde af DP:

  • Fractional Napsack Problem
  • Minimum antal mønter påkrævet

Lette problemer på Greedy Algoritme :

  • Opdel n i maksimale sammensatte tal
  • Køb maksimale aktier, hvis i-aktier kan købes på den i-te dag
  • Find minimums- og maksimumsbeløbet for at købe alle N slik
  • Maksimal sum muligt svarende til summen af ​​tre stakke
  • Opdel cuboid i terninger, så summen af ​​volumener er maksimal
  • Maksimalt antal kunder, der kan være tilfredse med en given mængde
  • Minimum rotationer for at låse en cirkulær lås op
  • Minimumslokaler til m arrangementer af n partier med given tidsplan
  • Minimumsomkostninger for at lave arraystørrelse 1 ved at fjerne større par
  • Minimumsomkostninger for at erhverve alle mønter med k ekstra mønter tilladt med hver mønt
  • Minimum stigning med k operationer for at gøre alle elementer ens
  • Find minimumsantallet af valutasedler og værdier, der summer til et givet beløb
  • Mindste delmængde med sum større end alle andre elementer

Medium problemer på Greedy Algoritme :

  • Maksimalt antal tog, for hvilke der kan stilles standsning
  • Minimum Fibonacci-vilkår med sum lig med K
  • Opdel 1 til n i to grupper med minimum sum forskel
  • Papir skåret i minimum antal firkanter
  • Minimumsforskel mellem grupper af størrelse to
  • Forbind n reb med minimale omkostninger
  • Minimum antal perroner, der kræves til en jernbane-/busstation
  • Minimum indledende hjørner for at krydse hele matrixen med givne betingelser
  • Største palindromiske tal ved permuterende cifre
  • Find mindste tal med givet antal cifre og cifre sum
  • Leksikografisk største undersekvens, således at hvert tegn forekommer mindst k gange

Hårde problemer på Greedy Algoritme :

  • Maksimalt antal elementer, der kan gøres lig med k opdateringer
  • Minimer pengestrømme blandt venner
  • Minimumsomkostninger for at skære et bræt i firkanter
  • Minimumsomkostninger til at behandle m opgaver, hvor skifteomkostninger
  • Minimum tid til at afslutte alle opgaver med givne begrænsninger
  • Minimer den maksimale forskel mellem tårnenes højder
  • Minimumskanter at vende for at lave en sti fra en kilde til en destination
  • Find den største terning dannet ved at slette minimumcifre fra et tal
  • Omarranger tegn i en streng, så ikke to tilstødende er ens
  • Omarranger en streng, så alle de samme tegn bliver d i afstand
  • Lær datastruktur og algoritmer | DSA Tutorial
  • Top 20 grådige algoritmer interviewspørgsmål
  • 'Practice Problemer' om grådige algoritmer
  • 'Quiz' om grådige algoritmer