Introduksjon til grådig algoritme
En strategi som brukes for å løse problemer. Grådig algoritme anses som en av tilnærmingene som brukes for å løse problemer. Denne problemløsende kjetteren følger med å ta et valg som virker best i det øyeblikket. Denne tilnærmingen brukes best for å løse optimaliseringsproblemer. Optimaliseringsproblemer kan defineres som problemer som krever minimum eller maksimalt resultat. En grådig algoritme er en enkleste og mest grei tilnærming som kan brukes for å oppnå en optimal løsning.
Hva er grådig algoritme?
Greedy Algorithm er en algoritmisk strategi som brukes for å gjøre det beste valgfrie valget på et veldig lite stadium mens du til slutt gir ut en globalt optimal løsning. Denne algoritmen velger den beste løsningen som er mulig i det øyeblikket uten hensyn til noen konsekvenser. Grådig metode sier at problemet bør løses i trinn hvor hver enkelt inngang blir vurdert gitt at denne inngangen er gjennomførbar. Siden denne tilnærmingen kun fokuserer på et øyeblikkelig resultat uten hensyn til det større bildet, regnes det som grådig.
Definere kjernekonseptet
Til nå vet vi hva en grådig algoritme er, og hvorfor heter den det. Tipsene nedenfor vil få deg til å forstå den grådige algoritmen på en bedre måte. Nå har det vært veldig tydelig at den grådige algoritmen bare fungerer når det er et problem; Likevel er denne tilnærmingen bare anvendelig hvis vi har en betingelse eller begrensning for det problemet.
Typer av problemer
- Minimeringsproblem: Det er enkelt å få en løsning på et problem gitt at alle betingelsene er oppfylt. Når dette problemet krever et minimumsresultat, kalles det imidlertid et minimeringsproblem.
- Maksimeringsproblem: Et problem som krever maksimalt resultat kalles maksimeringsproblemet.
- Optimaliseringsproblem: Et problem kalles optimaliseringsproblem når det krever minimum eller maksimalt resultat.
Typer av løsninger
- Gjennomførbar løsning: Nå når et problem oppstår, har vi mange sannsynlige løsninger på dette problemet. Likevel tar vi i betraktning betingelsen som er satt på det problemet, vi velger løsninger som tilfredsstiller den gitte tilstanden. Slike løsninger som hjelper oss med å få resultater som oppfyller den gitte betingelsen, kalles en gjennomførbar løsning .
- Optimal løsning: En løsning kalles optimal når den allerede er gjennomførbar og når målet med problemet; det beste resultatet. Dette målet kan enten være et minimum eller maksimalt resultat. Poenget her å bli lagt merke til er at ethvert problem bare vil ha en optimal løsning.
Følgende eksempel vil få deg til å forstå den grådige metoden lett. Si, man vil kjøpe den beste bilen som er tilgjengelig i markedet. En av metodene for å velge denne bilen er ved å analysere alle bilene i markedet. Nå, dette er en tidkrevende, for å gjøre det enkelt en velger bil fra de spesifikke merkene som de er interessert i å investere i. Ved å kategorisere dette videre, vil man igjen velge de ønskede modellene og se på funksjonene. Derfor er tilnærmingen som brukes her grådig da denne løsningen var den optimale løsningen for deg mens du vurderte alle faktorene som var gunstige for deg.
Kjernekomponenter i en grådig algoritme
Når vi nå har en bedre forståelse av denne mekanismen, la oss utforske kjernekomponentene i en grådig algoritme som skiller den fra andre prosesser:
- Kandidatsett: Et svar opprettes fra dette settet.
- Seleksjonsfunksjon: Den velger den beste kandidaten som skal inkluderes i løsningen.
- Mulighetsfunksjon: Denne delen beregner om en kandidat kan brukes til å bidra til løsningen.
- En objektiv funksjon: Den tildeler en verdi til en komplett eller delvis løsning.
- En løsningsfunksjon: Denne brukes til å indikere om en riktig løsning er oppfylt.
Hvor fungerer den grådige algoritmen best?
Grådig algoritme kan brukes på de ovennevnte problemene.
- Den grådige tilnærmingen kan brukes til å finne den minimale spredende tregrafen ved å bruke Prim's eller Kruskals algoritme
- Å finne den korteste veien mellom to toppunkt er enda et problem som kan løses ved hjelp av en grådig algoritme. Å bruke Dijkstra's algoritme sammen med den grådige algoritmen vil gi deg en optimal løsning.
- Huffman Coding
Fordeler
Den største fordelen som den grådige algoritmen har over andre er at den er enkel å implementere og veldig effektiv i de fleste tilfeller.
ulemper
Grådig algoritme bygger i utgangspunktet en løsning del for del og velger neste del på en slik måte at den gir den beste løsningen på det aktuelle problemet øyeblikkelig. Som et resultat er det ingen hensyn eller bekymring for konsekvensene av den nåværende avgjørelsen som er tatt. Greedy Algoritm unnlater aldri å vurdere en optimal løsning, selv om den gir en nær optimal løsning . Ryggsekkproblem og reisende selgerproblem er eksempler på problemer der den grådige algoritmen ikke klarer å produsere en optimal løsning.
- Ryggsekkproblem: Det vanligste navnet ryggsekkproblemet, er et dagligdags problem som mange mennesker står overfor. Si at vi har sett med varer, og hver har ulik vekt og verdi (fortjeneste) som skal fylles i en container eller bør samles på en slik måte at den totale vekten er mindre enn eller lik den for beholderen mens den totale fortjenesten maksimeres .
Konklusjon
Grådig algoritme er best aktuelt når man trenger en løsning i sanntid og omtrentlige svar er “gode nok”. Det er klart at en grådig algoritme minimerer tiden mens den sørger for at en optimal løsning blir produsert, og derfor er det mer anvendelig å bruke i en situasjon der det kreves mindre tid. Etter å ha lest denne artikkelen, kan man ha en god ide om grådige algoritmer. I tillegg forklarer dette innlegget hvorfor det blir sett på som de beste rammene som svarer på nesten alle programmeringsutfordringer sammen med å hjelpe deg med å bestemme den mest optimale løsningen på et gitt tidspunkt.
På den grove siden, for å anvende teorien om grådig algoritme, må man imidlertid jobbe hardere for å vite de riktige problemene. Selv om det er et vitenskapelig konsept som har logikk, har det også en essens av kreativitet.
Anbefalte artikler
Dette har vært en guide til Hva er en grådig algoritme. Her diskuterte vi kjernekonseptet, komponenter, fordel og ulempe ved grådig algoritme. Du kan også gå gjennom andre foreslåtte artikler for å lære mer -
- Algoritme i programmering
- Hva er Perl?
- Introduksjon til algoritme
- Hva er Agile Sprint?