CNF公式赋值空间上可满足解的概率性质

• 作者: 莫孝玲 许道云
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 合取范式(CNF)公式 赋值空间 翻转控制参数 可满足解
• 年，卷（期）: 2018,（11）
• 所属期刊栏目: 理论与算法
• 页码范围: 1852-1861
• 页数: 10页
• 分类号: TP301
• 字数: 8294字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1805035

摘要

为分析合取范式(conjunctive normal form,CNF)公式的赋值空间在可满足性情况下的结构性质,引入一个变元翻转次数控制的参数k,k不小于1且不大于n,n为公式中出现的变元个数,以赋值作为结点,基于翻转界控制下赋值满足子句数的大小,引入一类有向图——BF(bounded flips)图.研究带翻转控制参数的BF图的若干基础性质,根据BF图的性质研究CNF公式可满足解的概率性质.对于含有n个变元m个子句CNF公式,随着翻转控制参数k的增大,在其BF图上取得可满足解的概率也相应增大.当k靠近n时,概率稳定.对于可满足的CNF公式,在其任意k值下的BF图上进行t次随机游走.当t足够大时,取得可满足解的概率最终会收敛于1.最后,实验仿真支持性质的正确性.

作者信息

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