logo

TechCodeview

Grådige algoritmer

Grådige algoritmer er en klasse av algoritmer som lager lokalt optimalt valg på hvert trinn med håp om å finne en globalt optimum løsning. I disse algoritmene tas beslutninger basert på informasjonen som er tilgjengelig i øyeblikket uten å vurdere konsekvensene av disse beslutningene i fremtiden. Nøkkelideen er å velge det best mulige valget ved hvert trinn, noe som fører til en løsning som kanskje ikke alltid er den mest optimale, men som ofte er god nok for mange problemer.

I denne artikkelen vil vi forstå grådige algoritmer med eksempler. Vi vil også se på problemer og deres løsninger ved å bruke den grådige tilnærmingen.

Grådige algoritmer



Innholdsfortegnelse

datastrukturer java

Hva er Greedy Algorithm?

EN grådig algoritme er en type optimaliseringsalgoritme som gjør lokalt optimale valg ved hvert trinn for å finne en globalt optimal løsning. Den opererer etter prinsippet om å ta det beste alternativet nå uten å vurdere de langsiktige konsekvensene.

For å lære hva som er grådig metode og hvordan du bruker den grådige tilnærmingen, les den gitte opplæringen om den grådige algoritmen:

Trinn for å lage en grådig algoritme

Trinnene for å definere en grådig algoritme er:

hva er en spesiell karakter
  1. Definer problemet: Angi tydelig problemet som skal løses og målet som skal optimaliseres.
  2. Identifiser det grådige valget: Bestem det lokalt optimale valget ved hvert trinn basert på gjeldende tilstand.
  3. Ta det grådige valget: Velg det grådige valget og oppdater gjeldende tilstand.
  4. Gjenta: Fortsett å ta grådige valg til en løsning er nådd.

Ved å følge de gitte trinnene kan man lære å bruke grådige algoritmer for å finne optimale løsninger.

Eksempler på grådige algoritmer

Eksempler på grådige algoritmer er den beste måten å forstå algoritmen på. Noen eksempler på grådige algoritmer fra det virkelige liv er:

cobol programmering
  • Fraksjonert ryggsekk : Optimaliserer verdien av gjenstander som kan inkluderes brøkdel i en ryggsekk med begrenset kapasitet.
  • Dijkstras algoritme : Finner den korteste veien fra et kildepunkt til alle andre toppunkter i en vektet graf.
  • Kruskals algoritme : Finner minimumsspenningstreet i en vektet graf.
  • Huffman-koding : Komprimerer data ved å tilordne kortere koder til hyppigere symboler.

Anvendelser av Greedy Algorithm

Det er mange anvendelser av den grådige metoden i DAA . Noen viktige grådige algoritmeapplikasjoner er:

  • Tilordne oppgaver til ressurser for å minimere ventetiden eller maksimere effektiviteten.
  • Velge de mest verdifulle gjenstandene for å passe inn i en ryggsekk med begrenset kapasitet.
  • Dele et bilde i områder med lignende egenskaper.
  • Redusere størrelsen på data ved å fjerne overflødig informasjon.

Ulemper/begrensninger ved å bruke en grådig algoritme

Nedenfor er noen ulemper med Greedy Algorithm:

  • Grådige algoritmer finner kanskje ikke alltid den best mulige løsningen.
  • Rekkefølgen som elementene vurderes i kan påvirke resultatet betydelig.
  • Grådige algoritmer fokuserer på lokale optimaliseringer og kan gå glipp av bedre løsninger som krever å vurdere en bredere kontekst.
  • Grådige algoritmer er ikke anvendelige på problemer der det grådige valget ikke fører til en optimal løsning.

Grunnleggende om Greedy Algorithm:

  • Grådige algoritmer (generell struktur og applikasjoner)
  • Forskjellen mellom Greedy Algorithm og Divide and Conquer Algorithm
  • Grådig tilnærming vs dynamisk programmering
  • Sammenligning mellom Greedy, Divide and Conquer og dynamisk programmeringsalgoritme

Standard grådige algoritmer:

  • Aktivitetsvalgproblem
  • Problem med jobbsekvensering
  • Huffman-koding
  • Huffman-dekoding
  • Vanntilkoblingsproblem
  • Minimumsbytte for brakettbalansering
  • Egyptisk brøk
  • Politimenn fanger tyver
  • Problem med montering av hyller
  • Tilordne mus til hull

