Grådighet

En grådig algoritme bygger løsningen gjennom en serie valg, og tar hvert valg lokalt. Den gjør det som ser best ut her og nå, uten å løse noen delinstanser først. Dynamisk programmering løser delinstansene for alle valgene og bygger på den beste delløsningen. En grådig algoritme velger først og løser bare den ene delinstansen som er igjen. Slike algoritmer er som regel korte og raske. Det kan være vanskelig å vise at de gir riktig svar, og for mange problemer gjør de ikke det.

Grådige valg

Du får punktene $x_1 \le x_2 \le \cdots \le x_n$ på tallinja, og skal dekke dem med færrest mulig lukkede intervaller med lengde 1. Et intervall må dekke $x_1$, og det er ingen punkter til venstre for $x_1$. Legg derfor intervallet $[x_1, x_1 + 1]$, som dekker $x_1$ og går lengst til høyre. Fjern punktene det dekker, og gjenta med resten. Punktene er sortert, så algoritmen tar $\Theta(n)$ tid.

En algoritme som velger slik, er grådig. Den gjør et valg $c$, her intervallet $[x_1, x_1 + 1]$, og krymper instansen til det som er igjen etter valget, her punktene til høyre for $x_1 + 1$. Så løser den delinstansen og setter $c$ og delløsningen sammen. Valget er det beste lovlige valget sett helt lokalt, og det tas før delinstansen er løst, så algoritmen kan ikke se om det lønner seg. Dynamisk programmering som prøver alle valgene, gir også riktig svar på et problem som kan løses grådig, bare langsommere.

For at den grådige algoritmen skal være riktig, må det første valget være trygt.

Intervallproblemet har grådighetsegenskapen. La $I$ være intervallet som dekker $x_1$ i en optimal løsning. $I$ starter i $x_1$ eller til venstre for det, så det slutter i $x_1 + 1$ eller tidligere. Flytt $I$ til $[x_1, x_1 + 1]$. Det flyttede intervallet dekker fortsatt $x_1$ og alle punktene $I$ dekket til høyre for $x_1$. Løsningen har like mange intervaller og tar det grådige valget.

Grådighetsegenskapen sier ingenting om valgene etter det første. Til det trengs optimal delstruktur: det grådige valget satt sammen med en optimal løsning på delinstansen som er igjen, gir en optimal løsning. I intervallproblemet tar du den optimale løsningen som har $[x_1, x_1 + 1]$. De andre intervallene i den dekker punktene til høyre for $x_1 + 1$, så de er minst like mange som i en optimal løsning på delinstansen. Bytt dem ut med en optimal løsning på delinstansen. Antallet intervaller øker ikke, så løsningen er fortsatt optimal.

Delinstansen er et problem av samme form, så grådighetsegenskapen gjelder der også, og optimal delstruktur sier at det holder å løse den optimalt. Med induksjon over størrelsen på instansen er alle de grådige valgene trygge.

Læreboka gir en oppskrift i tre trinn.

1. Ett valg, én delinstans

   Formuler problemet så hvert valg etterlater nøyaktig én delinstans.

2. Grådighetsegenskapen

   Vis at det alltid finnes en optimal løsning som tar det grådige valget.

3. Optimal delstruktur

   Vis at det grådige valget sammen med en optimal løsning på delinstansen gir en optimal løsning.

Intervallproblemet følger oppskriften. Valget etterlater bare punktene til høyre for $x_1 + 1$, flyttingen av $I$ til $[x_1, x_1 + 1]$ viser grådighetsegenskapen, og byttet av de andre intervallene mot en optimal løsning på delinstansen viser optimal delstruktur.

Flyttingen av $I$ er et utvekslingsargument, den vanlige måten å vise grådighetsegenskapen på. Start med en vilkårlig optimal løsning. Bytt ut ett av valgene i den med det grådige valget, og vis at løsningen fortsatt er lovlig og ikke blir dårligere. Da finnes en optimal løsning med det grådige valget. Å vise at et grådig valg ikke er trygt, er lettere. Ett moteksempel holder.

Det kontinuerlige ryggsekkproblemet

I det binære ryggsekkproblemet er hver gjenstand med eller ikke med. I det kontinuerlige ryggsekkproblemet kan du ta med en andel mellom 0 og 1 av hver gjenstand, og får samme andel av verdien. Gjenstand $i$ har verdi $v_i$ og vekt $w_i$, og sekken har kapasitet $W$.

Det grådige valget er gjenstanden med høyest kilopris $v_i / w_i$. Ta med mest mulig av den, så mest mulig av den med nest høyest kilopris, og fortsett til sekken er full. Bare den siste gjenstanden blir delt. Grådighetsegenskapen vises med et utvekslingsargument. Tar en løsning mindre enn mulig av gjenstanden med høyest kilopris, har sekken tom plass eller noe med samme eller lavere kilopris. Fyll den tomme plassen, eller bytt ut like mange kilo av det andre, med den beste gjenstanden, og totalverdien øker eller står stille. Optimal delstruktur: kapasiteten som er igjen, må fylles optimalt med det som er igjen av gjenstandene. Sorteringen etter kilopris tar $O(n \lg n)$, og resten er én gjennomgang.

