求解约束可满足问题的eSTR算法优化

王瑞伟; 李占山; 李宏博

doi:10.7544/issn1000-1239.2016.20150284

求解约束可满足问题的eSTR算法优化

王瑞伟^1,3,
李占山^1,2,3,
李宏博^1,2

¹(符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012)
²(吉林大学计算机科学与技术学院长春 130012)
³(吉林大学软件学院长春 130012) (120801104@qq.com)

基金项目: 国家自然科学基金项目(61170314,61272208)；吉林省自然科学基金项目(20140101200JC)

详细信息

中图分类号: TP18
计量
- 文章访问数: 01108
- HTML全文浏览量: 0
- PDF下载量: 0613
出版历程
- 发布日期: 2016-06-30

Optimizing eSTR Algorithm for Solving Constraint Satisfaction Problems

¹(Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
²(College of Computer Science and Technology, Jilin University, Changchun 130012)
³(College of Software, Jilin University, Changchun 130012)

摘要

摘要: 表约束方法是1种外延式知识表示方法，每个约束通过元组集直接枚举出其在1个变量集上允许或禁止的所有元组，直观易于理解，在约束程序中得到了深入的研究，这是因为表约束出现在如设计、数据库、配置以及偏好建模等许多现实世界的应用中.但随着约束的增多及其元组集增大，占有的空间与相容性检测效率成了关键问题.eSTR是1个将STR扩展到高阶相容的算法，通过深入分析eSTR算法后发现有2种优化方式:PW\+{sup}数据结构和极小约束范围，同时证明了在极小约束范围上，约束网络仍然能够维持PWC+GAC，其中极小约束范围可以通过删除约束元组集中相应的列来降低eSTR2算法的空间消耗，而PW\+{sup}数据结构能够通过避免不必要的PW支持检测来减少eSTR2的CPU运行时间，实验结果表明：2种优化方式和eSTR2相结合后能够同时减少算法的空间消耗和CPU运行时间，在许多类实例上明显优于eSTR2和eSTR2w.
- 高阶相容 /
- 极小约束范围 /
- 约束网络 /
- PW\+{sup}数据结构 /
- PWC+GAC
Abstract: Table constraints, i.e., constraints given in extension by listing all allowed (or forbidden) tuples, are very straight forward and easy to understand, which are intensively studied in constraint programming (CP). Because such constraints are presented in many real world applications from areas such as design, databases, configuration and preferences modeling. However, With the growth of number of constraints and number of tuples, the space cost for table constraints and time cost of consistency checking have become key topics. eSTR is an algorithm which extends simple tabular reduction (STR) to higher-order consistency. After in-depth analysis of eSTR algorithm, this paper proposes two kinds of optimized methods for eSTR: PW\+{sup} data structure and minimal constraint scope, and then we prove that the constraint network enforce Pair-Wise Consistency and Generalized Arc-Consistency (PWC+GAC) with minimal constraint scope is equivalent to original constraint scope. At the same time, minimal constraint scope can reduce further space cost of eSTR2 algorithm by deleting columns of the tables in constraints, and PW\+{sup} data structure can reduce the CPU running time by avoiding some unnecessary checking of Pair-Wise-support (PW-support), since tuples in table of the constraint may not lose any PW-supports on the tables of other neighbour constraints. The experimental results show that combining our methods with eSTR2 algorithm can obviously outperform eSTR2 and eSTR2w on many instances of different problems, since it reduces the space cost and CPU running time of eSTR algorithm.
- higher-order consistency /
- minimal constraint scope /
- constraint network /
- PW\+{sup} data structure /
- PWC+GAC

HTML全文

参考文献(0)

施引文献(45)

期刊类型引用(12)

1.	刘强，朱金森，赵龙龙，沙宇晨，刘尚东，季一木. 基于字句动态特征和自注意力的情感分析方法. 数据采集与处理. 2024(01): 193-203 . 百度学术
2.	韩虎，孟甜甜. 面向语法加权图文本的方面情感三元组抽取. 北京航空航天大学学报. 2024(02): 409-418 . 百度学术
3.	郭磊，贾真，李天瑞. 面向方面级情感分析的交互式关系图注意力网络. 计算机应用. 2024(03): 696-701 . 百度学术
4.	杨锐，刘永坚，解庆，刘平峰. 基于Graph-LSTMs的双重位置感知方面级情感分类. 计算机应用与软件. 2024(04): 165-172 . 百度学术
5.	刘辉，马祥，张琳玉，何如瑾. 融合匹配长短时记忆网络和语法距离的方面级情感分析模型. 计算机应用. 2023(01): 45-50 . 百度学术
6.	代祖华，刘园园，狄世龙. 语义增强的图神经网络方面级文本情感分析. 计算机工程. 2023(06): 71-80 . 百度学术
7.	孟甜甜，韩虎，吴渊航. 面向方面抽取与情感分类的多任务联合建模. 计算机科学与探索. 2023(07): 1669-1679 . 百度学术
8.	程帆，王芳，黄树成. 基于混合编码与双通道GCN的方面级情感分析. 软件导刊. 2023(07): 15-20 . 百度学术
9.	孙天伟，杨长春，顾晓清，谈国胜. 结合共现网络的方面级情感分析研究. 计算机工程与应用. 2023(20): 111-118 . 百度学术
10.	张文钧，蒋良孝，张欢，陈龙. 一种双层贝叶斯模型：随机森林朴素贝叶斯. 计算机研究与发展. 2021(09): 2040-2051 . 本站查看
11.	韩虎，吴渊航，秦晓雅. 面向方面级情感分析的交互图注意力网络模型. 电子与信息学报. 2021(11): 3282-3290 . 百度学术
12.	巫浩盛，缪裕青，张万桢，周明，文益民. 基于距离与图卷积网络的方面级情感分析. 计算机应用研究. 2021(11): 3274-3278+3321 . 百度学术