Grådige problemer på Array:

  • Minimum produkt undersett av en matrise
  • Maksimer matrisesummen etter K negasjoner ved å bruke sortering
  • Minimum sum av produktet av to matriser
  • Minimum sum av absolutt differanse av par av to matriser
  • Minimum økning/reduksjon for å gjøre matrisen ikke-økende
  • Sorteringsarray med revers rundt midten
  • Summen av arealer av rektangler mulig for en matrise
  • Største leksikografiske array med maksimalt K påfølgende bytter
  • Del opp i to undergrupper med lengdene k og (N – k) slik at forskjellen mellom summer er maksimal

Grådige problemer på operativsystemet:

  • First Fit-algoritmen i minneadministrasjon
  • Best Fit-algoritme i minneadministrasjon
  • Worst Fit-algoritmen i minneadministrasjon
  • Korteste jobb først planlegging
  • Jobbplanlegging med to jobber tillatt om gangen
  • Program for optimal sideerstatningsalgoritme

Grådige problemer på grafen:

  • Kruskals minimumsspennende tre
  • Prims minimumsspennende tre
  • Boruvkas minimumsspennende tre
  • Dijkastras korteste vei-algoritme
  • Dial sin algoritme
  • Minimumskostnad for å koble sammen alle byer
  • Max Flow Problem Introduksjon
  • Antall enkeltsykluskomponenter i en urettet graf

Omtrentlig grådig algoritme for NP fullført:

  • Sett dekselproblem
  • Problem med søppelpakking
  • Graffarging
  • K-sentre problem
  • Korteste superstrengproblem
  • Omtrentlig løsning for reisende selgerproblem ved bruk av MST

Grådig etter spesielle tilfeller av DP:

  • Problem med brøksekk
  • Minimum antall mynter kreves

Enkle problemer på Greedy Algoritme :

  • Del n i maksimale sammensatte tall
  • Kjøp maksimale aksjer hvis i-aksjer kan kjøpes på i-te dag
  • Finn minimums- og maksimumsbeløpet for å kjøpe alle N-godterier
  • Maksimal sum mulig lik summen av tre stabler
  • Del kuboid i terninger slik at summen av volumer er maksimal
  • Maksimalt antall kunder som kan være fornøyd med gitt kvantum
  • Minimum rotasjoner for å låse opp en sirkulær lås
  • Minimumsrom for m arrangementer på n partier med gitt tidsplan
  • Minimumskostnad for å lage matrisestørrelse 1 ved å fjerne større par
  • Minimumskostnad for å skaffe alle mynter med k ekstra mynter tillatt med hver mynt
  • Minimum økning med k operasjoner for å gjøre alle elementene like
  • Finn minimum antall valutasedler og verdier som summerer til gitt beløp
  • Minste delmengde med sum større enn alle andre elementer

Middels problemer på Greedy Algoritme :

  • Maksimalt antall tog som kan gis stans
  • Minimum Fibonacci-termer med sum lik K
  • Del 1 til n i to grupper med minimum sumdifferanse
  • Papir kuttet i minimum antall firkanter
  • Minimumsforskjell mellom grupper i størrelse to
  • Koble n tau med minimumskostnad
  • Minimum antall plattformer som kreves for en jernbane-/busstasjon
  • Minimum startpunkt for å krysse hele matrisen med gitte betingelser
  • Største palindromiske tall ved permuterende sifre
  • Finn minste tall med gitt antall sifre og tallsum
  • Leksikografisk største undersekvens slik at hvert tegn forekommer minst k ganger

Harde problemer på Greedy Algoritme :

  • Maksimalt antall elementer som kan gjøres like med k oppdateringer
  • Minimer kontantstrømmen blant venner
  • Minimumskostnad for å kutte et brett i firkanter
  • Minimumskostnad for å behandle m oppgaver hvor byttekostnader
  • Minimum tid for å fullføre alle jobber med gitte begrensninger
  • Minimer maksimal forskjell mellom høydene på tårnene
  • Minimumskanter å reversere for å lage bane fra en kilde til en destinasjon
  • Finn den største kuben dannet ved å slette minimumssiffer fra et tall
  • Omorganiser tegn i en streng slik at ikke to tilstøtende er like
  • Omorganiser en streng slik at alle de samme tegnene blir d avstand unna
  • Lær datastruktur og algoritmer | DSA veiledning
  • Topp 20 grådige algoritmer intervjuspørsmål
  • 'Øvningsproblemer' på grådige algoritmer
  • 'Quiz' om grådige algoritmer