CSP I: formulering og konsistens

Et institutt skal legge eksamen i fem emner over tre dager: Algoritmer, Databaser, Etikk, Logikk og Planlegging. Noen studenter tar flere av emnene og kan ikke ha to eksamener samme dag. Etikk er forkurs for Databaser, og instituttet vil ha etikkeksamenen først. Den store salen er opptatt dag 1, og Algoritmer trenger den.

Et søkeproblem fra kapittel 2 behandler en tilstand som en svart boks: algoritmen vet bare hvilke handlinger som finnes, og om målet er nådd. Et begrensningsproblem (constraint satisfaction problem, CSP) åpner boksen. Tilstanden er en samling variabler med verdier, og målet er gitt av eksplisitte regler. Formelt er problemet en ƒCSP-trippel:

• •$X=\{X_1,\dots ,X_n\}$ er variablene, her $A,D,E,L,P$ med én eksamen hver.
• •$D=\{D_1,\dots ,D_n\}$ er domenene. Et domene (domain) er mengden verdier en variabel kan få, her dagene $\{1,2,3\}$.
• •$C$ er mengden begrensninger. En begrensning (constraint) har et omfang, altså variablene den gjelder, og en relasjon som sier hvilke kombinasjoner av verdier som er lov, for eksempel $E<D$.

En tilordning (assignment) gir verdier til noen eller alle variablene. Den er konsistent når den ikke bryter noen begrensning, og komplett når alle variablene har fått en verdi. En løsning er en tilordning som er både konsistent og komplett. Delvise tilordninger er like viktige: søket i kapittel 10 bygger dem opp én variabel om gangen.

Hvor mange komplette tilordninger finnes? Hver av de $n$ variablene kan få hver av de $d$ verdiene, så ƒantall komplette tilordninger er $d^n$. For eksamensplanen er det $3^5=243$, regnet med de fulle domenene før $A\ne 1$ er brukt. Det er overkommelig her, men med 30 emner og 10 dager er det $10^{30}$ planer. Formuleringen lønner seg fordi begrensningene lar oss forkaste store deler av rommet uten å se på planene én og én.

Det finnes en gevinst til. Fordi tilstanden har en fast struktur, kan de samme algoritmene løse alle problemer som er skrevet på denne formen: timeplaner, vaktlister, kartfarging og puslespill. Vi trenger ingen problemspesifikk heuristikk av typen $h(n)$ fra kapittel 3. Heuristikkene i kapittel 10 leser bare domenene og grafen.

En begrensningsgraf (constraint graph) har én node per variabel og en kant mellom to variabler når en begrensning knytter dem sammen. Grafen for eksamensplanen har fem noder og fem kanter. Den viser hvem som påvirker hvem: Planlegging henger bare sammen med Etikk, mens Etikk og Logikk har tre naboer hver.

Kanten mellom Etikk og Databaser er urettet, selv om begrensningen er $E<D$. Det er relasjonen som har en retning, ikke påvirkningen: en dag for $E$ utelukker dager for $D$, og en dag for $D$ utelukker like mye for $E$. Algoritmene i resten av kapitlet går derfor hver kant i begge retninger.

Begrensninger sorteres etter hvor mange variabler de gjelder:

• •En unær begrensning (unary constraint) gjelder én variabel, som $A\ne 1$. Den blir ingen kant, men krymper domenet direkte.
• •En binær begrensning (binary constraint) gjelder to variabler, som $D\ne L$, og blir én kant.
• •En global begrensning (global constraint) gjelder vilkårlig mange variabler. Den vanligste er alldiff, som krever at alle variablene i omfanget får ulike verdier.

Alldiff kan alltid skrives om til binære ulikheter, én for hvert par. Har et par allerede en annen begrensning, blir det likevel én kant med begge kravene. Andre begrensninger på tre eller flere variabler, som $X+Y=Z$, kan gjøres binære med en hjelpevariabel (auxiliary variable): innfør en ny variabel $W$ hvis domene er alle trippler $(x,y,z)$ med $x+y=z$, og knytt hver av $X$, $Y$ og $Z$ til $W$ med en binær begrensning som sier at variabelen er lik sin komponent i $W$. Derfor holder det å kunne behandle binære begrensninger.

Ikke alle regler er absolutte. En preferansebegrensning (preference constraint) sier hva som er ønsket, for eksempel at en sensor helst ikke vil rette dag 3. Den kan brytes mot en kostnad, og problemet blir da et optimeringsproblem. Eksamensoppgaver handler nesten alltid om absolutte begrensninger.

Domenene kan også variere. I dette kapitlet er de endelige og små, som dagene 1–3. Et domene kan også være uendelig, for eksempel alle heltall når starttidspunktet for en jobb er variabelen. Da kan begrensningene ikke ramses opp som lovlige par, men skrives som ulikheter: skal jobb 1 med varighet 3 være ferdig før jobb 2 starter, blir det $T_1+3\le T_2$. Med kontinuerlige domener og lineære begrensninger er problemet lineær programmering, som løses med helt andre metoder.

