Grådige algoritmer

Å ta det beste valget akkurat nå

Tenk deg at du står i kassakøen og skal gi tilbake 47 kroner i mynter, og du vil bruke færrest mulig. Du tar den største mynten som ikke overskrider beløpet — en 20-kroning — og spør deretter det samme om resten: 27 kroner. Igjen en 20-kroning, så en 5-kroning, så to 1-kroninger. Du vurderte aldri alle kombinasjoner; du tok bare det lokalt beste valget hver gang og lot resten følge. Det er kjernen i en grådig algoritme: bygg løsningen steg for steg, og ta i hvert steg det valget som ser best ut der og da, uten å angre.

Det forbløffende er at denne nærsynte strategien noen ganger gir et globalt optimalt svar. Men ikke alltid. Med et tenkt myntsystem på 1, 5 og 8 kroner gir grådighet 13 = 8 + 5 (to mynter), men for 16 tar grådighet 8 + 8 = 16 (to mynter) der det også er optimalt — mens for 10 tar grådighet 8 + 1 + 1 (tre mynter) når 5 + 5 (to mynter) er bedre. Grådighet feilet. Hele dette kapittelet handler om å forstå når den nærsynte strategien er trygg, og hvordan vi beviser det.

To egenskaper må være på plass

Et grådig argument hviler på to ben. Det første er optimal delstruktur: en optimal løsning på hele problemet må inneholde en optimal løsning på det som gjenstår etter et valg. ƒgrådig krever optimal delstruktur Hvis vi tar et grådig valg og deretter løser den gjenstående delinstansen optimalt, skal de to bitene til sammen utgjøre en optimal helhet. Mangler denne strukturen, er det meningsløst å bygge løsningen stykkevis.

Det andre benet er grådig-valg-egenskapen. Den sier at det lokalt beste valget faktisk kan inngå i en optimal løsning. ƒgrådig-valg-egenskapen Merk «en»: vi krever ikke at enhver optimal løsning inneholder det grådige valget, bare at minst én gjør det. Da kan vi trygt ta valget og aldri se oss tilbake. Forskjellen fra dynamisk programmering er nettopp dette: en DP-algoritme vurderer flere valg i hvert steg og lar tilbakekoblingen avgjøre, mens grådighet binder seg til ett valg umiddelbart. Det er raskere, men virker bare når grådig-valg-egenskapen holder.

Utbyttingsargumentet: slik beviser vi at valget er trygt

Hvordan vet vi at det grådige valget er trygt? Vi bruker et utbyttingsargument. Idéen er enkel og kraftig: ta en hvilken som helst optimal løsning. Hvis den allerede inneholder det grådige valget, er vi ferdige. Hvis ikke, viser vi at vi kan bytte ut ett element i den optimale løsningen med det grådige valget, uten å gjøre løsningen dårligere. Etter byttet er løsningen fortsatt optimal, og nå inneholder den det grådige valget. Dermed finnes det alltid en optimal løsning som starter grådig.

Dette mønsteret går igjen i alle grådige bevis. Du antar en optimal løsning, peker på det grådige valget den eventuelt mangler, og argumenterer for at en byttehandling ikke kan tape noe. Vi skal se det konkret nå.

Aktivitetsutvelgelse: tidligst slutt vinner

Du har ett auditorium og en bunke forelesninger som hver har en start- og en slutt-tid. To forelesninger er kompatible hvis de ikke overlapper. Du vil få plass til flest mulig. Dette er aktivitetsutvelgelse, og den grådige regelen er overraskende enkel: blant aktivitetene som fortsatt er kompatible, velg alltid den som blir ferdig først. ƒaktivitetsutvelgelse

Hvorfor tidligst slutt, og ikke for eksempel kortest varighet eller tidligst start? Fordi den aktiviteten som slutter først, etterlater mest tid til alt det andre. Den «spiser opp» minst mulig av tidslinja. Utbyttingsargumentet gjør dette presist: la $a_m$ være aktiviteten med tidligst slutt-tid, og la $S$ være en optimal løsning. Hvis $a_m$ ikke er i $S$, ser vi på den aktiviteten i $S$ som slutter først — kall den $a_k$. Siden $a_m$ slutter minst like tidlig som $a_k$, kan vi bytte ut $a_k$ med $a_m$ i $S$. Den nye løsningen har like mange aktiviteter og er fortsatt gyldig, fordi $a_m$ slutter tidligere og dermed ikke kan kollidere med resten. Altså finnes det en optimal løsning som inneholder $a_m$ — grådig-valg-egenskapen holder.

