| O(m~2)时间求解SAT问题的随机算法 |
| |
| 引用本文： | 徐云,陈国良,许胤龙,顾钧.O(m~2)时间求解SAT问题的随机算法[J].计算机学报,2001(11). |
| |
| 作者姓名： | 徐云 陈国良 许胤龙 顾钧 |
| |
| 作者单位： | 中国科学技术大学计算机科学与技术系 合肥230027
(徐云，陈国良，许胤龙)，中国科学技术大学计算机科学与技术系 合肥230027(顾钧) |
| |
| 基金项目： | 国家“九七三”重点基础研究发展规划项目 ( G19980 30 40 3)资助 |
| |
| 摘 要： | 传统的求解 SAT问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 SAT问题的随机算法 Sat Test1和 Sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 SAT问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 Sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 SAT实例有较好的求解能力 .
|
| 关 键 词： | SAT问题 随机算法 数学期望 不满足解数 |
O(m~2) Time Randomized Algorithms for SAT Problem |
| |
| XU Yun CHEN Guo-Liang XU Yin-Long GU Jun ,.O(m~2) Time Randomized Algorithms for SAT Problem[J].Chinese Journal of Computers,2001(11). |
| |
| Authors: | XU Yun CHEN Guo-Liang XU Yin-Long GU Jun |
| |
| Affiliation: | XU Yun 1) CHEN Guo-Liang 1) XU Yin-Long 1) GU Jun 1),2) 1) |
| |
| Abstract: | |
| |
| Keywords: | satisfiability problem randomized algorithms mathematical expectation the number of unsatisfiable solutions |
| 本文献已被 CNKI 等数据库收录！ |
