Lokal konsistens - Local consistency

Når det gjelder begrensningstilfredshet , er lokale konsistensbetingelser egenskaper for problemer med begrensningstilfredshet relatert til konsistensen av undergrupper av variabler eller begrensninger. De kan brukes til å redusere søkeområdet og gjøre problemet enklere å løse. Ulike typer lokale konsistensforhold utnyttes, inkludert nodekonsistens , lysbue-konsistens og banekonsistens .

Hver lokal konsistensbetingelse kan håndheves ved en transformasjon som endrer problemet uten å endre løsningene. En slik transformasjon kalles begrensningsutbredelse . Begrensningsutbredelse fungerer ved å redusere domener til variabler, styrke begrensninger eller lage nye. Dette fører til en reduksjon av søkeområdet, noe som gjør problemet lettere å løse med noen algoritmer. Begrensningsutbredelse kan også brukes som en usikkerhetskontroll, ufullstendig generelt, men fullstendig i noen spesielle tilfeller.

Lokale konsistensforhold kan grupperes i forskjellige klasser. De opprinnelige lokale konsistensbetingelsene krever at hvert konsistent oppdrag konsekvent kan utvides til en annen variabel. Retningskonsistens krever bare at denne betingelsen er oppfylt når den andre variabelen er høyere enn dem i oppgaven, i henhold til en gitt rekkefølge. Relasjonell konsistens inkluderer utvidelser til mer enn en variabel, men denne utvidelsen er bare nødvendig for å tilfredsstille en gitt begrensning eller sett med begrensninger.

Antagelser

I denne artikkelen er et begrensningstilfredshetsproblem definert som et sett med variabler, et sett med domener og et sett med begrensninger. Variabler og domener er tilknyttet: domenet til en variabel inneholder alle verdier variabelen kan ta. En begrensning er sammensatt av en rekke variabler, kalt dens omfang, og et sett av deres evalueringer, som er evalueringene som tilfredsstiller begrensningen.

De begrensningstilfredshetsproblemer som er referert til i denne artikkelen antas å være i en spesiell form. Et problem er i normalisert form , henholdsvis vanlig form , hvis hver sekvens med variabler er omfanget av høyst en begrensning eller nøyaktig en begrensning. Forutsetningen om regularitet som bare gjøres for binære begrensninger, fører til den standardiserte formen . Disse forholdene kan alltid håndheves ved å kombinere alle begrensninger over en sekvens med variabler til en enkelt og / eller legge til en begrensning som er tilfredsstilt av alle verdiene i en sekvens med variabler.

I figurene som er brukt i denne artikkelen indikerer mangelen på koblinger mellom to variabler at det enten ikke eksisterer noen begrensning eller en begrensning som er tilfredsstilt av alle verdier mellom disse to variablene.

Lokal konsistens

De "standard" lokale konsistensbetingelsene krever alle at alle konsistente delevalueringer kan utvides til en annen variabel på en slik måte at den resulterende tildelingen er konsistent. En delvis evaluering er konsistent hvis den tilfredsstiller alle begrensninger hvis omfang er en undergruppe av de tildelte variablene.

Knutepunktkonsistens

Knutepunktkonsistens krever at hver unary begrensning på en variabel tilfredsstilles av alle verdier i variabeldomenet, og omvendt. Denne betingelsen kan håndheves trivielt ved å redusere domenet til hver variabel til verdiene som tilfredsstiller alle unære begrensninger på den variabelen. Som et resultat kan unære begrensninger forsømmes og antas innlemmet i domenene.

For eksempel, gitt en variabel med et domene på og en begrensning , vil nodekonsistensen begrense domenet til og begrensningen kan deretter kastes. Dette forbehandlingstrinnet forenkler senere stadier. ${\ displaystyle V}$${\ displaystyle \ left \ {1,2,3,4 \ right \}}$${\ displaystyle V \ leq 3}$${\ displaystyle \ left \ {1,2,3 \ right \}}$

Bue konsistens

x2 er bue-konsistent med x3, men ikke med x1, da verdien x2 = 1 ikke tilsvarer noen verdi for x1.