Begrensningene kan brukes før søket starter. Ideen kalles begrensningspropagering (constraint propagation): fjern verdier som ikke kan være med i noen løsning, så søket får færre valg.

Det enkleste nivået er nodekonsistens (node consistency). En variabel er nodekonsistent når alle verdiene i domenet oppfyller de unære begrensningene. I eksamensplanen fjerner nodekonsistens dag 1 fra Algoritmer, så $D_A=\{2,3\}$. Etterpå kan de unære begrensningene strykes fra problemet.

Neste nivå er buekonsistens (arc consistency). En bue er et ordnet par $(X_i,X_j)$ med en binær begrensning mellom variablene. $X_i$ er buekonsistent mot $X_j$ når hver verdi $x$ i $D_i$ har minst én støtte $y$ i $D_j$, altså en verdi som sammen med $x$ oppfyller begrensningen. Det er ƒkravet om buekonsistens:

Operasjonen som gjør en bue konsistent, kalles REVISE: gå gjennom verdiene i $D_i$ én for én, let etter en støtte i $D_j$, og fjern verdien hvis ingen finnes. REVISE$(X_i,X_j)$ endrer bare $D_i$. $D_j$ står urørt, også når noen av verdiene der mangler støtte. Derfor gir hver kant i grafen, altså hvert par av variabler med minst én begrensning mellom seg, to buer, én i hver retning. Et problem med $c$ kanter har $2c$ buer, også når et par har to begrensninger.

En forening skal holde budsjettmøte og styremøte samme uke, dag 1–5. Budsjettet må behandles før styret vedtar det, budsjettmøtet kan ikke være mandag, og styret møtes ikke fredag.

Samme regel virker i eksamensplanen. REVISE$(E,D)$ fjerner dag 3 fra Etikk, fordi ingen dag for Databaser kommer etter dag 3. REVISE$(D,E)$ fjerner dag 1 fra Databaser av samme grunn i motsatt retning. Én begrensning ga to buer og to fjernede verdier.

Én runde REVISE over alle buene er ikke nok. Når $D_i$ krymper, kan en verdi hos en nabo $X_k$ ha mistet sin eneste støtte, og buen $(X_k,X_i)$ som var konsistent, er det ikke lenger. AC-3 holder styr på buene som må sjekkes, i en kø:

1. 1.Legg alle buene i køen, i begge retninger. Standarden i dette faget er alfabetisk rekkefølge på $(X_i,X_j)$.
2. 2.Ta ut buen først i køen og kjør REVISE på den.
3. 3.Ble $D_i$ tomt, finnes ingen løsning. Stopp med «inkonsistent».
4. 4.Krympet $D_i$, legg $(X_k,X_i)$ bakerst i køen for hver nabo $X_k\ne X_j$, i alfabetisk rekkefølge, men bare hvis buen ikke allerede står i køen.
5. 5.Gjenta til køen er tom.

Hvorfor legges ikke $(X_j,X_i)$ tilbake? En verdi som ble fjernet fra $D_i$, hadde ingen støtte i $D_j$. Den støttet dermed heller ingen verdi i $D_j$, så ingen verdi der kan ha mistet støtten sin.

1ac3(domener, buer):2    kø = alle buer (xi, xj) i begge retninger, sortert alfabetisk3    så lenge kø ikke er tom:4        (xi, xj) = ta ut første bue i kø5        hvis revider(xi, xj, domener):          # D[xi] krympet6            hvis D[xi] er tom:7                returner inkonsistent8            for hver nabo xk av xi med xk ≠ xj, alfabetisk:9                hvis (xk, xi) ikke står i kø:10                    legg (xk, xi) bakerst i kø11    returner domener12 13revider(xi, xj, domener):14    endret = usann15    for hver verdi x i D[xi]:16        hvis ingen y i D[xj] passer med x:      # x mangler støtte17            fjern x fra D[xi]18            endret = sann19    returner endret

Fire frivillige på en festival skal fordeles på vakt 1–4. Bjørn og Lise deler bil og vil ha samme vakt. Kari lærer opp Lise og må ha en tidligere vakt, og Lise lærer opp Rolf på samme måte.

Etter AC-3 har hver frivillig to mulige vakter igjen. Problemet er buekonsistent, men ikke løst: søket må fortsatt velge.

Betyr rekkefølgen i køen noe? For sluttdomenene gjør den ikke det. AC-3 ender alltid med de største domenene som er buekonsistente, uansett hvilken bue som tas først. Rekkefølgen avgjør derimot hvor mange REVISE-kall som trengs, hvilke rader som står i tabellen, og hvilken bue som tømmer et domene først i et inkonsistent problem. Derfor oppgir eksamensoppgaver køregelen.

Hvor dyrt er AC-3? En bue $(X_k,X_i)$ legges tilbake bare når $D_i$ krymper, og det kan skje høyst $d$ ganger. Med $c$ kanter (par av variabler med minst én begrensning) er det $2c$ buer, og hver REVISE sammenligner opptil $d\cdot d$ verdipar. ƒKjøretiden til AC-3 blir dermed $O(c{d}^3)$, altså polynomisk, mens søket i verste fall er eksponentielt.

