Node and arc consistency in weighted CSP
Javier Larrosa · 2002
Recently, a general definition of arc consistency (AC) for soft constraint frameworks has been proposed (Schiex 2000). In this paper we specialize this definition to weighted CSP and introduce a O(ed3) algorithm. Then, we refine the definition and introduce a stronger form of arc consistency (AC*) along with a O(n2d3) algorithm. We empirically demonstrate that AC * is likely to be much better than AC in terms of pruned values.