En variabel av et begrensningstilfredshetsproblem er bue-konsistent med en annen hvis hver av dens tillatte verdier er konsistent med en eller annen tillatelig verdi av den andre variabelen. Formelt sett er en variabel lysbue-konsistent med en annen variabel hvis det for hver verdi i domenet til finnes en verdi i domenet til slike som tilfredsstiller den binære begrensningen mellom og . Et problem er lysbue konsistent hvis hver variabel er i samsvar med alle andre. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle a}$${\ displaystyle x_ {i}}$${\ displaystyle b}$${\ displaystyle x_ {j}}$${\ displaystyle (a, b)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Vurder for eksempel begrensningen der variablene går over domenet 1 til 3. Fordi det aldri kan være 3, er det ingen bue fra 3 til en verdi i, så det er trygt å fjerne. Likeledes kan aldri bli en, så det er ingen bue, derfor kan fjernes. ${\ displaystyle x <y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$

Bue-konsistens kan også defineres i forhold til en spesifikk binær begrensning: en binær begrensning er bue-konsistent hvis hver verdi av en variabel har en verdi av den andre variabelen slik at de tilfredsstiller begrensningen. Denne definisjonen av lysbue-konsistens ligner på det ovennevnte, men gis spesifikt for en begrensning. Denne forskjellen er spesielt relevant for ikke-normaliserte problemer, der definisjonen ovenfor vil ta hensyn til alle begrensninger mellom to variabler, mens denne bare vurderer en spesifikk.

Bue konsistens håndheves ved å fjerne 1 som en verdi for x2. Som et resultat er x3 ikke lenger bue-konsistent med x2 fordi x3 = 2 ikke tilsvarer en verdi for x2.

Hvis en variabel ikke stemmer overens med en annen, kan den gjøres ved å fjerne noen verdier fra domenet. Dette er formen for begrensningsutbredelse som tvinger bue-konsistens: den fjerner, fra domenet til variabelen, hver verdi som ikke tilsvarer en verdi av den andre variabelen. Denne transformasjonen opprettholder problemløsningene, ettersom de fjernede verdiene uansett ikke er noen løsning.

Begrensningsutbredelse kan gjøre hele problemstillingen bue ved å gjenta denne fjerningen for alle par av variabler. Denne prosessen må kanskje vurdere et gitt par variabler mer enn en gang. Å fjerne verdier fra domenet til en variabel kan føre til at andre variabler ikke lenger er i samsvar med det. For eksempel, hvis er buen konsekvent med , men algoritmen reduserer domene , bue konsistens med holder ikke lenger, og må håndheves igjen. ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$

En forenklet algoritme ville sykle over parene med variabler, håndheve lysbue-konsistens, gjenta syklusen til ingen domener endres for en hel syklus. Den AC-3-algoritme bedrer over denne algoritmen ved å ignorere begrensninger som ikke har blitt endret siden de sist ble analysert. Spesielt fungerer det på et sett med begrensninger som i utgangspunktet inneholder alle av dem; på hvert trinn tar det en begrensning og håndhever lysbue-konsistens; Hvis denne operasjonen kan ha gitt brudd på lysbue-konsistensen i forhold til en annen begrensning, plasserer den den tilbake i settet med begrensninger som skal analyseres. På denne måten, når lysbue-konsistens er håndhevet på en begrensning, blir denne begrensningen ikke vurdert på nytt med mindre domenet til en av dens variabler er endret.

Banekonsistens

x1 og x2 stemmer ikke overens med x3. De kan gjøres bane konsistente ved å fjerne de blå verdiene fra R12.

Banekonsistens er en egenskap som ligner på lysbue konsistens, men vurderer par variabler i stedet for bare en. Et par variabler er bane-konsistent med en tredje variabel hvis hver konsistent evaluering av paret kan utvides til den andre variabelen på en slik måte at alle binære begrensninger er oppfylt. Formelt, og er sti konsistent med hvis, for hvert par av verdier som tilfredsstiller den binære begrensnings mellom og eksisterer det en verdi i domenet av slik at og tilfredsstille begrensningen mellom og og mellom og hhv. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$${\ displaystyle (a, b)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle c}$${\ displaystyle x_ {k}}$${\ displaystyle (a, c)}$${\ displaystyle (b, c)}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$

Formen av begrensningsutbredelse som håndhever banekonsistens fungerer ved å fjerne en tilfredsstillende oppgave fra en begrensning. Faktisk kan banekonsistens håndheves ved å fjerne alle evalueringer som ikke kan utvides til en annen variabel fra en binær begrensning. Når det gjelder lysbue-konsistens, kan det hende at denne fjerningen må vurdere en binær begrensning mer enn en gang. Når det gjelder lysbue-konsistens, har det resulterende problemet de samme løsningene som den opprinnelige, ettersom de fjernede verdiene ikke er i noen løsning.

To variabler som ikke er i en begrensning, kan betraktes som relatert av en virtuell begrensning som tillater ethvert mulig parverdier, representert av de blå kantene i denne figuren.

Å håndheve banekonsistensen av x1 og x2 med x3 fjerner kanten på toppen. Verdiene til x1 og x2 er ikke lenger gratis, men relatert til en ny faktisk begrensning.

Formen av begrensningsutbredelse som håndhever banekonsistens kan føre til nye begrensninger. Når to variabler ikke er relatert av en binær begrensning, er de praktisk talt relatert av begrensningen slik at et hvilket som helst par verdier. Imidlertid kan noen par verdier fjernes ved begrensningsutbredelse. Den resulterende begrensningen blir ikke lenger tilfredsstilt av alle verdipar. Derfor er det ikke lenger en virtuell, triviell begrensning.

Navnet "banekonsistens" stammer fra den opprinnelige definisjonen, som involverte et par variabler og en bane mellom dem, i stedet for et par og en enkelt variabel. Mens de to definisjonene er forskjellige for et enkelt par variabler, er de likeverdige når det refereres til hele problemet.

generaliseringer

Bue- og banekonsistens kan generaliseres til ikke-binære begrensninger ved bruk av tupler av variabler i stedet for en enkelt eller et par. En tippel med variabler er i samsvar med en annen variabel hvis hver konsistent evaluering av variablene kan utvides med en verdi av den andre variabelen mens konserveringen bevares. Denne definisjonen strekker seg til hele problemer på den åpenbare måten. Sterk- konsistens er -konsistens for alle . ${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle j \ leq i}$

Det spesielle tilfellet med 2-konsistens sammenfaller med lysbue-konsistens (alle problemer antas node-konsistente i denne artikkelen). På den annen side sammenfaller 3-konsistens med banekonsistens bare hvis alle begrensninger er binære, fordi banekonsistens ikke innebærer ternære begrensninger mens 3-konsistens gjør det.

En annen måte å generalisere lysbue-konsistens er hyperbue-konsistens eller generalisert lysbue-konsistens , som krever utvidbarhet av en enkelt variabel for å tilfredsstille en begrensning. Nemlig er en variabel hyperbue konsistent med en begrensning hvis hver verdi av variabelen kan utvides til de andre variablene i begrensningen på en slik måte at begrensningen er oppfylt.

Konsistens og tilfredshet

Denne forekomsten er bue konsistent og inneholder ikke noe tomt domene, men har ingen løsning. De blå linjene indikerer oppdrag tvunget av valget x1 = 1.

Begrensningsutbredelse (håndheve en form for lokal konsistens) kan gi et tomt domene eller en utilfredsstillende begrensning. I dette tilfellet har problemet ingen løsning. Konversasjonen er ikke sant generelt: et inkonsekvent forekomst kan være bue-konsistent eller sti-konsistent mens det ikke har noe tomt domene eller utilfredsstillende begrensning.

Lokal konsistens er faktisk bare i forhold til konsistensen av grupper med variabler. For eksempel garanterer lysbue-konsistens at hver konsistent evaluering av en variabel kan utvides til en annen variabel. Når en enkelt verdi av en variabel utvides til å omfatte to andre variabler, er det imidlertid ingen garanti for at disse to verdiene er i samsvar med hverandre. For eksempel kan være i samsvar med og med , men disse to evalueringene er kanskje ikke i samsvar med hverandre. ${\ displaystyle x_ {1} = 1}$${\ displaystyle x_ {2} = 1}$${\ displaystyle x_ {3} = 1}$

Imidlertid kan utbredelse av begrensninger brukes til å bevise tilfredshet i noen tilfeller. Et sett med binære begrensninger som er bue-konsistente og ikke har noe tomt domene, kan være inkonsekvent bare hvis nettverket av begrensninger inneholder sykluser. Hvis begrensningene er binære og danner en acyklisk graf, kan verdier alltid forplantes på tvers av begrensninger: for hver verdi av en variabel har alle variabler i en begrensning en verdi som tilfredsstiller den begrensningen. Som et resultat kan en løsning bli funnet ved iterativt å velge en ikke tilordnet variabel og rekursivt forplante seg på tvers av begrensninger. Denne algoritmen prøver aldri å tilordne en verdi til en variabel som allerede er tilordnet, da det ville innebære eksistensen av sykluser i nettverket av begrensninger.

En lignende tilstand gjelder for banekonsistens. De spesielle tilfellene der tilfredshet kan etableres ved å håndheve lysbue konsistens og sti konsistens er følgende.

1. håndhevelse av lysbue-konsistens fastslår tilfredsstillelse av problemer laget av binære begrensninger uten sykluser (et tre av binære begrensninger);
2. håndhevelse av banekonsistens etablerer tilfredshet for binære begrensninger (muligens med sykluser) med binære domener;
3. Å håndheve sterk konsistens fastslår tilfredshet med problemer som inneholder variabler.${\ displaystyle n}$${\ displaystyle n}$

Spesielle tilfeller

Noen definisjoner eller resultater om relativ konsistens gjelder bare i spesielle tilfeller.

Når domenene er sammensatt av heltall , kan bundet konsistens defineres. Denne formen for konsistens er basert på konsistensen av de ekstreme verdiene til domenene, det vil si minimums- og maksimumsverdiene en variabel kan ta.

Når begrensninger er algebraiske eller boolske , tilsvarer lysbue konsistens til å legge til ny begrensning eller syntaktisk endre en gammel, og dette kan gjøres ved å komponere begrensninger på passende måte.

Spesialiserte begrensninger

Noen typer begrensninger brukes ofte. For eksempel brukes ofte begrensningen for at noen variabler er forskjellige. Effektive spesialiserte algoritmer for å håndheve lysbue-konsistens på slike begrensninger eksisterer.

Begrensningen for å håndheve et antall variabler for å være forskjellig er vanligvis skrevet eller . Denne begrensningen tilsvarer ikke-likheten for alle par av forskjellige variabler, det vil si for hver . Når domenet til en variabel reduseres til en enkelt verdi, kan denne verdien fjernes fra alle andre domener ved å begrense forplantning når du håndhever lysbue-konsistens. Bruken av den spesialiserte begrensningen gir mulighet for å utnytte egenskaper som ikke holder for individuelle binære ulikheter . ${\ displaystyle \ mathop {\ rm {alldifferent}} (x_ {1}, \ ldots, x_ {n})}$alldifferent([X1,...,Xn])${\ displaystyle x_ {i} \ not = x_ {j}}$${\ displaystyle i \ not = j}$

En første egenskap er at det totale antallet elementer i domenene til alle variabler må være minst antall variabler. Mer presist, etter at lysbue-konsistensen er håndhevet, må antallet ikke tildelte variabler ikke overstige antall verdier i foreningen av deres domener. Ellers kan ikke begrensningen tilfredsstilles. Denne tilstanden kan lett sjekkes på en begrensning i alldifferentformen, men tilsvarer ikke bue-konsistensen i ulikhetsnettverket. En annen egenskap ved den eneste alldifferentbegrensningen er at hyperbue-konsistens kan kontrolleres effektivt ved bruk av en bipartitt matching- algoritme. Spesielt er en graf bygget med variabler og verdier som de to settene med noder, og en spesialisert bipartitt-samsvarende algoritme kjøres på den for å sjekke eksistensen av en slik matching.

En annen type begrensning som ofte brukes, er den cumulative. Det ble introdusert for problemer med planlegging og plassering. Som et eksempel cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L)kan brukes til å formalisere tilstanden der det er maktiviteter, hver med starttid si, varighet diog bruk riav en ressursmengde. Begrensningen sier at den totale tilgjengelige mengden ressurser er L. Spesialiserte forplantningsteknikker for kumulative begrensninger eksisterer; forskjellige teknikker brukes avhengig av hvilke variable domener som allerede er redusert til en enkelt verdi.

En tredje spesialisert begrensning som brukes i programmering av begrensningslogikk er den element. I begrensningslogikk-programmering er lister tillatt som verdier av variabler. En begrensning element(I, L, X)er tilfreds hvis Ler en liste og Xer det-det Ielementet i denne listen. Spesialiserte regler for forplantning av begrensninger for disse begrensningene finnes. Som et eksempel, hvis Log Ier redusert til et domene med en verdi, kan en unik verdi Xbestemmes. Mer generelt Xkan man utlede umulige verdier fra domenet til og omvendt. ${\ displaystyle I}$

Retningskonsistens

Retningskonsistens er varianten av lysbue, bane og -konsistens som er skreddersydd for å brukes av en algoritme som tildeler verdier til variabler etter en gitt rekkefølge av variabler. De ligner på de ikke-retningsbestemte kollegene, men krever bare at en konsekvent tilordning til noen variabler konsekvent kan utvides til en annen variabel som er større enn dem i henhold til rekkefølgen. ${\ displaystyle i}$

Retningsbue og banekonsistens

En forekomst som er retningsbestemt bue konsistent i henhold til rekkefølgen x1 x2 x3, men ikke bue-konsistent (ingen begrensning er til stede mellom x1 og x3; tilsvarende kanter utelatt). Hver verdi av en lavere indeksvariabel tilsvarer verdiene for høyere indeksvariabler. Spørsmålstegn indikerer punkter der samtalen ikke holder.

Hvis en algoritme evaluerer variabler i rekkefølgen , er konsistens bare nyttig når den garanterer at verdier av lavere indeksvariabler alle er i samsvar med verdier for høyere indeksverdier. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

Når du velger en verdi for en variabel, kan verdier som er uforenlige med alle verdiene til en ikke tilordnet variabel, forsømmes. Selv om disse verdiene samsvarer med den nåværende delevalueringen, vil algoritmen senere ikke finne en konsistent verdi for den ikke tildelte variabelen. På den annen side er det ikke nødvendig å håndheve konsistens med variabler som allerede er evaluert: hvis algoritmen velger en verdi som er uoverensstemmende med den nåværende delevalueringen, oppdages uoverensstemmelse uansett.

Forutsatt at rekkefølgen av evaluering av variablene er , er et begrensningstilfredshetsproblem retningsvis bue konsistent hvis hver variabel er bue konsistent med noen annen variabel slik . Retningslinjens konsistens er lik, men to variabler må være banekonsekvente med bare hvis . Sterk retningskonsistens betyr både retningsbestemt banekonsistens og retningsbestemt bue-konsistens. Lignende definisjoner kan gis for de andre formene for konsistens. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle i <j}$${\ displaystyle x_ {i}, x_ {j}}$${\ displaystyle x_ {z}}$${\ displaystyle i, j <z}$

