期刊
ARTIFICIAL INTELLIGENCE
卷 159, 期 1-2, 页码 1-26出版社
ELSEVIER
DOI: 10.1016/j.artint.2004.05.004
关键词
constraint satisfaction; weighted CSP; local consistency; soft constraints
Recently, a general definition of arc consistency (AC) for soft constraint frameworks has been proposed by T. Schiex [Proc. CP-2000, Singapore, 2000, pp. 411-424]. In this paper we specialize this definition to weighted CSP and introduce two O(ed(3)) enforcing algorithms. Then, we refine the definition and introduce a stronger form of arc consistency (AC*) along with two O(n(2)d(2) + ed(3)) algorithms. As in the CSP case, an important application of AC is to combine it with search. We empirically demonstrate that a branch and bound algorithm that maintains either AC or AC* is a state-of-the-art general solver for weighted CSP Our experiments cover binary Max-CSP and Max-SAT problems. (C) 2004 Published by Elsevier B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据