I figuren over sorterer vi etter slutt-tid og plukker $a_1$ (slutter ved 4). Da forkastes alt som overlapper $a_1$. Neste kompatible med tidligst slutt er $a_4$ (start 5, slutt 7), og til sist $a_8$ (start 8). Resultatet er tre aktiviteter. Algoritmen i 0-indeksert stil:

AKTIVITETSUTVALG(start[], slutt[])     // antar sortert på slutt stigende
    valgt = [0]                         // ta aktiviteten som slutter først
    forrige = 0
    for i = 1 to n - 1
        if start[i] >= slutt[forrige]   // kompatibel med sist valgte
            valgt.append(i)
            forrige = i
    return valgt

Når aktivitetene først er sortert på slutt-tid, gjør løkka bare ett gjennomløp. Selve utvalget er $\Theta (n)$; sorteringen på forhånd koster $\Theta (n\lg n)$ og dominerer.

Huffman-koding: grådighet på bits

Det neste eksempelet er datakomprimering. Du skal lagre en tekst med færrest mulig bits. En fast kode gir hvert tegn like mange bits, men det er sløsing hvis noen tegn er mye vanligere enn andre. Bedre å gi hyppige tegn korte kodeord og sjeldne tegn lange. Det er nettopp det huffman-koding gjør.

Men variabel lengde skaper et problem: hvor slutter ett kodeord og hvor begynner det neste? Løsningen er en prefiksfri kode kode — ingen kodeord er en innledning til et annet. Er 0 et kodeord, kan ikke noe annet kodeord starte med 0. Da kan dekoderen lese bit for bit og vite nøyaktig når et tegn er ferdig, uten skilletegn. Prefiksfrie koder svarer til binærtrær der hvert tegn sitter i et blad og kodeordet er stien fra rota: venstre er 0, høyre er 1. Kostnaden vi minimerer er den vektede stilengden, summen av hver frekvens ganget med dybden i treet. ƒhuffman-koding

Det grådige grepet er å bygge treet nedenfra. Gjentatte ganger: ta de to symbolene med lavest frekvens og slå dem sammen til én ny node med summen av frekvensene. Gjenta til alt henger sammen i ett tre. De minst hyppige tegnene havner dermed dypest — lengst kodeord — akkurat som vi vil.

Anta frekvensene A:8, B:3, C:2, D:5, E:2. Vi tar de to minste, C:2 og E:2, og slår dem til en node med vekt 4. Nå er de minste B:3 og denne 4-noden — slå dem til 7. Deretter D:5 og 7 til 12, og til slutt A:8 og 12 til rota 20. Les kodene fra rota: A er nærmest og får 0, mens C og E sitter dypest og får 1110 og 1111. Den vanligste bokstaven fikk ett bit, de sjeldneste fire — som ønsket.

Hvorfor er det grådige byttet trygt her? Fordi i et optimalt tre må de to minst hyppige tegnene sitte på den dypeste nivået, som søsken. Hvis et hyppigere tegn satt dypere enn et sjeldnere, kunne vi byttet dem og redusert den vektede stilengden — et utbyttingsargument igjen. Derfor taper vi aldri på å slå sammen de to minste først. Med en prioritetskø (binærhaug) over frekvensene koster hver sammenslåing $O(\lg n)$, og vi gjør $n-1$ av dem, så hele byggingen er $O(n\lg n)$.

Når grådighet ikke holder

Det er fristende å tro at grådighet alltid virker fordi den er så enkel, men grådig vs. dynamisk programmering er et viktig skille. Begge bygger på optimal delstruktur. Forskjellen er at grådighet binder seg til ett valg uten å vurdere konsekvensene nedover, mens dynamisk programmering holder flere muligheter åpne og lar dem konkurrere. Myntveksling med uvennlige myntverdier, og det såkalte 0/1-ryggsekkproblemet, er klassiske eksempler der grådighet gir feil svar mens DP gir riktig. Når du møter et nytt optimaliseringsproblem, er det ikke nok at en grådig regel ser plausibel ut — du må kunne bevise grådig-valg-egenskapen med et utbyttingsargument. Klarer du ikke det, er det ofte fordi den ikke holder, og da må du gå til dynamisk programmering.

Lærdommen fra dette kapittelet er todelt. Grådighet er et skarpt verktøy: når det passer, gir det enkle og raske algoritmer, slik vi så for aktivitetsutvelgelse og Huffman. Men verktøyet er smalt. De to egenskapene — optimal delstruktur og grådig-valg — er ikke pynt; de er beviskravene som skiller en korrekt grådig algoritme fra en som tilfeldigvis ser riktig ut på små eksempler.