Begrensningsutbredelse for bue- og banekonsistens

Begrensningsutbredelse som tvinger retningsbestemt bue-konsistens itererer over variabler fra den siste til den første, og på hvert trinn håndheves bue-konsistensen til hver variabel med lavere indeks med den. Hvis rekkefølgen på variablene er , itererer denne algoritmen over variabler fra til ; for variabel tvinger den buekonsistensen til hver indeksvariabel lavere enn med . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle x_ {n}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {j}}$${\ displaystyle j}$${\ displaystyle x_ {j}}$

En forekomst som ikke er retningsbuen konsistent: tilsvarer ikke noen verdi av og tilsvarer ikke noen verdi av . Det er ingen begrensning mellom og (tilsvarende kanter er utelatt). ${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {3}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {3}}$	Å håndheve retningsbestemt bue-konsistens starter med , og gjør buen konsistent med den ved å fjerne verdien . ${\ displaystyle x_ {3}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$	Å håndheve retningsbue-konsistensen fortsetter med . Siden har allerede fjernet, både og fjernes. ${\ displaystyle x_ {2}}$${\ displaystyle x_ {2} = 3}$${\ displaystyle x_ {1} = 2}$${\ displaystyle x_ {1} = 3}$

Retningslinjekonsistens og sterk retningsveikonsistens kan håndheves med algoritmer som ligner den for bue-konsistens. De behandler variabler fra til ; for hver variabel to variabler med blir vurdert, og banekonsistensen av dem med blir håndhevet. Ingen drift er nødvendig hvis problemet ikke inneholder noen begrensning og eller ingen begrensning mellom og . Selv om det ikke er noen begrensning mellom og , antas det imidlertid en bagatellmessig. Hvis begrensningsutbredelse reduserer settet med tilfredsstillende oppdrag, skaper det effektivt en ny ikke-triviell begrensning. Begrensningsutbredelse som styrker sterk retningskonsekvens er lik, men tvinger også lysbue-konsistens. ${\ displaystyle x_ {n}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}, x_ {j}}$${\ displaystyle i, j <z}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {z}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Retningskonsistens og tilfredshet