For det binære problemet er det samme valget ikke trygt. Med $W = 50$ og gjenstandene under har gjenstand 1 høyest kilopris.

Velger du etter kilopris, tar du 1 og 2, til 160, og da får ikke 3 plass. Det beste er 2 og 3, til 220. I det kontinuerlige problemet tar den grådige algoritmen 1, 2 og to tredjedeler av 3, til $60 + 100 + 80 = 240$, og det er optimalt. Utvekslingsargumentet virker ikke i det binære problemet, fordi en gjenstand bare kan byttes ut hel. Bytter du ut 3 med 1 i den beste løsningen, står 20 kilo tomt, og verdien synker fra 220 til 160. For å avgjøre om en gjenstand skal være med, må du sammenligne den beste løsningen med gjenstanden og den beste uten, og den sammenligningen er dynamisk programmering.

Aktivitetsutvalg

Flere aktiviteter vil bruke det samme rommet, og rommet kan bare brukes av én om gangen. Aktivitet $a_i$ varer i det halvåpne intervallet $[s_i, f_i)$, så to aktiviteter overlapper ikke når den ene slutter før eller idet den andre starter. Aktivitetsutvalg (activity selection) er å velge flest mulig aktiviteter der ingen to overlapper. Aktivitetene er sortert etter sluttid, $f_1 \le f_2 \le \cdots \le f_n$.

Velger du en aktivitet $a_k$, deler den resten i to delinstanser: aktivitetene som slutter ved $s_k$ eller før, og de som starter ved $f_k$ eller senere. Den delingen gir en løsning med dynamisk programmering som prøver hver $a_k$. Det grådige valget er $a_1$, aktiviteten som slutter først, og er det valget trygt, trenger du ikke prøve de andre. Aktiviteten $a_1$ lar rommet være ledig for flest mulig av de andre, og siden ingen aktivitet slutter før $a_1$ starter, er bare én delinstans igjen, aktivitetene som starter ved $f_1$ eller senere.

Grådighetsegenskapen vises med et utvekslingsargument. La $A$ være en optimal løsning, og la $a_j$ være aktiviteten i $A$ som slutter først. Bytt ut $a_j$ med $a_1$. De andre aktivitetene i $A$ overlapper ikke $a_j$, og siden $a_j$ slutter først, starter de ved $f_j$ eller senere. Siden $f_1 \le f_j$, slutter $a_1$ før eller idet de starter, så ingen av dem overlapper $a_1$. Løsningen er like stor og inneholder $a_1$. Optimal delstruktur: aktivitetene som starter ved $f_1$ eller senere, er en instans av samme problem og må velges optimalt.

Recursive-Activity-Selector får indeksen $k$ til den sist valgte aktiviteten, og leter fra $k + 1$ etter den første aktiviteten $a_m$ som ikke overlapper $a_k$. Aktivitetene er sortert, så $f_m \ge f_k$, og da overlapper $a_m$ ikke $a_k$ nøyaktig når $s_m \ge f_k$. Aktiviteten $a_m$ tas med, og resten løses rekursivt fra den. Det første kallet har $k = 0$, med en tenkt aktivitet $a_0$ der $f_0 = 0$. Greedy-Activity-Selector gjør det samme med en løkke.

def recursive_activity_selector(s, f, k, n):  # plass 0 er a0, med f[0] = 0
  m = k + 1
  while m <= n and s[m] < f[k]:
      m = m + 1
  if m <= n:
      return [m] + recursive_activity_selector(s, f, m, n)
  return []

def greedy_activity_selector(s, f, n):
  A = [1]
  k = 1
  for m in range(2, n + 1):
      if s[m] >= f[k]:
          A.append(m)
          k = m
  return A

Hver aktivitet sjekkes én gang, så begge versjonene tar $\Theta(n)$ tid når aktivitetene er sortert, og $O(n \lg n)$ med sorteringen.

Huffman-koder

En tekst skal lagres med færrest mulig bits. Hvert tegn $c$ i alfabetet $C$ får et binært kodeord, og den kodede teksten er kodeordene etter hverandre. Tegnet $c$ står $c.\mathit{freq}$ ganger i teksten. Med like lange kodeord trengs $\lceil \lg n \rceil$ bits per tegn for $n$ tegn. Får de hyppige tegnene korte kodeord og de sjeldne lange, blir teksten kortere.

Prefiksfrie koder

I en prefiksfri kode er ingen kodeord et prefiks av et annet. Da er det første kodeordet i en kodet tekst entydig, og teksten kan dekodes ett kodeord om gangen fra starten. Koden tegnes som et binært kodetre med tegnene i løvnodene. Kodeordet til et tegn er stien fra rota til løvnoden, der 0 er venstre barn og 1 er høyre barn, så lengden av kodeordet er dybden $d_T(c)$. Antall bits i den kodede teksten er kostnaden til treet:

Et optimalt kodetre er fullt: hver indre node har to barn. Har en indre node bare ett barn, kan noden erstattes med barnet, og alle kodeordene under den blir én bit kortere. Et fullt binærtre med $n$ løvnoder har $n - 1$ indre noder.

