CSP II: backtracking og lokalt søk

Et CSP kan løses som et vanlig søkeproblem: starttilstanden er den tomme tilordningen, en handling gir en ikke-tilordnet variabel en verdi, og målet er en komplett, konsistent tilordning. Gjort naivt blir treet enormt. På første nivå kan hvilken som helst av de $n$ variablene få hvilken som helst av de $d$ verdiene, så forgreningen er $n\cdot d$, deretter $(n-1)\cdot d$ og så videre. Treet får $n!d^n$ blader, selv om det bare finnes $d^n$ ulike komplette tilordninger.

Nøkkelen er kommutativitet (commutativity): rekkefølgen tilordningene gjøres i, endrer ikke resultatet. $A=2$ og så $L=1$ gir samme tilordning som $L=1$ og så $A=2$. Det holder derfor å velge én variabel på hvert nivå og forgrene bare på verdiene. Da får treet $d^n$ blader i stedet for $n!d^n$, se ƒantall blader i søketreet.

Algoritmen backtracking-søk (backtracking search) er dybde-først-søk i dette treet. Den velger en variabel, prøver verdiene i tur og orden og går videre med den første som ikke bryter en begrensning mot variablene som alt er tilordnet. Går en variabel tom for verdier, trekkes forrige tilordning tilbake, og forrige variabel prøver sin neste verdi. Det er et tilbakesteg. Søket lagrer bare én delvis tilordning om gangen, så minnet er lineært i $n$. Algoritmen er fullstendig: finnes en løsning, finner den den, og finnes ingen, slår den fast det etter å ha prøvd hele treet. Verken MRV, LCV eller propageringen senere i kapitlet endrer det. De endrer bare hvor raskt svaret kommer.

1tilbakespor(tilordning, domener):2    hvis alle variabler har en verdi:3        returner tilordning4    x = velg_variabel(tilordning, domener)        # fast, MRV, MRV + grad5    for v i ordne_verdier(x, tilordning, domener): # fast eller LCV6        hvis v passer med alle tilordnede naboer:7            legg til x = v8            nye = utled(x, v, domener)              # ingenting, FC eller MAC9            hvis ingen domener i nye er tomme:10                svar = tilbakespor(tilordning, nye)11                hvis svar ikke er feil:12                    returner svar13            fjern x = v                             # prøv neste verdi14    returner feil                                   # tilbake til forrige valg

Figuren bruker eksamensplanen fra kapittel 9, med fast variabelrekkefølge og dagene i stigende rekkefølge.

Planen viser svakheten ved fast rekkefølge. Databaser får dag 1 uten at søket ser på Etikk, og først når Etikk skal tilordnes, viser det seg at ingen dag kommer før dag 1. Feilen ble gjort ett nivå opp, men oppdages ett nivå ned. I større problemer kan avstanden være mange nivåer, og søket kan bruke lang tid på å prøve alt under en tilordning som var dømt fra starten.

To ord holdes fra hverandre i resten av kapitlet. En verdi som bryter en begrensning mot en tilordnet nabo, forkastes på stedet og blir aldri tilordnet. Et tilbakesteg skjer først når en variabel har prøvd alle verdiene sine, og en tidligere tilordning må trekkes tilbake. Eksamensoppgaver som spør etter antall tilbakesteg, teller det siste.

Hvilken variabel bør søket ta først? MRV-heuristikken (minimum remaining values) velger variabelen med færrest lovlige verdier igjen, altså verdier som ikke bryter en begrensning mot de tilordnede variablene. ƒMRV-valget:

Tanken er at en variabel med få verdier er den som mest sannsynlig feiler. Har den null verdier, oppdages blindveien med en gang, i stedet for etter at søket har brukt tid på resten av treet. Det kalles feil først (fail-first).

MRV gir ofte likhet, særlig i starten, når alle domenene er like store. Da brukes gradheuristikken (degree heuristic): velg variabelen med flest begrensninger mot variabler som ikke er tilordnet ennå. Den legger tunge avgjørelser tidlig og krymper flest domener for resten av søket. Står det fortsatt likt, avgjør en fast regel, som standard laveste indeks, altså den som står først i variabellista.

MRV må regnes ut på nytt etter hver tilordning, fordi de lovlige verdiene til en variabel endrer seg hver gang en nabo får verdi. Uten inferens betyr det å sjekke hver verdi mot de tilordnede naboene. Med fremoversjekking fra steg 4 står svaret allerede i domenene.

Samme eksamensplan, nå med MRV og gradheuristikken som første tie-break.