Retningskonsistens garanterer at delvise løsninger som tilfredsstiller en begrensning, konsekvent kan utvides til en annen variabel med høyere indeks. Det garanterer imidlertid ikke at utvidelsene til forskjellige variabler stemmer overens med hverandre. For eksempel kan en delvis løsning utvides konsekvent til variabel eller til variabel , men likevel er disse to utvidelsene ikke konsistente med hverandre. ${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$

Det er to tilfeller der dette ikke skjer, og retningsbestemt konsistens garanterer tilfredshet hvis ikke noe domene er tomt og ingen begrensninger er utilfredsstillende.

Det første tilfellet er det med et binært begrensningsproblem med en rekkefølge av variablene som gjør at den ordnede graden av begrensning har bredde 1. En slik bestilling eksisterer hvis og bare hvis grafen for begrensninger er et tre. Hvis dette er tilfelle, grenser grafens bredde det maksimale antallet lavere (i henhold til rekkefølge) noder en knute er koblet til. Retningsbue-konsistens garanterer at hver konsistent tildeling til en variabel kan utvides til høyere noder, og bredde 1 garanterer at en node ikke kobles til mer enn en lavere node. Som et resultat, når den lavere variabelen er tilordnet, kan dens verdi konsekvent utvides til alle høyere variabler den blir satt sammen med. Denne utvidelsen kan ikke senere føre til inkonsekvens. Ingen andre lavere variabler er faktisk knyttet til den høyere variabelen, ettersom grafen har bredde 1.

Som et resultat, hvis et begrensningsproblem har bredde 1 med hensyn til en rekkefølge av dets variabler (noe som innebærer at dets tilsvarende graf er et tre) og problemet er retningsvis bue konsistent med hensyn til den samme bestillingen, vil en løsning (hvis noen) kan bli funnet ved iterativt å tilordne variabler i henhold til bestillingen.

Det andre tilfellet der retningsbestemt konsistens garanterer tilfredshet hvis intet domene er tomt og ingen begrensning er utilfredsstillende, er det med binære begrensningsproblemer hvis graf har indusert bredde 2 ved bruk av sterk retningskonsistens. Faktisk garanterer denne formen for konsistens at hver tilordning til en variabel eller et par variabler kan utvides til en høyere variabel, og bredde 2 garanterer at denne variabelen ikke blir knyttet til et annet par med lavere variabler.

Årsaken til at den induserte bredden vurderes i stedet for bredden, er at å håndheve retningskonsekvensen kan legge til begrensninger. Hvis to variabler ikke er i samme begrensning, men har en begrensning med en høyere variabel, kan noen par av verdiene deres krenke banekonsistensen. Å fjerne slike par skaper en ny begrensning. Som et resultat kan spredning av begrensning gi et problem hvis graf har flere kanter enn den opprinnelige. Imidlertid er alle disse kantene nødvendigvis i den induserte grafen, ettersom de alle er mellom to foreldre til samme node. Bredde 2 garanterer at hver konsistent delevaluering kan utvides til en løsning, men denne bredden er i forhold til den genererte grafen. Som et resultat kreves indusert bredde som er 2 for sterk retningsveiskonsistens for å garantere eksistensen av løsninger.

Retningsbestemt i-konsistens

De blå linjene indikerer at det ikke er noen begrensning mellom x3 og x4, slik at hvert par verdier er tillatt. I disse bildene indikerer mangelen på kanter mellom to variabler implisitt mangelen på en begrensning. Dette problemet har bredde 2.

Retningskonsekvens er garantien for at hver konsistent tilordning til variabler kan utvides til en annen variabel som er høyere i rekkefølgen. Sterk retnings- konsistens er definert på en lignende måte, men alle grupper av høyst variabler blir vurdert. Hvis et problem er sterkt retningskonsistent og har bredde mindre enn og ikke har noe tomt domene eller utilfredsstillende begrensning, har det løsninger. ${\ displaystyle i}$${\ displaystyle i-1}$${\ displaystyle i}$ ${\ displaystyle i-1}$${\ displaystyle i}$${\ displaystyle i}$

Hvert problem kan gjøres sterkt retningskonsistent , men denne operasjonen kan øke bredden på de tilsvarende grafene. Prosedyren for utbredelse av begrensning som håndhever retningsbestemt konsistens, er lik den som brukes for retningsbue-konsistens og banekonsistens. Variablene blir vurdert i tur og orden, fra den siste til den første i henhold til rekkefølgen. For variabel vurderer algoritmen hver gruppe variabler som har indeks lavere enn og er i en begrensning med . Konsistensen av disse variablene med blir sjekket og muligens håndhevet ved å fjerne tilfredsstillende oppgaver fra begrensningen blant alle disse variablene (hvis noen, eller opprette en ny på annen måte). ${\ displaystyle i}$${\ displaystyle x_ {k}}$${\ displaystyle i-1}$${\ displaystyle k}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k}}$${\ displaystyle i}$

