Abstrakt. I detta dokument hävdar vi att ett attraktivt och potentiellt mycket allmänt sätt att uppnå generaliserad båge konsistens (GAC) på en begränsning är genom att använda enhet förökning (UP) över en CNF-kodning av begränsningen. Detta tillvägagångssätt för GAC erbjuder ett antal fördelar jämfört med traditionella begränsningar specifika algoritmer (propagatorer): det är lättare att genomföra, det ger automatiskt inkrementalitet och decrementalitet i ett bakåtspårande sammanhang, och det kan ge klausal skäl att stödja lärande och icke-kronologisk backtracking. Även om UP på standard CNF-kodningar av en begränsning misslyckas med att uppnå GAC, visar vi här att alternativa CNF-kodningar kan användas på vilka UP faktiskt uppnår GAC. Vi tillhandahåller en generisk kodning som är tillämplig på alla begränsningar. Vi ger också strukturspecifika kodningar för de regelbundna, bland och gensekvensbegränsningar som UP kan uppnå GAC med samma tidsramar som tidigare presenterade propagatorer. Slutligen förklarar vi hur en UP-motor kan läggas till en CSP-lösare för att uppnå en sömlös integrering av begränsningar som kodats i CNF och förökas via UP och de som förökas via traditionella restriktionsspecifika propagatorer.
I REF föreslås ett allmänt sätt att konstruera en (eventuellt icke-polynom) upac-kodning för eventuella begränsningar.
Gac via unit propagation
{'venue': 'Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007', 'journal': None, 'mag_field_of_study': ['Computer Science']}