Introduktion till girig algoritm
En strategi som används för att lösa problem. Grådig algoritm betraktas som en av de metoder som används för att lösa problem. Denna problemlösande kättare går med att göra ett val som verkar bäst i det ögonblicket. Den här metoden används bäst för att lösa optimeringsproblem. Optimeringsproblem kan definieras som problem som kräver antingen minimum eller maximalt resultat. En girig algoritm är en enklaste och mest enkla strategi som kan användas för att uppnå en optimal lösning.
Vad är girig algoritm?
Greedy Algoritm är en algoritmisk strategi som används för att göra det bästa valbara valet i ett mycket litet skede samtidigt som man till slut levererar en globalt optimal lösning. Denna algoritm väljer den bästa lösningen som är möjlig i det ögonblicket utan hänsyn till några konsekvenser. Den giriga metoden säger att problemet bör lösas i steg där varje inmatning anses med tanke på att denna inmatning är genomförbar. Eftersom denna strategi endast fokuserar på ett omedelbart resultat utan hänsyn till den större bilden, anses girig.
Definiera kärnkonceptet
Hittills vet vi vad en girig algoritm är och varför heter den så. Nedanstående pekare får dig att förstå den giriga algoritmen på ett bättre sätt. Nu har det varit mycket tydligt att den giriga algoritmen bara fungerar när det finns ett problem; ändå är denna metod endast tillämplig om vi har ett villkor eller begränsning för det problemet.
Typer av problem
- Minimeringsproblem: Att få en lösning på ett problem är lätt med tanke på att alla villkor är uppfyllda. Men när detta problem kräver ett minimiresultat kallas det då ett minimeringsproblem.
- Maximeringsproblem: Ett problem som kräver maximalt resultat kallas maximeringsproblemet.
- Optimeringsproblem: Ett problem kallas optimeringsproblem när det kräver antingen lägsta eller högsta resultat.
Typer av lösningar
- Genomförbar lösning: nu när ett problem uppstår har vi många rimliga lösningar på detta problem. Men med hänsyn till villkoret som ställs på det problemet väljer vi lösningar som uppfyller det givna villkoret. Sådana lösningar som hjälper oss att få resultat som uppfyller det givna villkoret kallas en genomförbar lösning .
- Optimal lösning: En lösning kallas optimal när den redan är genomförbar och når målet med problemet. det bästa resultatet. Detta mål kan antingen vara det minsta eller det maximala resultatet. Poängen här att märka är att alla problem bara har en optimal lösning.
Följande exempel gör att du lätt förstår den giriga metoden. Säg, man vill köpa den bästa bilen som finns på marknaden. En av metoderna för att välja denna bil är genom att analysera alla bilar på marknaden. Nu är det en tidskrävande, för att göra det enkelt man väljer bil från de specifika varumärken som de är intresserade av att investera i. Om man kategoriserar detta ytterligare skulle man åter välja de önskade modellerna och titta på dess funktioner. Därför är den metod som används här girig eftersom denna lösning var den optimala lösningen för dig med tanke på att alla faktorer var gynnsamma för dig.
Kärnkomponenter i en girig algoritm
Nu när vi har en bättre förståelse av denna mekanism, låt oss utforska kärnkomponenterna i en girig algoritm som skiljer den från andra processer:
- Kandidatuppsättning: Ett svar skapas från denna uppsättning.
- Urvalsfunktion: Den väljer den bästa kandidaten som ska inkluderas i lösningen.
- Feasibility-funktion: Det här avsnittet beräknar om en kandidat kan användas för att bidra till lösningen.
- En objektiv funktion: Den tilldelar ett värde till en komplett eller partiell lösning.
- En lösningsfunktion: Denna används för att indikera om en korrekt lösning har uppfyllts.
Var fungerar den giriga algoritmen bäst?
Grådig algoritm kan tillämpas på nedanstående problem.
- Den giriga metoden kan användas för att hitta den minimala spännande trädgrafen med Prims eller Kruskals algoritm
- Att hitta den kortaste vägen mellan två toppar är ännu ett problem som kan lösas med en girig algoritm. Att använda Dijkstra's algoritm tillsammans med den giriga algoritmen ger dig en optimal lösning.
- Huffman-kodning
fördelar
Den största fördelen som Greedy-algoritmen har jämfört med andra är att den är lätt att implementera och mycket effektiv i de flesta fall.
nackdelar
Grådig algoritm bygger i grund och botten en lösning delvis och väljer nästa del på ett sådant sätt att den ger den bästa lösningen på det aktuella problemet omedelbart. Som ett resultat finns det ingen hänsyn till eller oro för konsekvenserna av det nuvarande beslutet. Greedy Algoritm har aldrig tagit igenom de val som tagits tidigare och misslyckas med att producera en optimal lösning, även om den ger en nästan optimal lösning . Ryggsäckproblem och resande säljare Problem är exempel på problem där den giriga algoritmen inte lyckas producera en optimal lösning.
- Ryggsäckproblem: Vanligtvis känt under namnet ryggsäckproblem, är ett vardagsproblem som många människor möter. Säg att vi har uppsättning artiklar och var och en har olika vikt och värde (vinst) som ska fyllas i en behållare eller borde samlas in på ett sådant sätt att den totala vikten är mindre än eller lika med behållarens medan den totala vinsten maximeras .
Slutsats
Grådig algoritm är bäst tillämpbar när man behöver en lösning i realtid och ungefärliga svar är ”tillräckligt bra”. Det är uppenbart att en girig algoritm minimerar tiden medan den ser till att en optimal lösning produceras, varför det är mer tillämpligt att använda i en situation där mindre tid krävs. Efter att ha läst den här artikeln kan man ha en rättvisande uppfattning om giriga algoritmer. Dessutom förklarar detta inlägg varför det betraktas som de bästa ramarna som svarar på nästan alla programmeringsutmaningar tillsammans med att hjälpa dig att bestämma den mest optimala lösningen vid en viss tidpunkt.
På grov sida måste man dock arbeta hårdare för att veta de rätta frågorna för att tillämpa teorin om giriga algoritmer. Även om det är ett vetenskapligt begrepp som har logik, har det också en kärlek av kreativitet.
Rekommenderade artiklar
Detta har varit en guide till Vad är en girig algoritm. Här diskuterade vi Core Concept, komponenter, fördelar och nackdelar med girig algoritm. Du kan också gå igenom våra andra föreslagna artiklar för att lära dig mer -
- Algoritm i programmering
- Vad är Perl?
- Introduktion till algoritm
- Vad är Agile Sprint?