计算机科学 ›› 2015, Vol. 42 ›› Issue (7): 28-31.doi: 10.11896/j.issn.1002-137X.2015.07.007
陈德泉 张永刚 辛 颖 刘文壮
CHEN De-quan ZHANG Yong-gang XIN Ying LIU Wen-zhuang
摘要： 研究约束求解中的相容性技术,针对目前已有相容性的传播级别,提出一种新的相容性概念——基于序列的子问题相容性(SSAC),并给出相应的实现算法。然后分析其时空、空间复杂性及正确性,证明SSAC化简不改变原约束满足问题的解集,同时证明SSAC的约束传播能力介于SAC和AC之间。通过对随机问题和composed问题的测试表明,所提算法的效率是已有算法SAC-SDS和SAC-3的2～3倍。
| [1] Bartak R.Theory and Practice of Constraint Propagation[C]∥Proceedings of the 3rd Workshop on Constraint Programming in Decision and Control.Gliwice,Poland,2001:7-14 [2] Gent I P,Nightingale P,Rowley A,et al.Solving quantified constraint satisfaction problems[J].Artificial Intelligence,2008,172(6/7):738-771(下转第37页)(上接第31页) [3] Yokoo M,Durfee E H,Ishida T,et al.Distributed constraint satisfaction for formalizing distributed problem solving[C]∥Proceedings of the 12th IEEE International Conference on Distributed Computing System.Yokohama,Japan:IEEE Computer Society Press,1992:614-621 [4] Bessiere C,Regin J C,Yap R H C,et al.An optimal coarse-grained Arc Consistency algorithm[J].Artificial Intelligence,2005,165(2):165-185 [5] Mackworth A K.Consistency in networks of relations[J].Artificial Intelligence,1977,8(1):99-118 [6] Bessiere C,Regin J C.Refining the basic constraint propagation algorithm[C]∥Proceedings of the 17th International Joint Conference on Artificial Intelligence.Seattle,USA:Morgan Kaufmann,2001:309-315 [7] Deburyne R,Bessiere C.Some practical filtering techniques for the constraint satisfaction problem[C]∥Proceedings of the 15th International Joint Conference on Artificial Intelligence.Nagoya,Japan:Morgan Kaufmann,1997:412-417 [8] Bartak R,Erben R.A new algorithm for singleton arc consistency[C]∥Proceedings of FLAIRS Conference.Florida,USA:AAAI Press,2004:257-262 [9] Bessiere C,Debruyne R.Optimal and suboptimal singleton arcconsistency algorithms[C]∥Proceedings of the 19th International Joint Conference on Artificial Intelligence.Edinburgh,UK:Professional Book Center,2005:54-59 [10] Lecoutre C,Cardon S.A greedy approach to establish singleton arc consistency[C]∥Proceedings of the 19th International Joint Conference on Artificial Intelligence.Edinburgh,UK:Professional Book Center,2005:199-204 [11] Bessiere C,Bessiere R.Theoretical analysis of singleton arc consistency and its extensions[J].Artificial Intelligence,2008:172(1):29-41 [12] 孙吉贵,朱兴军,张永刚,等.最先失败原则的约束传播算法[J].小型微型计算机系统,2008,29(4):678-681 Sun J G,Zhu X J,Zhang Y G.Constraint Propagation on Fail First Principle[J].Mini-Micro Systems,2008,29(4):678-681 [13] 孙吉贵,朱兴军,张永刚,等.一种基于预处理技术的约束满足问题求解算法[J].计算机学报,2008,31(6):919-926 Sun J G,Zhu X J,Zhang Y G.An Approach of Solving Constraint Satisfaction Problem Based on Preprocessing[J].Chinese Journal of Computers,2008,31(6):919-926 [14] 朱兴军,孙吉贵,张永刚,等.一种新的基于完全独立相容性的预处理技术[J].自动化学报,2009,35(1):71-76 Zhu X J,Sun J G,Zhang Y G.A new preprocessing technique based on entirety singleton consistency[J].Acta Automatica Sinica,2009,35(1):71-76 [15] 朱兴军,张永刚,李莹,等.多值传播的相容性技术[J].自动化学报,2009,35(10):1296-1301 Zhu X J,Zhang Y G,Li Y,et al.Consistency Technique of Multi-Value Propagation[J].Acta Automatica Sinica,2009,35(10):1296-1301 [16] 刘春晖,朱兴军,孙吉贵.一种改进的双向singleton弧相容算法[J].吉林大学学报(工学版),2008,3(28):666-670 Liu C H,Zhu X J,Sun J G.Improved bidirectional singleton arc consistency algorithm[J].Journal of Jilin University Enginee-ring and Technology Edition,2008,3(28):666-670 [17] Tsang E P K.Foundations of Constraint Satisfaction[M].Academic Press,London and San Diego,1993 [18] Gent I P,Macintyre E,Prosser P,et al.Random constraint satisfaction:Flaws and structure[J].Journal of Constraints,2001,6(4):345-372 |
| No related articles found! |
|
||
首页