Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra CSP I: formulering og konsistens, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Et problem gitt ved variabler , domener og begrensninger , der målet er en tilordning som er både komplett og konsistent. Forkortes CSP (constraint satisfaction problem).
Mengden verdier en variabel kan få, for eksempel dagene for en eksamen (domain).
En regel med et omfang (variablene den gjelder) og en relasjon (hvilke kombinasjoner av verdier som er lov), for eksempel (constraint).
Verdier gitt til noen eller alle variablene. Den er konsistent når ingen begrensning brytes, og komplett når alle variablene har en verdi; en løsning er begge deler (assignment).
En graf med én node per variabel og en urettet kant mellom to variabler som deler en begrensning. Kanten er urettet også for ulikheter som (constraint graph).
En begrensning på én variabel, som . Den gir ingen kant i grafen, men krymper domenet direkte (unary constraint).
En begrensning mellom to variabler, som eller . Den blir én kant i begrensningsgrafen (binary constraint).
En begrensning som gjelder vilkårlig mange variabler, for eksempel Alldiff. Den har ofte en egen propageringsregel som er sterkere enn de binære delene (global constraint).
Den globale begrensningen som krever at alle variablene i omfanget får ulike verdier. Den kan skrives om til én binær ulikhet for hvert par av variabler (Alldiff).
En ny variabel som gjør en begrensning på tre eller flere variabler binær. Domenet er de lovlige kombinasjonene, og hver opprinnelig variabel knyttes til sin komponent (auxiliary variable).
En regel som sier hva som er ønsket, ikke hva som må holde. Den kan brytes mot en kostnad og gjør problemet til et optimeringsproblem (preference constraint).
En variabel er nodekonsistent når alle verdiene i domenet oppfyller de unære begrensningene. Den sjekkes først, og etterpå kan de unære begrensningene strykes (node consistency).
er buekonsistent mot når hver verdi i har minst én støtte i som oppfyller begrensningen mellom dem. Et problem er buekonsistent når alle buene er det (arc consistency).
Paret er stikonsistent mot når hver konsistent tilordning av og kan utvides med en verdi for som passer med begge (path consistency).
Hver konsistent tilordning av variabler kan utvides med en verdi for en hvilken som helst -te variabel. Sterkt -konsistent betyr at en løsning kan velges uten tilbakesteg (k-consistency).
Propagering der et stort tallområde representeres som et intervall, og bare grensene oppdateres gjennom begrensninger som summer og ulikheter (bounds propagation).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
CSP-trippel
Hver formulering starter her: list variablene , gi domenet til hver variabel i , og skriv alle begrensningene i . Vanlig feil er å utelate begrensninger som virker selvsagte, for da finnes de ikke for algoritmen.
Kravet om buekonsistens
Det REVISE håndhever: hver verdi i trenger en støtte i . Kravet har retning, så og er to ulike buer, og REVISE endrer bare .
Kjøretiden til AC-3
Med kanter (par av variabler med minst én begrensning) er det buer. En bue legges tilbake bare når domenet den peker mot, krymper, høyst ganger, og hver REVISE koster . Polynomisk, i motsetning til søket.
Alldiff-sjekken
Har variabler i en alldiff til sammen bare ulike verdier og , finnes ingen løsning. AC-3 på de binære ulikhetene oppdager det ofte ikke: har hver variabel minst to verdier, har hver verdi støtte langs hver kant.
Antall komplette tilordninger
Med variabler og verdier hver finnes komplette tilordninger. Har domenene ulik størrelse, er antallet produktet av domenestørrelsene.
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
AC-3 på eksamensplanen
maks_verdi = 3 # @param 2..6 # Eksamensplanen: A, D, E, L, P får en dag fra 1 til maks_verdiD = {x: set(range(1, maks_verdi + 1)) for x in "ADELP"}D["A"].discard(1) # nodekonsistens: A ≠ 1regler = {("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, alfabetiskkall, konsistent = 0, Truewhile 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 variabelprint(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'}")Prøv: sett maks_verdi til 2 og se at linja Konsistent: blir nei fordi Domene L: blir tom, og sett den så til 4 og se hvilken dag som forsvinner fra Domene E: og Domene D:.
Pseudokode
Pseudokode som forklarer fremgangsmåten steg for steg.
AC-3 i pseudokode
ac3(domener, buer): kø = alle buer (xi, xj) i begge retninger, sortert alfabetisk så lenge kø ikke er tom: (xi, xj) = ta ut første bue i kø hvis revider(xi, xj, domener): # D[xi] krympet hvis D[xi] er tom: returner inkonsistent for hver nabo xk av xi med xk ≠ xj, alfabetisk: hvis (xk, xi) ikke står i kø: legg (xk, xi) bakerst i kø returner domener revider(xi, xj, domener): endret = usann for hver verdi x i D[xi]: hvis ingen y i D[xj] passer med x: # x mangler støtte fjern x fra D[xi] endret = sann returner endretAC-3 er en kø av buer. Når et domene krymper, legges buene fra de andre naboene inn igjen, aldri buen som nettopp ble brukt.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Formaliser et begrensningsproblem som med alle begrensningene, også de som virker selvsagte
- 02Klassifiser begrensninger som unære, binære eller globale, og lag begrensningsgrafen
- 03Spor AC-3 i en tabell med kø, bue og domene før og etter, og oppgi sluttdomenene
- 04Regn ut antall buer i startkøen, antall komplette tilordninger og hvor mange verdier propageringen fjerner
- 05Forklar hvorfor buekonsistens ikke garanterer en løsning, og hva sti- og k-konsistens tilfører
- 06Bruk alldiff-sjekken og grensepropagering til å finne inkonsistens som AC-3 på binære ulikheter ikke ser