Greedytilnærming

Greedytilnærming er en algoritmisk strategi der man ved hvert trinn velger det tilsynelatende beste valget, med håp om å bygge en helhetsløsning uten å revurdere tidligere beslutninger. Ideen er å konstruere løsningen trinnvis ved å ta det valget som gir størst umiddelbar gevinst eller laveste kostnad. En vellykket greedytilnærming krever ofte at problemet har en greedy-valg-egenskap og en optimal understruktur; hvis disse egenskapene mangler, kan løsningen bli suboptimal.

Typiske kjennetegn er bruk av sortering eller prioriteringskøer, og ofte enkel implementasjon samt lavere kjøretid enn generelle søkeprosesser. Det finnes problemer der en greedytilnærming gir optimal løsning, spesielt når understruktur og valg-egenskaper stemmer.

Vanlige eksempler inkluderer: aktivitet-valgproblemet, der man maksimerer antall ikke-overlappende aktiviteter ved å sortere etter sluttid; Kruskal’s og Prim’s algoritmer for minste spanning tree; Dijkstra’s algoritme for korteste vei i grafer med ikke-negative vekter; Huffman-koding for effektiv komprimering; og visse myntevekslingsproblemer hvor en enkel lokale beslutning gir globalt optimal løsning.

Fordeler er enkelhet, rask kjøring og lavt ressursforbruk, mens begrensningene inkluderer at ikke alle problemer egner seg for greedytilnærming, og at man ofte ikke får en garantert globalt optimal løsning. I praksis brukes tilnærmingen ofte som et første forsøk eller som en del av mer avanserte metoder.