Dekodingen følger treet. Start i rota, les én bit om gangen, og gå til venstre barn for 0 og høyre barn for 1. I en løvnode skriver du ut tegnet og starter i rota igjen. Det tar konstant tid per bit.

Huffmans algoritme

Huffman bygger kodetreet nedenfra. Hvert tegn starter som et eget tre med én node, i en min-prioritetskø $Q$ på frekvens. I hver runde tas de to trærne med lavest frekvens, $x$ og $y$, ut av køen. De blir barn av en ny node $z$ med frekvens $x.\mathit{freq} + y.\mathit{freq}$, og $z$ settes inn i køen. Etter $n - 1$ runder er ett tre igjen, og det er kodetreet.

Valget er grådig. Å slå sammen to trær legger én bit til kodeordet for hvert tegn i dem, så sammenslåingen øker $B(T)$ med summen av frekvensene deres, og Huffman velger den billigste. Derfor er $B(T)$ også summen av frekvensene i alle de indre nodene. Med to tegn er det én indre node, begge kodeordene har én bit, og $B(T)$ er summen av de to frekvensene.

import heapq
from itertools import count

def huffman(C):  # C er en ordbok fra tegn til frekvens
  tie = count()  # løpenummer for like frekvenser, så trær sammenlignes aldri
  Q = [(freq, next(tie), c) for c, freq in C.items()]
  heapq.heapify(Q)
  for i in range(1, len(C)):
      fx, _, x = heapq.heappop(Q)
      fy, _, y = heapq.heappop(Q)
      z = (x, y)  # et tre er et tegn eller et par (venstre, høyre)
      heapq.heappush(Q, (fx + fy, next(tie), z))
  return Q[0][2]

def codes(T, prefix=""):
  if isinstance(T, str):
      return {T: prefix}
  return codes(T[0], prefix + "0") | codes(T[1], prefix + "1")

def decode(T, bits):
  text, x = "", T
  for b in bits:
      x = x[0] if b == "0" else x[1]
      if isinstance(x, str):
          text += x
          x = T
  return text

Med en binær min-haug bygges køen i $O(n)$ tid, og hver av de $n - 1$ rundene gjør tre køoperasjoner på $O(\lg n)$. Til sammen er det $O(n \lg n)$.

Hvorfor koden er optimal

Står et tegn ett nivå dypere, blir kodeordet én bit lengre, og den kodede teksten blir like mange bits lengre som tegnet har frekvens. De sjeldneste tegnene hører derfor hjemme nederst. Grådighetsegenskapen: la $x$ og $y$ være de to tegnene med lavest frekvens. Da finnes et optimalt kodetre der $x$ og $y$ er søsken på største dybde. Ta et optimalt tre $T$, og la $a$ og $b$ være søsken på største dybde. Bytt plass på $x$ og $a$, og kall det nye treet $T_1$. I $B(T)$ står $x.\mathit{freq}\, d_T(x) + a.\mathit{freq}\, d_T(a)$, og i $B(T_1)$ står $x.\mathit{freq}\, d_T(a) + a.\mathit{freq}\, d_T(x)$. Alle andre ledd er like, så kostnaden synker med

fordi $x$ har lavest frekvens og $a$ står dypest. Byttet gjør ikke treet dyrere, og det samme gjelder for å bytte $y$ og $b$. Treet er fortsatt optimalt, og $x$ og $y$ er søsken nederst, slik Huffman setter dem sammen.

Optimal delstruktur: erstatt $x$ og $y$ med ett nytt tegn $z$ med frekvens $x.\mathit{freq} + y.\mathit{freq}$, og la $T'$ være et kodetre for det nye alfabetet. Får $z$ barna $x$ og $y$, blir kodeordene deres én bit lengre enn kodeordet til $z$, og alle andre kodeord er like:

Tillegget avhenger ikke av $T'$, så blant trærne der $x$ og $y$ er søsken, er $T$ optimalt når $T'$ er det. Grådighetsegenskapen sier at et av disse trærne er optimalt blant alle, så $T$ er optimalt. Etter å ha slått sammen $x$ og $y$ løser Huffman nettopp det mindre problemet der $z$ er ett tegn.

Eksamensoppgave Hvilke trær er huffmantrær

Ordinær eksamen, desember 2024, oppgave 8

Du har oppgitt følgende frekvenser for tegnene a, b, c og d:

$$a.\mathit{freq} = 8 \allowbreak\qquad b.\mathit{freq} = 4 \allowbreak\qquad c.\mathit{freq} = 2 \allowbreak\qquad d.\mathit{freq} = 4$$

Med «huffmantre» menes et tre som kan konstrueres av Huffmans algoritme, hvis det er tilfeldig om en barnenode havner til venstre eller høyre. Det er minst ett korrekt huffmantre i figur 1, men det kan være flere.

Hvilke av trærne 1–5 i figur 1 er korrekte huffmantrær for disse tegnene, med disse frekvensene? Forklar kort. Flere svar er riktige. Kryss av alle som stemmer.

• 1
• 2
• 3
• 4
• 5

Sjekk svar

Sjekk deg selv