logo

TechCodeview

giriga algoritmer

giriga algoritmer är en klass av algoritmer som gör lokalt optimalt val vid varje steg med hopp om att hitta en globalt optimum lösning. I dessa algoritmer fattas beslut baserat på den information som finns tillgänglig för närvarande utan att ta hänsyn till konsekvenserna av dessa beslut i framtiden. Nyckelidén är att välja det bästa möjliga valet vid varje steg, vilket leder till en lösning som kanske inte alltid är den mest optimala men som ofta är tillräckligt bra för många problem.

I den här artikeln kommer vi att förstå giriga algoritmer med exempel. Vi kommer också att titta på problem och deras lösningar med den giriga metoden.

giriga algoritmer



Innehållsförteckning

Vad är Greedy Algorithm?

A girig algoritm är en typ av optimeringsalgoritm som gör lokalt optimala val vid varje steg för att hitta en globalt optimal lösning. Den arbetar utifrån principen att välja det bästa alternativet nu utan att ta hänsyn till de långsiktiga konsekvenserna.

För att lära dig vad som är girig metod och hur man använder den giriga metoden, läs den givna handledningen om girig algoritm:

Steg för att skapa en girig algoritm

Stegen för att definiera en girig algoritm är:

  1. Definiera problemet: Ange tydligt vilket problem som ska lösas och målet som ska optimeras.
  2. Identifiera det giriga valet: Bestäm det lokalt optimala valet vid varje steg baserat på det aktuella tillståndet.
  3. Gör det giriga valet: Välj det giriga valet och uppdatera det aktuella tillståndet.
  4. Upprepa: Fortsätt göra giriga val tills en lösning nås.

Genom att följa de givna stegen kan man lära sig hur man använder giriga algoritmer för att hitta optimala lösningar.

Exempel på giriga algoritmer

Exempel på giriga algoritmer är det bästa sättet att förstå algoritmen. Några exempel på giriga algoritmer från verkligheten är:

  • Fractional ryggsäck : Optimerar värdet på föremål som kan inkluderas dels i en ryggsäck med begränsad kapacitet.
  • Dijkstras algoritm : Hittar den kortaste vägen från en källpunkt till alla andra hörn i en viktad graf.
  • Kruskals algoritm : Hittar det minsta spännträdet i en viktad graf.
  • Huffman kodning : Komprimerar data genom att tilldela kortare koder till vanligare symboler.

Tillämpningar av Greedy Algorithm

Det är många tillämpningar av den giriga metoden i DAA . Några viktiga giriga algoritmapplikationer är:

  • Tilldela uppgifter till resurser för att minimera väntetiden eller maximera effektiviteten.
  • Att välja ut de mest värdefulla föremålen för att passa i en ryggsäck med begränsad kapacitet.
  • Dela upp en bild i regioner med liknande egenskaper.
  • Minska storleken på data genom att ta bort redundant information.

Nackdelar/begränsningar med att använda en girig algoritm

Nedan följer några nackdelar med den giriga algoritmen:

  • giriga algoritmer kanske inte alltid hittar den bästa möjliga lösningen.
  • Ordningen i vilken delarna beaktas kan avsevärt påverka resultatet.
  • Giriga algoritmer fokuserar på lokala optimeringar och kan missa bättre lösningar som kräver att man överväger ett bredare sammanhang.
  • Giriga algoritmer är inte tillämpliga på problem där det giriga valet inte leder till en optimal lösning.

Grunderna i Greedy Algorithm:

  • giriga algoritmer (allmän struktur och tillämpningar)
  • Skillnaden mellan Greedy Algorithm och Divide and Conquer Algorithm
  • Girigt tillvägagångssätt vs dynamisk programmering
  • Jämförelse mellan Greedy, Divide and Conquer och dynamisk programmeringsalgoritm

Standard giriga algoritmer:

  • Aktivitetsvalsproblem
  • Job Sequencing Problem
  • Huffman-kodning
  • Huffman-avkodning
  • Problem med vattenanslutningen
  • Minsta swappar för konsolbalansering
  • Egyptisk fraktion
  • Poliser fångar tjuvar
  • Problem med montering av hyllor
  • Tilldela möss till hål