Å håndheve konsistensen på x5 fjerner den røde linjen, og skaper dermed en ny ikke-triviell begrensning mellom x3 og x4. Som et resultat har x4 x3 som ny overordnet, i tillegg til x1 og x2. Denne endringen øker bredden til 3.

Denne prosedyren genererer et sterkt retningsbestemt- konsistent eksempel. Imidlertid kan det også legge til nye begrensninger i forekomsten. Som et resultat, selv om bredden på det originale problemet er , kan bredden på det resulterende tilfellet være større. Hvis dette er tilfelle, innebærer ikke retningsbestemt konsistens tilfredshet selv om ikke noe domene er tomt og ingen begrensninger er utilfredsstillende. ${\ displaystyle i}$${\ displaystyle i}$

Imidlertid legger begrensningsutbredelse bare begrensninger til variabler som er lavere enn den den for øyeblikket vurderer. Som et resultat blir ingen begrensninger over en variabel modifisert eller lagt til når algoritmen har håndtert denne variabelen. I stedet for å vurdere et fast , kan man endre det til antall foreldre til hver betraktede variabel (foreldrene til en variabel er variablene til indeks som er lavere enn variabelen og som er i en begrensning med variabelen). Dette tilsvarer å vurdere alle foreldre til en gitt variabel på hvert trinn. Med andre ord, for hver variabel fra den siste til den første, er alle foreldrene inkludert i en ny begrensning som begrenser deres verdier til de som er i samsvar med . Siden denne algoritmen kan sees på som en modifikasjon av den forrige med en verdi som endres til antall foreldre til hver node, kalles den adaptiv konsistens . ${\ displaystyle i}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle i}$

