Efficient Singleton Consistency by Combining Forward Checking and Bound Consistency

作者：Guo Jinsong^*; Li Hongbo; Li Zhanshan; Zhang Yonggang; Jia Xianghua

来源：International Journal on Artificial Intelligence Tools, 2014, 23(4): 1460017.

DOI：10.1142/S0218213014600173

• Constraint satisfaction problem
• maxRPC
• consistency
• algorithm

Maintaining local consistencies can improve the efficiencies of the search algorithms solving constraint satisfaction problems (CSPs). Comparing with arc consistency which is the most widely used local consistency, stronger local consistencies can make the search space smaller while they require higher computational cost. In this paper, we make an attempt on the compromise between the pruning ability and the computational cost. A new local consistency called singleton strong bound consistency (SSBC) and its light version, light SSBC, are proposed. The search algorithm maintaining light SSBC can outperform MAC on a considerable number of problems.

• 出版日期2014-8
• 单位吉林大学