Giriga problem på Array:

  • Minsta produktdelmängd av en array
  • Maximera matrissumman efter K negationer med hjälp av sortering
  • Minsta summa av produkten av två matriser
  • Minsta summa av den absoluta skillnaden mellan par av två matriser
  • Minsta ökning/minskning för att göra arrayen icke-ökande
  • Sorteringsmatris med revers runt mitten
  • Summan av arean av rektanglar möjliga för en matris
  • Största lexikografiska array med högst K på varandra följande byten
  • Dela upp i två undergrupper med längderna k och (N – k) så att skillnaden mellan summor är maximal

giriga problem på operativsystem:

  • First Fit-algoritmen i minneshantering
  • Best Fit-algoritmen i minneshantering
  • Worst Fit-algoritmen i minneshantering
  • Kortaste jobb första schemaläggning
  • Jobbschemaläggning med två jobb tillåtna åt gången
  • Program för Optimal Sidersättningsalgoritm

giriga problem på grafen:

  • Kruskals minsta spannande träd
  • Prims minsta utvidgningsträd
  • Boruvkas minsta spannande träd
  • Dijkastra's Shortest Path Algorithm
  • Urtavlans algoritm
  • Minsta kostnad för att ansluta alla städer
  • Max Flow Problem Introduktion
  • Antal enkelcykelkomponenter i en oriktad graf

Ungefärlig girig algoritm för NP komplett:

  • Ställskyddsproblem
  • Papperspackningsproblem
  • Graffärgning
  • K-center problem
  • Kortaste supersträngproblem
  • Ungefärlig lösning för resande säljareproblem med MST

Girig för speciella fall av DP:

  • Problem med fraktionerad ryggsäck
  • Minsta antal mynt krävs

Enkla problem på Greedy Algoritm :

  • Dela upp n i maximala sammansatta tal
  • Köp maximala aktier om i-aktier kan köpas på i-dagen
  • Hitta det lägsta och högsta beloppet för att köpa alla N godisar
  • Maximal summa som är möjlig lika med summan av tre stackar
  • Dela kuboid i kuber så att summan av volymer är maximal
  • Maximalt antal kunder som kan vara nöjda med given kvantitet
  • Minsta rotationer för att låsa upp ett cirkulärt lås
  • Minsta rum för m evenemang om n partier med givet schema
  • Minsta kostnad för att göra arraystorlek 1 genom att ta bort större par
  • Minsta kostnad för att skaffa alla mynt med k extra mynt tillåtna med varje mynt
  • Minsta ökning med k operationer för att göra alla element lika
  • Hitta minsta antal sedlar och värden som summerar till ett givet belopp
  • Minsta delmängd med summan större än alla andra element

Medium problem på giriga Algoritm :

  • Maximalt antal tåg för vilka stopp kan tillhandahållas
  • Minsta Fibonacci-termer med summa lika med K
  • Dela 1 till n i två grupper med minsta summaskillnad
  • Papper skärs i minsta antal rutor
  • Minsta skillnad mellan grupper av storlek två
  • Anslut n rep med minimal kostnad
  • Minsta antal plattformar som krävs för en järnvägs-/busstation
  • Minsta initiala hörn för att korsa hela matrisen med givna villkor
  • Största palindromiska talet genom permuterande siffror
  • Hitta minsta nummer med givet antal siffror och siffror summa
  • Lexikografiskt största undersekvens så att varje tecken förekommer minst k gånger

Hårda problem på Greedy Algoritm :

  • Maximalt antal element som kan göras lika med k uppdateringar
  • Minimera kassaflödet bland vänner
  • Minsta kostnad för att skära en bräda i rutor
  • Minsta kostnad för att bearbeta m uppgifter där byte kostar
  • Minsta tid för att avsluta alla jobb med givna begränsningar
  • Minimera den maximala skillnaden mellan höjderna på tornen
  • Minsta kanter att vända för att göra en väg från en källa till en destination
  • Hitta den största kuben som bildas genom att ta bort minsta siffror från ett nummer
  • Ordna om tecken i en sträng så att inga två intilliggande är lika
  • Ordna om en sträng så att alla samma tecken blir d avstånd
  • Lär dig datastruktur och algoritmer | Handledning för DSA
  • De 20 bästa intervjufrågorna för giriga algoritmer
  • 'Övningsproblem' på giriga algoritmer
  • 'Frågesport' om giriga algoritmer