Begränsning slutledning

I begränsningstillfredsställelse är begränsningsinferens ett förhållande mellan begränsningar och deras konsekvenser . En uppsättning begränsningar $D$ innebär en begränsning $C$ om varje lösning till $D$ också är en lösning till $C$ . Med andra ord, om $V$ är en värdering av variablerna i omfattningen av begränsningarna i $D$ och alla begränsningar i $D$ är uppfyllda av $V$ , då uppfyller $V$ också begränsningen $C$ .

Vissa operationer på begränsningar ger en ny begränsning som är en konsekvens av dem. Begränsningssammansättning fungerar på ett par binära begränsningar $((x,y),R)$ och $((y,z) ,S)$ med en gemensam variabel. Sammansättningen av dessa två begränsningar är begränsningen $((x,z),Q)$ som uppfylls av varje utvärdering av de två icke-delade variabler för vilka det finns ett värde av den delade variabeln $y$ så att utvärderingen av dessa tre variabler uppfyller de två ursprungliga begränsningarna $((x,y),R)$ och $((y,z),S)$ .

Begränsningsprojektion begränsar effekterna av en begränsning till några av dess variabler. Givet en begränsning $är {\displaystyle (t,R)}$ dess projektion till en delmängd $t'$ av dess variabler begränsningen $(t', R')$ som uppfylls av en utvärdering om denna utvärdering kan utökas till de andra variablerna på ett sådant sätt att den ursprungliga begränsningen ( $\displaystyle (t,R)}$ är uppfylld.

Utökad sammansättning liknar i princip sammansättning, men tillåter ett godtyckligt antal möjligen icke-binära begränsningar; den genererade begränsningen är på en godtycklig delmängd av variablerna för de ursprungliga begränsningarna. Givet begränsningar $C_{1},\ldots ,C_{m}$ och en lista $A$ av deras variabler, är den utökade sammansättningen av dem begränsningen $(A,R)$ där en utvärdering av $A$ uppfyller denna begränsning om den kan utökas till de andra variablerna så att $C_{1},\ ldots ,C_{m}$ är alla nöjda.

Se även

• Begränsning tillfredsställelse problem

•   Dechter, Rina (2003). Tvångsbearbetning . Morgan Kaufmann. ISBN 1-55860-890-7
•   Apt, Krzysztof (2003). Principer för begränsningsprogrammering . Cambridge University Press. ISBN 0-521-82583-0
•   Marriott, Kim; Peter J. Stuckey (1998). Programmering med begränsningar: En introduktion . MIT Press. ISBN 0-262-13341-5