I denne vejledning lærer du, hvad en grådig algoritme er. Du vil også finde et eksempel på en grådig tilgang.
En grådig algoritme er en fremgangsmåde til løsning af et problem ved at vælge den bedste tilgængelige løsning i øjeblikket uden at bekymre sig om det fremtidige resultat, det ville bringe. Med andre ord sigter de lokalt bedste valg mod at producere de bedste resultater globalt.
Denne algoritme er muligvis ikke den bedste mulighed for alle problemerne. Det kan i nogle tilfælde give forkerte resultater.
Denne algoritme går aldrig tilbage for at vende beslutningen. Denne algoritme fungerer i en top-down tilgang.
Den største fordel ved denne algoritme er:
- Algoritmen er lettere at beskrive .
- Denne algoritme kan fungere bedre end andre algoritmer (men ikke i alle tilfælde).
Mulig løsning
En mulig løsning er den løsning, der giver den optimale løsning på problemet.
Grådig algoritme
- Til at begynde med er løsningssættet (indeholdende svar) tomt.
- Ved hvert trin tilføjes et element i løsningssættet.
- Hvis løsningssættet er muligt, bevares den aktuelle vare.
- Ellers afvises varen og overvejes aldrig igen.
Eksempel - Grådig tilgang
Problem: Du skal foretage en ændring af et beløb ved hjælp af det mindst mulige antal mønter. Beløb: $ 28 Tilgængelige mønter: $ 5 mønt $ 2 mønt $ 1 mønt
Løsning:
- Opret et tomt løsningssæt = ().
- mønter = (5, 2, 1)
- sum = 0
- Mens sum ≠ 28, gør følgende.
- Vælg en mønt C fra mønter sådan, at summen + C <28.
- Hvis C + sum> 28, returneres ingen løsning.
- Ellers sum = sum + C.
- Føj C til løsningssættet.
Op til de første 5 iterationer indeholder løsningssættet 5 $ 5 mønter. Derefter får vi 1 $ 2 mønt og endelig 1 $ 1 mønt.
Grådige algoritme applikationer
- Valg af sortering
- Rygsækproblem
- Minimum spændende træ
- Enkeltkildes korteste sti-problem
- Jobplanlægningsproblem
- Prims minimale spændende træalgoritme
- Kruskals minimale spændende træalgoritme
- Dijkstras minimale spændende træalgoritme
- Huffman-kodning
- Ford-Fulkerson algoritme
