| 用于求解正则(3,4)-SAT实例集的修正警示传播算法 |
| |
| 引用本文： | 佘光伟,许道云.用于求解正则(3,4)-SAT实例集的修正警示传播算法[J].计算机科学,2018,45(11):312-317. |
| |
| 作者姓名： | 佘光伟 许道云 |
| |
| 作者单位： | 贵州大学计算机科学与技术学院 贵阳550025,贵州大学计算机科学与技术学院 贵阳550025 |
| |
| 基金项目： | 本文受国家自然科学基金项目(61762019,1)资助 |
| |
| 摘 要： | 利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。
|
| 关 键 词： | 极小不可满足公式 正则(3 4)-SAT问题 警示传播算法 |
| 收稿时间： | 2018/7/12 0:00:00 |
| 修稿时间： | 2018/9/21 0:00:00 |
Modified Warning Propagation Algorithm for Solving Regular (3,4)-SAT Instance Sets |
| |
| SHE Guang-wei and XU Dao-yun.Modified Warning Propagation Algorithm for Solving Regular (3,4)-SAT Instance Sets[J].Computer Science,2018,45(11):312-317. |
| |
| Authors: | SHE Guang-wei and XU Dao-yun |
| |
| Affiliation: | College of Computer Science and Technology,Guizhou University,Guiyang 550025,China and College of Computer Science and Technology,Guizhou University,Guiyang 550025,China |
| |
| Abstract: | |
| |
| Keywords: | Minimal unsatisfiable formula Regular (3 4)-SAT problem Warning propagation algorithm |
|
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
|
