greedyløsning

Greedyløsning, ofte kalt en greedy-algoritme, er en tilnærming i algoritmedesign der løsningen bygges trinnvis ved å velge det lokalt beste alternativet i hvert steg og ikke går tilbake. Målet er å oppnå en globalt optimal løsning, men det garanteres ikke for alle problemer.

Kjennetegnene ved greedyløsninger inkluderer en greedy-choice property, som innebærer at det valgte alternativet beholder sin verdi i alle fullstendige løsninger som inneholder det, samt en optimal understruktur, som sier at en optimal løsning består av optimale del-løsninger. Fordelen er ofte enkel implementasjon og lavere kjøretid sammenlignet med mer generelle metoder som dynamisk programmering, men ulempen er at løsningen ikke alltid er globalt optimal.

Vanlige bruksområder omfatter problemer som kan behandles med en rekke eksplisitte valg samtidig som de har greedy-choice og optimal understruktur. Eksempler er korteste vei i grafer med ikke-negative vekter (Dijkstra), minste-spantetre (Kruskal og Prim), intervallscheduling og visse mynt-problemer under canonical mynter-systemer.

Begrensninger inkluderer at greedyløsninger ikke passer alle problemtyper; for eksempel knapsack-problemet i 0/1-form og set cover kan kreve andre tilnærminger som dynamisk programmering eller helt andre metoder for å oppnå optimal løsning. En sentral del av bruken er dermed å bevise eller avkrefse korrektheten gjennom egenskaper som utvekslingsargumenter eller ved å vise at problemet har greediness og optimal understruktur.

Greedyløsning er derfor en viktig teknikk i algoritmeverktøyboksen, karakterisert av lokal beslutningstaking som ofte gir raske og enkle løsninger, men med begrensninger i gyldighet.