Denne algoritmen håndhever sterkt retningsbestemt samsvar med lik den induserte bredden på problemet. Den resulterende forekomsten er tilfredsstillende hvis og bare hvis intet domene eller begrensning er gjort tomt. Hvis dette er tilfelle, kan en løsning lett bli funnet ved å iterativt sette en ikke tilordnet variabel til en vilkårlig verdi, og propagere denne delevalueringen til andre variabler. Denne algoritmen er ikke alltid polynomisk, da antallet begrensninger som innføres ved å håndheve sterk retningsbestemt konsistens kan gi en eksponentiell økning av størrelsen. Problemet er imidlertid løsbart i polynomisk tid hvis håndhevelsen av sterk retningsbestemt konsistens ikke superpolynomisk forstørrer forekomsten. Som et resultat, hvis en forekomst har indusert bredde begrenset av en konstant, kan den løses i polynomisk tid. ${\ displaystyle i}$${\ displaystyle i}$

Eliminering av bøtte

Eliminering av bøtte er en tilfredsstillende algoritme. Det kan defineres som en omformulering av adaptiv konsistens. Definisjonene bruker bøtter, som er containere for begrensning, hver variabel har en tilhørende bøtte. En begrensning hører alltid til bøtten til den høyeste variabelen.

Elimineringsalgoritmen for bøtte fortsetter fra den høyeste til den laveste variabelen etter tur. På hvert trinn vurderes begrensningene i bøttene til denne variabelen . Per definisjon involverer disse begrensningene bare variabler som er lavere enn . Algoritmen endrer begrensningen mellom disse lavere variablene (hvis noen, ellers oppretter den en ny). Spesielt tvinger det verdiene deres til å være utvidbare til konsekvent med begrensningene i bøtta til . Denne nye begrensningen, om noen, blir deretter plassert i riktig bøtte. Siden denne begrensningen bare involverer variabler som er lavere enn , legges den til en bøtte med en variabel som er lavere enn . ${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {i}}$

Denne algoritmen tilsvarer håndheving av adaptiv konsistens. Siden de begge håndhever konsistensen av en variabel med alle foreldrene, og siden det ikke legges til noen ny begrensning etter at en variabel er vurdert, er hvilke resultater et eksempel som kan løses uten tilbakesporing .

