Grådighet

En grådig algoritme bygger en løsning ved å gjøre det valget som ser best ut akkurat nå, og angrer aldri. Hvert slikt grådige valg er lokalt; utfordringen er sjelden å utføre det — det er å bevise at en stripe av lokale valg faktisk ender i et globalt optimum. Når det holder, er grådige algoritmer ofte de enkleste og raskeste vi har.

De to egenskapene en grådig algoritme trenger

Grådighet er beslektet med dynamisk programmering — begge bygger på optimal delstruktur — men der DP vurderer alle første valg, satser grådighet på ett. Det krever en egenskap til.

Det typiske beviset for grådighetsegenskapen er et ombyttingsargument: ta en vilkårlig optimal løsning, og vis at du kan bytte ut dens første valg med det grådige valget uten å gjøre løsningen dårligere. Da finnes en like god optimal løsning som starter grådig.

Aktivitetsutvelgelse

Gitt aktiviteter med start- og sluttider skal vi velge flest mulig som ikke overlapper. Det grådige valget er overraskende enkelt: velg alltid aktiviteten som slutter først. Den frigjør ressursen tidligst og etterlater mest plass til resten.

1. Sorter etter sluttid

   Sorter alle aktivitetene stigende på sluttidspunkt. Dette er den dominerende kostnaden, $O(n \lg n)$.

2. Velg den som slutter først

   Ta den første aktiviteten i den sorterte rekkefølgen — den med tidligst sluttid er alltid med i en optimal løsning (grådighetsegenskapen).

3. Hopp over det som kolliderer

   Gå videre nedover lista og hopp over alle aktiviteter som starter før den sist valgte sluttet.

4. Gjenta på resten

   Den neste aktiviteten som er kompatibel velges, og prosessen gjentas til lista er tom. Hele skanningen etter sortering er $O(n)$.

Beviset er et ombyttingsargument: har en optimal løsning en annen første aktivitet, kan vi erstatte den med den som slutter først uten å skape nye kollisjoner — løsningen forblir like stor. Etter sorteringen koster utvelgelsen bare én lineær skanning, så algoritmen er $O(n \lg n)$ totalt.

Kontinuerlig (fractional) ryggsekk

Her er det grådighet — og ikke DP — som er rett verktøy. I den kontinuerlige ryggsekken kan gjenstander deles: vi kan ta en brøkdel av en gjenstand. Det grådige valget er å sortere på verditetthet $v_i / w_i$ og fylle sekken med den tetteste først, og til slutt ta en brøkdel av den neste for å fylle akkurat opp til kapasiteten.

Huffman-koder

Huffman-algoritmen bygger en optimal prefikskode for å komprimere data: hyppige tegn får korte bitstrenger, sjeldne får lange, og ingen kode er prefiks av en annen (så avkoding er entydig). Det grådige valget jobber nedenfra: gjentatte ganger slå sammen de to symbolene med lavest frekvens til én ny node hvis frekvens er summen, helt til alt henger i ett tre.

Med en min-haug for å hente de to minste frekvensene koster hver av de $n-1$ sammenslåingene $O(\lg n)$, så Huffman bygger den optimale koden i $O(n \lg n)$.

Sjekk deg selv