I denne opplæringen vil du lære hva en grådig algoritme er. Du vil også finne et eksempel på en grådig tilnærming.
En grådig algoritme er en tilnærming for å løse et problem ved å velge det beste alternativet tilgjengelig for øyeblikket, uten å bekymre deg for det fremtidige resultatet det vil bringe. Med andre ord tar de lokalt beste valgene sikte på å gi de beste resultatene globalt.
Denne algoritmen er kanskje ikke det beste alternativet for alle problemene. I noen tilfeller kan det gi gale resultater.
Denne algoritmen går aldri tilbake for å reversere beslutningen. Denne algoritmen fungerer i en top-down-tilnærming.
Den største fordelen med denne algoritmen er:
- Algoritmen er lettere å beskrive .
- Denne algoritmen kan fungere bedre enn andre algoritmer (men ikke i alle tilfeller).
Gjennomførbar løsning
En gjennomførbar løsning er den som gir den optimale løsningen på problemet.
Grådig algoritme
- Til å begynne med er løsningssettet (som inneholder svar) tomt.
- Ved hvert trinn legges et element til i løsningssettet.
- Hvis løsningssettet er gjennomførbart, beholdes den nåværende varen.
- Ellers avvises varen og blir aldri vurdert på nytt.
Eksempel - Grådig tilnærming
Problem: Du må endre et beløp ved å bruke minst mulig antall mynter. Beløp: $ 28 Tilgjengelige mynter: $ 5 mynt $ 2 mynt $ 1 mynt
Løsning:
- Lag et tomt løsningssett = ().
- mynter = (5, 2, 1)
- sum = 0
- Mens sum ≠ 28, gjør du følgende.
- Velg en mynt C fra mynter slik at summen + C <28.
- Hvis C + sum> 28, returner ingen løsning.
- Else, sum = sum + C.
- Legg C til løsningssettet.
Opp til de fem første iterasjonene inneholder løsningssettet 5 $ 5 mynter. Etter det får vi 1 $ 2 mynt og til slutt 1 $ 1 mynt.
Grådige algoritmeapplikasjoner
- Valg Sorter
- Ryggsekkproblem
- Minimum spennende tre
- Enkeltkildes problem med korteste vei
- Jobbplanlegging Problem
- Prim's Minimal Spanning Tree Algorithm
- Kruskals Minimal Spanning Tree Algorithm
- Dijkstra's Minimal Spanning Tree Algorithm
- Huffman Coding
- Ford-Fulkerson algoritme