Planen ble løst uten ett eneste tilbakesteg, og gradheuristikken avgjorde i tredje valg. Databaser og Etikk hadde da begge to lovlige dager. Etikk har to ikke-tilordnede naboer, Databaser bare én, så Etikk ble valgt. Med laveste indeks i stedet hadde Databaser fått dag 2, og Etikk hadde stått uten dag før dag 2, med et tilbakesteg som følge.

Når variabelen er valgt, gjenstår rekkefølgen på verdiene. Her snur logikken: heuristikken minst begrensende verdi (least constraining value, LCV) prøver først verdien som fjerner færrest lovlige verdier hos de ikke-tilordnede naboene. Ved likhet går laveste verdi først.

Tenk på hvordan du pakker en bil før ferien. Den store kjølebagen skal med uansett, så den legger du inn først, mens det fortsatt er plass å flytte på. Men når du velger hvor den skal stå, tar du plassen som sperrer minst for resten av bagasjen. Det er feil først og feil sist (fail-first, fail-last): variabelvalget avgjør bare når en variabel får verdi, ikke om, så den vanskeligste bør tas mens treet er grunt og en blindvei er billig å oppdage. Verdivalget avgjør derimot hvilken gren vi går ned i, og vi trenger bare én gren som holder hele veien, så vi begynner med den som har best sjanse. Skal vi finne alle løsningene, eller har problemet ingen, må hver verdi prøves uansett, og da spiller verdirekkefølgen ingen rolle.

LCV teller verdier som forsvinner hos naboene, ikke egne verdier. En verdi som tømmer et nabodomene, havner sist, fordi den fjerner alt naboen hadde.

LCV koster noe å regne ut: for hver kandidatverdi må søket sjekke alle naboene. I store problemer brukes den derfor sammen med fremoversjekking, som uansett regner ut hvilke verdier som forsvinner.

MRV og LCV bestemmer rekkefølgen, men ser ikke etter hva en tilordning ødelegger. Det gjør fremoversjekking (forward checking, FC): etter hver tilordning $X=v$ fjernes alle verdier hos de ikke-tilordnede naboene til $X$ som er inkonsistente med $v$. Blir et nabodomene tomt, forkastes $v$ med en gang, og søket prøver neste verdi uten å gå dypere.

FC ser bare én kant ut fra variabelen som nettopp ble tilordnet. Den sjekker ikke begrensninger mellom to variabler som begge er ikke-tilordnet, selv om domenene deres har krympet. FC passer godt sammen med MRV: domenene etter FC er nettopp de lovlige verdiene MRV trenger, så telling blir gratis.

På eksamen skrives FC som en domenetabell: én rad per tilordning, med alle domener etter at FC er ferdig. En verdi som tømmer et domene, får en egen rad med det tomme domenet markert, og raden etter viser at søket prøver neste verdi eller går tilbake.

Seks bydeler i en tenkt by skal fargelegges med rødt, grønt og blått, og naboer skal ha ulik farge. Fjellet kan ikke være rødt, fordi rødt er brukt på kommunegrensen der.

Tømmingen skjer i femte tilordning. Etter $M=\text{grønn}$ har både Torget og Vika bare blått igjen, og de er naboer. FC ser ikke det, fordi ingen av dem er tilordnet. Først når Torget får blått, blir Vika tom, og søket må tilbake til Moen.

Koden under løser n-dronningproblemet med 14 dronninger, én variabel per kolonne og radene som verdier. Du kan slå MRV og FC av og på.

bruk_mrv = 0  # @param 0..1
bruk_fc = 0  # @param 0..1

n = 14  # variabel = kolonne, verdi = rad
forsok = tilbake = 0


def kolliderer(k1, r1, k2, r2):
    return r1 == r2 or abs(r1 - r2) == abs(k1 - k2)


def los(tilordning, domener):
    global forsok, tilbake
    if len(tilordning) == n:
        return tilordning
    ledige = [k for k in range(n) if k not in tilordning]
    lovlige = {k: [r for r in domener[k] if not any(kolliderer(k, r, j, s) for j, s in tilordning.items())]
               for k in ledige}
    k = min(ledige, key=lambda j: len(lovlige[j])) if bruk_mrv else ledige[0]
    for r in lovlige[k]:
        forsok += 1
        nye = domener
        if bruk_fc:  # fjern verdier hos de ledige som kolliderer med k = r
            nye = {j: [s for s in domener[j] if not kolliderer(k, r, j, s)] for j in ledige if j != k}
            if any(not d for d in nye.values()):
                continue  # et domene ble tomt: forkast verdien
        svar = los({**tilordning, k: r}, nye)
        if svar:
            return svar
    tilbake += 1  # k gikk tom: tilbake til forrige variabel
    return None