Koden under kjører AC-3 på eksamensplanen fra første steg, med dagene 1 til maks_verdi.

maks_verdi = 3  # @param 2..6

# Eksamensplanen: A, D, E, L, P får en dag fra 1 til maks_verdi
D = {x: set(range(1, maks_verdi + 1)) for x in "ADELP"}
D["A"].discard(1)  # nodekonsistens: A ≠ 1
regler = {("E", "D"): lambda e, d: e < d, ("D", "L"): lambda d, l: d != l,
          ("E", "L"): lambda e, l: e != l, ("E", "P"): lambda e, p: e != p,
          ("A", "L"): lambda a, l: a != l}
rel = {}
for (x, y), f in regler.items():  # én bue i hver retning
    rel[(x, y)] = f
    rel[(y, x)] = lambda b, a, f=f: f(a, b)

naboer = {x: {b for a, b in rel if a == x} for x in "ADELP"}
ko = sorted(rel)  # startkøen: alle buer, alfabetisk
kall, konsistent = 0, True
while ko and konsistent:
    xi, xj = ko.pop(0)  # REVISE(xi, xj)
    kall += 1
    nytt = {x for x in D[xi] if any(rel[(xi, xj)](x, y) for y in D[xj])}
    if nytt != D[xi]:
        konsistent = bool(nytt)
        ko += [(k, xi) for k in sorted(naboer[xi] - {xj}) if (k, xi) not in ko]
    D[xi] = nytt

vis = lambda x: "{" + ", ".join(map(str, sorted(D[x]))) + "}" if D[x] else "∅"
print(f"Domene A: {vis('A')}")  # én linje «Domene <X>:» per variabel
print(f"Domene D: {vis('D')}")
print(f"Domene E: {vis('E')}")
print(f"Domene L: {vis('L')}")
print(f"Domene P: {vis('P')}")
print(f"REVISE-kall: {kall}")
print(f"Konsistent: {'ja' if konsistent else 'nei'}")

Tre variabler $X$, $Y$ og $Z$ med domene $\{1,2\}$ og $X\ne Y$, $Y\ne Z$, $X\ne Z$ er buekonsistente: hver verdi har en støtte langs hver kant. Likevel finnes ingen løsning, fordi tre variabler ikke kan få tre ulike verdier fra et domene med to. AC-3 ser bare på én kant om gangen og oppdager det ikke.

Neste nivå, stikonsistens (path consistency), ser på tre variabler samtidig. Paret $(X_i,X_j)$ er stikonsistent mot $X_m$ når hver konsistent tilordning av $X_i$ og $X_j$ kan utvides med en verdi for $X_m$ som passer med begge. I eksempelet over kan $X=1$, $Y=2$ ikke utvides med noen verdi for $Z$, og stikonsistens avslører problemet.

Generelt sier k-konsistens (k-consistency) at hver konsistent tilordning av $k-1$ variabler kan utvides med en verdi for en hvilken som helst $k$-te variabel. 1-konsistens er nodekonsistens, 2-konsistens er buekonsistens, og 3-konsistens er stikonsistens for binære problemer. Et problem er sterkt $k$-konsistent når det er $k$-konsistent, $(k-1)$-konsistent og så videre ned til 1. Er et problem med $n$ variabler sterkt $n$-konsistent, kan en løsning plukkes uten et eneste tilbakesteg: velg en verdi for én variabel om gangen, og det finnes alltid en verdi som passer med de forrige. Prisen er at det å håndheve sterk $n$-konsistens i verste fall tar eksponentiell tid. I praksis nøyer man seg med bue- og av og til stikonsistens, og lar søket gjøre resten.

Globale begrensninger har ofte egne propageringsregler som er sterkere enn de binære delene. For alldiff gjelder ƒalldiff-sjekken: har $m$ variabler i omfanget til sammen bare $n<m$ ulike verdier, er begrensningen inkonsistent. Fem foredrag som må ha hver sin av fire saler, kan aldri fordeles, selv om AC-3 på de binære ulikhetene ikke fjerner én eneste verdi. Telleregelen blir sterkere med en opprydding som gjentas: en variabel med én verdi igjen er avgjort, så verdien strykes hos de andre i omfanget. Ender det med et tomt domene, eller slår telleregelen til, finnes ingen løsning.

Tabellen viser et latinsk kvadrat på 3 × 3, der hver rad og hver kolonne er en alldiff over tallene 1–3. Bare to ruter er gitt. Første runde stryker de gitte tallene fra samme rad og kolonne, og to ruter står da igjen med én verdi. Hver slik rute stryker sin verdi videre, og etter noen runder har alle ruter én verdi. Her løser propageringen hele kvadratet, men det er ikke regelen: med færre gitte tall eller større kvadrater må søket overta.

For store tallområder er det upraktisk å liste alle verdiene. Grensepropagering (bounds propagation) representerer domenet som et intervall $[\text{min},\text{maks}]$ og propagerer bare grensene gjennom begrensninger som summer og ulikheter.