I denna artikel presenteras en modell och genomförandetekniker för att påskynda tvångsförökning. Tre grundläggande tillvägagångssätt för att förbättra begränsningsförökning baserad på förökningar som genomförande av begränsningar undersöks: hålla reda på vilka förökningsförrättare som är på fixering, välja vilken förökningsförrättare som ska tillämpas härnäst, och hur man ska kombinera flera förökningsförrättare för samma begränsning. Vi visar hur idempotence resonemang och händelser hjälper spåra fixpoints mer exakt. Vi förbättrar dessa metoder genom att använda dem dynamiskt (med hänsyn till aktuella variabelområden för att förbättra noggrannheten). Vi definierar prioritetsbaserade metoder för att välja nästa propagator och visar att dynamiska prioriteringar kan förbättra utbredningen. Vi illustrerar att användningen av flera propagatorer för samma begränsning kan vara fördelaktig med prioriteringar, och införa iscensatta propagatorer som kombinerar effekterna av flera propagatorer med prioriteringar för ökad effektivitet. • 2:3 lösning till CSP. Det andra subproblemet har x 1  på {2}, x 2 på {2} och x 3 på {1, 2}, och leder till en annan lösning. Som framgår av exemplet, ändliga domänrestriktion programmering interleaves förökning med sökning. I detta dokument undersöker vi hur man gör en förökningsmotor så effektiv som möjligt. Det finns två viktiga beslut som motorn måste fatta: vilka propagatorer som ska verkställa och i vilken ordning de ska verkställa. För att göra begränsningsutbredningen effektiv är det tydligt att motorn måste ta hänsyn till följande frågor: undvika onödig spridning, begränsa spridningen till relevanta variabler och välja den billigaste möjliga metoden för förökning. I den här artikeln visar vi hur förökning kan påskyndas om motorn tar hänsyn till dessa frågor. Artikelns bidrag är följande: -Vi ger en formell definition av förökningssystem inklusive fixpoint- och händelsebaserade optimeringar som används i nuvarande förökningssystem. -Vi utökar händelsebaserade spridningssystem för att använda dynamiskt föränderliga händelseuppsättningar. -Vi introducerar flera propagatorer och iscensatta propagatorer för en enda begränsning för användning med förökningsköer med prioritet. -Vi ger experimentella resultat som klargör effekten av många val i genomförandet av förökningsmotorer: inklusive idempotence resonemang, statiska och dynamiska händelser, grundläggande köstrategier, prioriterade köer, och iscensatt förökning. Artikelns plan. I nästa avsnitt införs förökningsbaserad begränsningslösning, följt av en modell för begränsningsutbredningssystem i avsnitt 3. I avsnitt 4 presenteras hur man optimerar spridningen genom att ta hänsyn till idempotens, medan avsnitt 5 undersöker användningen av händelseuppsättningar. Vilken förökningsförrättare som ska avrättas härnäst diskuteras i avsnitt 6, medan kombinationsstrategier för flera förökningsförrättare för samma begränsning diskuteras i avsnitt 7. Experiment för varje funktion ingår i det relevanta avsnittet, och en sammanfattning ges i avsnitt 8. Avsnitt 9 avslutas. I detta avsnitt definieras vår terminologi för de grundläggande komponenterna i en tvångsförökningsmotor. I detta papper, vi begränsar oss till ändliga domän heltal begränsning lösning. Nästan all diskussion gäller för andra former av ändliga domänbegränsningslösning såsom för uppsättningar och multiuppsättningar. En domän D är en fullständig kartläggning från en fast (finita) uppsättning av variabler V till ändliga uppsättningar av heltal. En falsk domän D är en domän med D(x) = ∅ för vissa x  på V. En variabel x  på V är fixerad av en domän D, om  på D(x) ska = 1. Skärningspunkten mellan domänerna D 1 och D 2, betecknad D 1 D 2, definieras av domänen A domän D 1 är starkare än en domän D 2, skriven D 1 D 2, om D 1 (x) D 2 (x) för alla x  på V. En domän D 1 är starkare än (lika med) en domän D 2 w.r.t. Variabler Ett intervall är en sammanhängande uppsättning heltal; vi använder område notation [l.. u] för att beteckna intervallet {d  till Z  till l ≤ d ≤ u} när l och u är heltal. En domän är en områdesdomän om D(x) är ett område för alla x. Låt D = range(D) vara den minsta område domän som innehåller D, det vill säga den unika domänen Vi ska vara intresserade av begreppet en initial domän, som vi betecknar D init. Den ursprungliga domänen anger de initiala värden som är möjliga för varje variabel. Det gör det möjligt för oss att begränsa uppmärksamheten till domäner D sådan att D D init. Restriktioner. Ett heltal värdering är en kartläggning av variabler till heltal värden, skriven {x 1 → d 1,. .., x n → d n }. Vi utvidgar värderingen till att kartlägga uttryck och begränsningar som involverar variablerna på det naturliga sättet. Låt vars vara den funktion som returnerar uppsättningen av variabler som visas i en värdering. Vi definierar en värdering som en del av en domän D, skriven  och D, om.(x i )  och D(x i ) för alla x i  på vars( ska ). Den infimum och supremum av ett uttryck e med avseende på en domän D definieras som inf D e = inf{ på (e)  på... och sup D e = sup{.. Vi kan kartlägga en värdering till en domän D  på följande sätt:
Flera möjligheter kan övervägas för att genomföra restriktion förökning när flera förökningsmaterial finns tillgängliga REF.
Efficient constraint propagation engines
{'venue': 'TOPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}