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(ed~3) algorithm. Then, we refine the definition and introduce a stronger form of arc consistency (AC~*) along with a O(n~2d~3) algorithm. We empirically demonstrate that AC~* is likely to be much better than AC in terms of pruned values.
展开▼