Siden grafen til forekomsten de produserer er et underbilde av den induserte grafen, hvis den induserte bredden er avgrenset av en konstant, er den genererte forekomsten av polynomstørrelse i størrelsen på den opprinnelige forekomsten. Som et resultat, hvis den induserte bredden av et eksempel er avgrenset av en konstant, kan det løses på polynomisk tid av de to algoritmene.

Relasjonell konsistens

Mens de forrige definisjonene av konsistens handler om konsistens i oppdrag, innebærer relasjonell konsistens tilfredshet med en gitt begrensning eller sett med begrensninger. Mer presist innebærer relasjonell konsistens at enhver konsistent deloppgave kan utvides på en slik måte at en gitt begrensning eller sett med begrensninger blir oppfylt. Formelt sett er en begrensning av variabler relasjonell bue-konsistent med en av dens variabler hvis hver konsistente oppgave som kan utvides til på en slik måte er oppfylt. Forskjellen mellom "vanlig" konsistens og relasjonell bue-konsistens er at sistnevnte bare krever den utvidede tildelingen for å tilfredsstille en gitt begrensning, mens den førstnevnte krever at den tilfredsstiller alle relevante begrensninger. ${\ displaystyle C}$${\ displaystyle X}$${\ displaystyle x}$${\ displaystyle X \ backslash \ {x \}}$${\ displaystyle x}$${\ displaystyle C}$${\ displaystyle i}$

(Vanlig) i-konsistens: hvis en evaluering er konsistent, kan den utvides til en annen variabel på en slik måte at alle relevante begrensninger er oppfylt.

Relasjonell bue-konsistens: hvis en evaluering av variablene til en begrensning, men en er konsistent, kan den alltid utvides til den variabelen på en slik måte at begrensningen er tilfredsstilt. Cyankantene representerer begrensninger som ikke trenger å tilfredsstilles av utvidelsen.

Denne definisjonen kan utvides til mer enn en begrensning og mer enn en variabel. Spesielt er relasjonsbanekonsistens lik relasjonell bue-konsistens, men to begrensninger brukes i stedet for en. To begrensninger er relasjonsvei som er konsistente med en variabel hvis hver konsistent tildeling til alle deres variabler, men den betraktede kan utvides på en slik måte at de to begrensningene er oppfylt.

For mer enn to begrensninger er relasjons- konsistens definert. Relasjons- konsistens innebærer et sett med begrensninger og en variabel som er innenfor rammen av alle disse begrensningene. Spesielt er disse begrensningene relasjonelle - samsvarer med variabelen hvis hver konsistente tilordning til alle andre variabler som er i deres omfang kan utvides til variabelen på en slik måte at disse begrensningene er oppfylt. Et problem er -forholdskonsekvent hvis hvert sett med begrensninger er relasjonelt - konsistent med hver variabel som er i alle omfangene. Sterk relasjonell konsistens er definert som ovenfor: det er egenskapen å være relasjonell- konsistent for alle . ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle k <m}$

Relasjonell konsistens kan også defineres for flere variabler, i stedet for en. Et sett med begrensninger er relasjonelt - konsistent hvis hver konsistent tilordning til en delmengde av variablene deres kan utvides til en evaluering av alle variabler som tilfredsstiller alle begrensninger. Denne definisjonen utvider ikke akkurat det ovennevnte fordi variablene som evalueringene skal antas å være utvidbare ikke nødvendigvis er i alle omfang av de involverte begrensningene. ${\ displaystyle m}$${\ displaystyle (i, m)}$${\ displaystyle i}$

Hvis det blir gitt en rekkefølge av variablene, kan relasjonskonsistens begrenses til tilfellene når variablene (r) evalueringen skal kunne utvides for å følge de andre variablene i rekkefølgen. Denne modifiserte tilstanden kalles retningsbestemt relasjonskonsistens.

Relasjonell konsistens og tilfredshet

Et problem med begrensningstilfredshet kan være relasjonelt konsistent, ikke ha noe tomt domene eller utilfredsstillende begrensning, og likevel være utilfredsstillende. Det er imidlertid noen tilfeller der dette ikke er mulig.

Det første tilfellet er det med et sterkt relasjonelt- konsistent problem når domenene maksimalt inneholder elementer. I dette tilfellet kan en konsistent evaluering av variabler alltid utvides til en annen variabel. Hvis er en slik evaluering og er variabelen, er det bare mulige verdier variabelen kan ta. Hvis alle slike verdier er uoverensstemmende med evalueringen, er det (ikke nødvendigvis unike) begrensninger som blir krenket av evalueringen og en av dens mulige verdier. Som et resultat kan evalueringen ikke utvides til å tilfredsstille alle disse eller mindre begrensningene, og bryter betingelsen om sterk relasjonell- konsistens. ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle k}$${\ displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$

Det andre tilfellet er relatert til et mål på begrensningene, i stedet for domenene. En begrensning er -tett hvis hver evaluering til alle dens variabler, men en kan utvides for å tilfredsstille begrensningen, enten med alle mulige verdier for den andre variabelen eller ved de fleste av dens verdier. Problem med å ha tette begrensninger er tilfredsstillende hvis og bare hvis de er sterkt relasjonelt- konsistente. ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle m + 1}$

