An Algorithm Based on Extension Rule For Solving #SAT Using Complementary Degree
-
摘要: #SAT问题又称模型计数(model counting)问题是人工智能领域的研究热点之一，在人工智能领域被广泛应用.在对基于扩展规则的#SAT问题求解方法CER(counting models using extension rules)深入研究的基础上，提出一种结合互补度的#SAT问题求解方法.在计算给定子句集的模型个数时，利用SE-Tree(set enumeration tree)形式化地表达计算过程，逐步生成需要计算的子句集合，并在SE-Tree中添加终止结点，避免大部分含互补文字子句集合的生成，且不会因剪枝而导致求解不完备.提出互补度的概念，在扩展SE-Tree结点时按照互补度由大到小的顺序扩展，较早地生成含互补文字且长度较小的子句集合，有效减少枚举树生成的结点个数，进而减少对子句集合判断是否含互补文字的计算次数.实验结果表明：与CER方法相比该方法效率较好，且进一步改进了CER方法在互补因子较低时求解效率低下的不足.Abstract: The #SAT problem also called model counting is one of the important and challenging problems in artificial intelligence. It is used widely in the field of artificial intelligence. After doing the in-depth study of model counting algorithm CER that is based on Extension Rule, we propose a method using complementary degree for #SAT problem in this paper. We formalize the computing procedure of solving #SAT problem by introducing SE-Tree which produces all the subsets of clause set that need to be computed. As the closed nodes are added into the SE-Tree, the most subsets that contain complementary literal(s) can never be produced, and the true resolutions cannot be missed by pruning either. Then the concept of complementary degree is presented in this paper, and the nodes of SE-Tree are extended in accordance with the descending order of complementary degree. With this extended order, the subsets that contain complementary literal(s) and have smaller size can not only be generated early, but also can reduce the number of generated nodes that are redundant. Moreover the calculation for deciding the complementarity of subsets is reduced. Results show that the corresponding algorithm runs faster than CER algorithm and further improves the solving efficiency of problems which complementary factor is lower.
-
-
期刊类型引用(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 . 百度学术
其他类型引用(33)
计量
- 文章访问数: 1070
- HTML全文浏览量: 0
- PDF下载量: 464
- 被引次数: 45
下载:
