一种基于预处理技术的约束满足问题求解算法  

An Approach of Solving Constraint Satisfaction Problem Based on Preprocessing

作　　者：孙吉贵[1] 朱兴军[1] 张永刚[1] 李莹[1] 

机构地区：[1]吉林大学计算机科学与技术学院

出　　处：《计算机学报》2008年第6期919-926,共8页Chinese Journal of Computers

基　　金：国家自然科学基金项目“扩展规则推理方法研究”(60773097)资助~~

摘　　要：相容性技术作为约束满足问题的一种有效求解技术，不论是在求解前的预处理过程中，还是在搜索过程中，都扮演着极为重要的角色。文中对预处理阶段的相容性技术进行改进和信息抽取，提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC^＊，并嵌入到BT框架中，形成新的搜索算法BT＋MPAC和BT＋MPAC^＊，给出了其正确性证明，通过复杂性分析得到Pre-AC和Pre-AC”的时间复杂度分别是O（nd）和O（ed^2），明显低于目前最流行的弧相容技术的时间复杂度O（ed^3）．实验测试结果表明：对于不同类别的用例，新算法的执行效率是弧相容维护算法的2～50倍。As an effective technology for solving constraint satisfaction problem, consistency technology plays an important role not only in preprocessing, but also in searching. Firstly, this paper proposes two new consistency algorithms called Pre-AC and Pre-AC^＊ applied during searching, which are based on the performance on an improvement of consistency during preprocessing and information extraction. Secondly this paper presents two new searching algorithms called BT＋MPAC and BT＋MPAC^＊ by embedding those two consistency algorithms into the BT framework respectively. ＇Thirdly, after proving the correctness of Pre-AC and Pre-AC^＊, this paper analyzes their time complexity. It is evidently that the complexities of Pre-AC and Pre-AC^＊ are O（nd） and O（ed^2） respectively, which are apparently lower than O（ed^3）, the complexity of arc consistency algorithm. In the experiments on several kinds of instances, efficiency of the pro- posed algorithms is 2-50 times higher of that of maintaining arc consistency.

关 键 词：约束满足问题 弧相容技术 singleton弧相容 pre-弧相容 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]