En konvek matris: radene i hver rad er sammenhengende (ingen 0 mellom dem).

Det tredje tilfellet er det med binære begrensninger som kan representeres av rad-konvekse matriser. En binær begrensning kan bli representert med en bidimensjonal matrise , hvor er 0 eller 1 avhengig av om -th-verdien til domenet til og -th-verdien til domenet for å tilfredsstille begrensningen. En rad med denne matrisen er konveks hvis 1-ene den inneholder er påfølgende (formelt, hvis to elementer er 1, er alle elementer i mellom også 1). En matrise er rad-konveks hvis alle radene er konvekse. ${\ displaystyle M}$${\ displaystyle M_ {ij}}$${\ displaystyle i}$${\ displaystyle x_ {i}}$${\ displaystyle j}$${\ displaystyle x_ {j}}$

Hver matrise representerer begrensningen mellom x _i og x _{k +1} . Hvis a ₁ ... a _k er verdier for x ₁ ... x _k , forteller radene a ₁ ... a _k i hver matrise de tillatte verdiene for x _{k +1} . Rad-konveks ness og sterk relasjonell banekonsistens innebærer eksistensen av en konsistent verdi a _{k +1} for x _{k +1} .

Betingelsen som gir sterk relasjonell banekonsistens som tilsvarer tilfredshet er den av problemer med begrensningstilfredshet som det eksisterer en rekkefølge av variablene som gjør at alle begrensninger blir representert av rad konvekse matriser. Dette resultatet er basert på det faktum at et sett med konvekse rader som har et felles element parvis også har et globalt felles element. Tatt i betraktning en evaluering av variabler, blir de tillatte verdiene for den ene gitt ved å velge noen rader fra noen begrensninger. Spesielt for hver variabel blant disse representerer raden i forhold til dens verdi i matrisen som representerer begrensningen knyttet til den med den tillatte verdiene til sistnevnte. Siden disse radene er konvekse, og de har et felles element parvis på grunn av banekonsistens, har de også et delt felleselement, som representerer en verdi av den siste variabelen som er i samsvar med de andre. ${\ displaystyle k}$${\ displaystyle k + 1}$${\ displaystyle k}$${\ displaystyle k + 1}$

Bruk av lokal konsistens

Alle former for lokal konsistens kan håndheves ved forplantning av begrensninger, noe som kan redusere domenene til variabler og oppdragssett som tilfredsstiller en begrensning og kan innføre nye begrensninger. Når forplantning av begrensning produserer et tomt domene eller en utilfredsstillende begrensning, er det originale problemet ikke tilfredsstillende. Derfor kan alle former for lokal konsistens brukes som tilnærminger av tilfredshet. Mer presist kan de brukes som ufullstendige algoritmer for usikkerhet, da de kan bevise at et problem er utilfredsstillende, men generelt ikke er i stand til å bevise at et problem er tilfredsstillende. Slike tilnærmede algoritmer kan brukes av søkealgoritmer ( backtracking , backjumping , local search , etc.) som heuristikker for å fortelle om en delvis løsning kan utvides for å tilfredsstille alle begrensninger uten å analysere den ytterligere.

Selv om begrensningsutbredelse ikke gir et tomt domene eller en utilfredsstillende begrensning, kan det likevel redusere domenene eller styrke begrensningene. Hvis dette er tilfelle, reduseres søkeområdet for problemet, og reduserer dermed mengden søk som trengs for å løse problemet.

Lokal konsistens viser tilfredshet i noen begrensede tilfeller (se Kompleksitet med begrensningstilfredshet # Begrensninger ). Dette er tilfelle for noen spesielle slags problemer og / eller for noen slags lokal konsistens. Å håndheve lysbue-konsistens på binære sykliske problemer gir for eksempel mulighet til å fortelle om problemet er tilfredsstillende. Å håndheve sterk retnings- konsistens gjør det mulig å fortelle tilfredsstillelsen av problemer som har indusert bredde i samme rekkefølge. Adaptiv retningskonsistens gjør det mulig å fortelle tilfredsstillelsen av et vilkårlig problem. ${\ displaystyle i}$${\ displaystyle i-1}$

Se også

• Enhetsformering
• Begrensningsprogrammering
• Begrensning logikk programmering
• Se fremover (backtracking)

Eksterne linker

• Constraint Propagation - Dissertation av Guido Tack som gir en god oversikt over teori og implementeringsspørsmål

referanser

• Lecoutre, Christophe (2009). Begrensningsnettverk: Teknikker og algoritmer . ISTE / Wiley. ISBN  978-1-84821-106-3
• Dechter, Rina (2003). Behandling av begrensninger . Morgan Kaufmann.ISBN  1-55860-890-7
• Apt, Krzysztof (2003). Prinsipper for begrensningsprogrammering . Cambridge University Press.ISBN  0-521-82583-0
• Marriott, Kim; Peter J. Stuckey (1998). Programmering med begrensninger: En introduksjon . MIT Trykk.ISBN  0-262-13341-5