一种笛卡尔积压缩的负表约束上表缩减算法

详细信息    查看全文 | 推荐本文 |

英文篇名：A Tabular Reduction Algorithm on Negative Table Constraint Compressed by Cartesian Product 作者：蔡毛毛 ; 李占山 ; 董学阳 英文作者：CAI Maomao;LI Zhanshan;DONG Xueyang;Key Laboratory of Symbolic Computation and Knowledge Engineering Ministry of Education,College of Computer Science and Technology,Jilin University;Public Computer Education and Research Center,Jilin University; 关键词：约束满足问题 ; 负表约束 ; 表压缩 ; 弧相容 英文关键词：constraint satisfaction problem;;negative table constraint;;table compression;;arc consistency 中文刊名：JLDX 英文刊名：Journal of Jilin University(Science Edition) 机构：吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室;吉林大学公共计算机教学与研究中心; 出版日期：2019-05-26 出版单位：吉林大学学报(理学版) 年：2019 期：v.57;No.237 基金：吉林省科技发展计划项目(批准号:20140101200JC) 语种：中文; 页：JLDX201903023 页数：7 CN：03 ISSN：22-1340/O 分类号：139-145

摘要

利用笛卡尔积压缩方法可有效减小负表约束规模的原理,提出一种在压缩负表上维持广义弧相容的高效算法STRC-N,以解决负表约束维持弧相容过程中遍历所有元组导致效率低的问题.实验结果表明,当压缩负表上压缩率较大时,得益于表规模的减小,新算法相对于主流的负表约束处理算法效率更高,性能更好,从而实现了对负表约束处理算法的改进.
        Based on the principle that cartesian product compression could effectively reduce the scale of negative table constraint,we proposed an efficient algorithm STRC-N to maintain generalized arc consistency on compressed negative table,which solved the problem of traversal of all tuples and low efficiency in the process of maintaining generalized arc consistency on negative table constraint.Experimental results show that when the compression rate of negative table is large,the new algorithm has higher efficiency and better performance than the mainstream negative table constraint processing algorithm due to the reduction of table size.Thus,the negative table constraints processing algorithm is improved.

引文

[1]FREUDER E C,MACKWORTH A K.Constraint Satisfaction:An Emerging Paradigm[J].Foundations of Artificial Intelligence,2006,2:13-27.
    [2]LECOUTRE C.STR2:Optimized Simple Tabular Reduction for Table Constraints[J].Constraints,2011,16(4):341-371.
    [3]LECOUTRE C,LIKITVIVATANAVONG C,YAP R H C.STR3:A Path-Optimal Filtering Algorithm for Table Constraints[J].Artificial Intelligence,2015,220:1-27.
    [4]CHENG K C K,YAP R H C.An MDD-Based Generalized Arc Consistency Algorithm for Positive and Negative Table Constraints and Some Global Constraints[J].Constraints,2010,15(2):265-304.
    [5]XIA Wei,YAP R H C.Optimizing STR Algorithms with Tuple Compression[C]//International Conference on Principles and Practice of Constraint Programming.Berlin:Springer,2013:724-732.
    [6]WANG Ruiwei,XIA Wei,YAP R H C,et al.Optimizing Simple Tabular Reduction with a Bitwise Representation[C]//International Joint Conference on Artificial Intelligence.Palo Alto:AAAI Press,2016:787-793.
    [7]DEMEULENAERE J,HARTERT R,LECOUTRE C,et al.Compact-Table:Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets[C]//International Conference on Principles and Practice of Constraint Programming.Berlin:Springer,2016:207-223.
    [8]LI Hongbo,LIANG Yanchun,GUO Jinsong,et al.Making Simple Tabular Reduction Works on Negative Table Constraints[C]//Twenty-Seventh AAAI Conference on Artificial Intelligence.Palo Alto:AAAI Press,2013:1629-1630.
    [9]李宏博,梁艳春,李占山.负表约束的简单表缩减广泛弧相容算法[J].软件学报,2016,27(11):2701-2711.(LIHongbo,LIANG Yanchun,LI Zhanshan.Simple Tabular Reduction for Generalized Arc Consistency on Negative Table Constraints[J].Journal of Software,2016,27(11):2701-2711.)
    [10]李宏博.约束满足问题研究及其在蛋白质结构预测中的应用[D].长春:吉林大学,2015.(LI Hongbo.Research of Constraint Satisfaction Problem and Its Application in Protein Structure Prediction[D].Changchun:Jilin University,2015.)
    [11]BESSTERE C,REGIN J C.Arc Consistency for General Constraint Networks:Preliminary Results[C]//Proceddings of 15th International Joint Conference on Artificial Intelligence.Palo Alto:AAAI Press,1997:398-404.
    [12]KATSIRELOS G,WALSH T.A Compression Algorithm for Large Arity Extensional Constraints[C]//International Conference on Principles and Practice of Constraint Programming.Berlin:Springer-Verlag,2007:379-393.
    [13]GENT I P,MACINTYRE E,PRESSER P,et al.An Empirical Study of Dynamic Variable Ordering Heuristics for the Constraint Satisfaction Problem[C]//International Conference on Principles and Practice of Constraint Programming.Berlin:Springer,1996:179-193.
    [14]XU Ke,BOUSSEMART F,HEMERY F,et al.A Simple Model to Generate Hard Satisfiable Instances[C]//International Joint Conference on Artificial Intelligence.San Francisco,CA:Morgan Kaufmann Publishers,2005:337-342.
    [15]XU Ke,BOUSSEMART F,HEMNERY F,et al.Random Constraint Satisfaction:Easy Generation of Hard(Satisfiable)Instances[J].Artificial Intelligence,2007,171(8):514-534.