Ordering heuristics for Singleton Arc Consistency

Ordering heuristics for Singleton Arc Consistency,10.1109/MEC.2011.6025478,ChuiLiu Kong,Shimei Xing

Ordering heuristics for Singleton Arc Consistency  
BibTex | RIS | RefWorks Download
The use of consistency techniques is the main feature of any Constraint S atisfaction Problems(CS Ps)solver. Arc Consistency (AC) applied to preprocessing can reduce the search space by removingthe values which are arc inconsistent. Singleton Arc Consistency (S AC) is a stronger level of consistencythan AC. Arc consistency technique with heuristic strategy has been proved to be an efficient techniqueto improve the efficiency of algorithms. In this paper, we first study the well-known S AC-3 algorithm indetail, and propose two algorithms with heuristic strategies for the drawbacks in S AC-3, S AC-3-FFPand S AC-3-MINIsup. Then, we give the correctness proof and complexity analysis. In the end, we implement the two algorithms in some random CS Ps and benchmarks during the preprocessing step. Experimental results show that the two algorithms perform better than S AC-3 for most test cases.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.