Greedy algoritmer er en type algoritmisk strategi som gjør det optimale valget i hvert trinn med håp om å finne den globale optimal. De er mye brukt til å løse optimaliseringsproblemer der lokale beslutninger fører til en globalt optimal løsning. Denne artikkelen utforsker konseptet av grådige algoritmer, gir praktiske eksempler og demonstrerer hvordan du utfører relaterte beregninger.

Hva er greedy algoritmer?

En grådig algoritme bygger opp en løsningsbit etter stykke, alltid velge det neste stykket som tilbyr den mest umiddelbare fordelen. Denne tilnærmingen er enkel og effektiv, men garanterer ikke alltid den beste totale løsningen for alle problemer. Det er mest effektivt når problemet utviser den grådige-valg eiendom og optimale substruktur.

Praktiske eksempler

Vanlige problemer som løses ved hjelp av grådige algoritmer inkluderer myntendringsproblemet, aktivitetsvalget og fraksjonsproblemet. Disse eksemplene viser hvordan å gjøre lokalt optimale valg kan føre til en global optimal løsning i bestemte scenarier.

Beregninger og implementering

Tenk på problemet med myntendringen der målet er å gjøre endringer for et visst beløp ved hjelp av de færreste myntene. Antak at myntberegningene er 1, 5, 10 og 25 cent, og målbeløpet er 63 cent. Den grådige tilnærmingen innebærer å velge den største mynten mindre enn eller lik den resterende mengden ved hvert trinn.

Trinn-for-trinns beregning:

  • Velg 25 cent (gjenopprette: 63 - 25 = 38)
  • Velg 25 cent (gjenopprette: 38 - 25 = 13)
  • Velg 10 cent (gjenopprette: 13 - 10 = 3)
  • Velg 1 cent (gjenopprette: 3 - 1 = 2)
  • Velg 1 cent (gjenopprette: 2 - 1 = 1)
  • Velg 1 cent (gjenstår: 1 - 1 = 0)

Totalt antall mynter som brukes: 6.