分类算法在命题公式骨干集中的应用研究
在理论计算机科学领域,命题公式的可满足性问题（SAT问题）是一类非常重要的NP完全问题。骨干集是SAT问题中一组特殊的变元,如果能够给出SAT实例的骨干集,那么求解SAT问题将会变得容易。一般情况,求解骨干集是NP难的。多数求解骨干集的算法都调用了SAT求解器,由于骨干集的上界较大,导致调用SAT求解器的次数较多,求解效率变低。ID3算法是最为基础的分类算法,其特征是计算属性的信息增益,利用信息增益对数据进行分类。因此,本文从命题公式的赋值数据集出发,计算变元的信息增益,探索变量取值与命题公式可满足性之间的关系,具体地讲,有如下创新点:（1）分析ID3算法的原理,寻找ID3算法原理与命题公式变量取值之间的关系,由此来缩小求解骨干集复杂度的上界,并减少调用SAT求解器次数,从而提高求解骨干集的效率。（2）提出了ID3＿Backbone算法,经实验证明,在调用同样SAT求解器的次数下,该算法效率优于传统算法,其准确率与SAT求解器的调用次数均在可允许的范围内。（3）基于该算法设计开发了求解骨干集的求解器,经测试可以满足用户实际使用的需求,具有很大的应用价值。
- 作者：
- 梁田
- 学位授予单位：
- 北方民族大学
- 专业名称：
- 计算机技术
- 授予学位：
- 硕士
- 学位年度：
- 2021年
- 导师姓名：
- 王晓峰；周琦
- 中图分类号：
- TP18
- 关键词：
- 分类算法；命题公式；ID3算法；骨干集
-