SLS算法求解平衡正则(k,2r)-CNF公式

• 作者: 李梓齐 许道云
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: SAT问题 正则CNF公式 随机局部搜索 WalkSAT算法 NSAT算法
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1-5
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2019.01.001

摘要

可满足性问题的求解算法和结构性质研究是计算机科学中重要问题之一,为寻求某些CNF公式子类问题有效算法或算法改进途径,对公式的结构加以某些限制,其中限定子句长度为恒定常数和变元出现次数是常见的处理方式.研究具有正则结构且每个变元正负出现均衡的结构化公式的可满足性问题求解,其随机生成模型的构建及随机实验测试有助于观察解分布状况.并且,随机局部搜索算法在求解具有一定规则结构CNF公式实例中具有良好效率.本文集中研究平衡正则(k,2r)-CNF公式的求解问题,即限制每个子句的长度为k,每个变元出现的次数为偶数2r,并且每个变元正负出现的次数在相等情况下的可满足性问题求解.给出BR(n,k,2r)模型,以此模型来生成具有特殊结构的平衡正则(k,2r)-CNF公式实例,利用随机局部搜索算法求解问题.通过限制初始指派的0文字和1文字各占一半且均匀生成,以WalkSAT算法和NSAT算法做实验对比,发现对于平衡正则(k,2r)-CNF公式,实例具有明显效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与技术学院	125	460	12.0	16.0
2	李梓齐	贵州大学计算机科学与技术学院	1	0	0.0	0.0