svar = los({}, {k: list(range(1, n + 1)) for k in range(n)})
print(f"Løsning: {', '.join(str(svar[k]) for k in range(n))}" if svar else "Løsning: ingen")
print(f"Tilordninger forsøkt: {forsok}")
print(f"Tilbakesteg: {tilbake}")

FC stopper etter ett ledd. Har to ikke-tilordnede naboer begge bare verdien 2 igjen og en ulikhet mellom seg, er saken avgjort, men FC merker det ikke. MAC (maintaining arc consistency) går lenger: etter tilordningen $X=v$ kjøres AC-3 med en startkø som inneholder buene $(X_j,X)$ for hver ikke-tilordnet nabo $X_j$. Krymper et domene, legges nye buer til som i kapittel 9, så propageringen brer seg så langt den rekker.

MAC fjerner alt FC fjerner, og ofte mer. Prisen er mer arbeid per tilordning. I de fleste problemer lønner det seg, fordi hver blindvei som oppdages et nivå tidligere, sparer et helt deltre.

MAC henger tett sammen med AC-3 fra kapittel 9. Kjør AC-3 på hele problemet før søket starter, og kjør den så igjen, med den korte startkøen, etter hver tilordning. En tilordning er bare en unær begrensning, $X=v$, som krymper ett domene til én verdi, og propageringen derfra er nøyaktig den samme som før.

Backtracking bygger en løsning bit for bit. Algoritmen min-conflicts starter i motsatt ende: med en komplett tilordning, gjerne full av konflikter, og reparerer den. I hvert steg velges en tilfeldig variabel som er i konflikt, og den får verdien som gir færrest konflikter med de andre, ƒmin-conflicts-trekket:

Ved likhet trekkes en av de beste verdiene tilfeldig. Det er lokalt søk fra kapittel 4, med antall brutte begrensninger som kostnaden som skal ned til null.

For n-dronninger er metoden overraskende god. Fra en tilfeldig start løser den problemet med en million dronninger på rundt 50 steg i snitt, fordi løsningene ligger tett i tilstandsrommet. Den egner seg også når et problem endres litt, for eksempel når et fly blir forsinket og en rutetabell må repareres: start fra den gamle løsningen og fiks konfliktene, i stedet for å bygge alt på nytt. Svakheten er platåer der mange tilordninger har like mange konflikter, og problemer der løsningene er få og spredt. Da kan søket vandre lenge uten å finne fram, og det kan aldri bevise at en løsning ikke finnes.

Tabellen bruker en fast regel i stedet for tilfeldige trekk, så stegene kan regnes for hånd: dronningen lengst til venstre som er i konflikt, flyttes, og ved lik konflikt går den til laveste rad. I tabellen faller antall konfliktpar i hvert steg, men det er ikke garantert generelt. Et trekk kan like gjerne gi samme antall, og ofte trengs slike sidelengs trekk for å komme seg over et platå. To tiltak hjelper i vanskelige problemer: en kort liste med nylig besøkte tilordninger som ikke får besøkes igjen, og vekter på begrensninger som brytes ofte, så søket prioriterer dem.

Koden under kjører min-conflicts på $n$ dronninger fra en tilfeldig start med fast frø.

import random

random.seed(4)
n = 8  # @param 4..40
maks_steg = 100  # @param 10..1000

rad = [random.randrange(n) for _ in range(n)]  # tilfeldig start: rad[k] i kolonne k


def konflikter(k, r):
    return sum(1 for j in range(n) if j != k and (rad[j] == r or abs(rad[j] - r) == abs(j - k)))


lost_etter = None
for steg in range(maks_steg + 1):
    i_konflikt = [k for k in range(n) if konflikter(k, rad[k]) > 0]
    if not i_konflikt:
        lost_etter = steg
        break
    if steg == maks_steg:
        break
    k = random.choice(i_konflikt)  # tilfeldig variabel i konflikt
    tall = [konflikter(k, r) for r in range(n)]
    rad[k] = random.choice([r for r in range(n) if tall[r] == min(tall)])  # likhet: tilfeldig

par = sum(1 for a in range(n) for b in range(a + 1, n) if rad[a] == rad[b] or abs(rad[a] - rad[b]) == b - a)
print(f"Løst etter steg: {lost_etter}" if lost_etter is not None else f"Løst etter steg: ikke løst innen {maks_steg} steg")
print(f"Konflikter igjen: {par}")

Sammenlign med backtracking-koden i steg 4. Der trengte 14 dronninger 1899 tilordninger uten MRV og 124 med, mens min-conflicts bruker omtrent like mange steg på 40 dronninger som på 20. Forskjellen kommer av hvor løsningene ligger. Systematisk søk må lete seg fram gren for gren, mens lokalt søk hopper rett inn blant fullstendige tilordninger, og der ligger det mange løsninger nær hverandre.