| O（m^2）时间求解SAT问题的随机算法 |
| |
| 引用本文： | 徐云 顾钧 等. O（m^2）时间求解SAT问题的随机算法[J]. 计算机学报, 2001, 24(11): 1136-1141 |
| |
| 作者姓名： | 徐云 顾钧 等 |
| |
| 作者单位： | [1]中国科学技术大学计算机科学与技术系，合肥230027 [2]香港科技大学计算机系，香港 |
| |
| 基金项目： | 本课题得到国家"九七三”重点基础研究发展规划项目(G1998030403)资助. |
| |
| 摘 要： | 传统的求解SAT问题的随机算法主要是对满足解进行搜索，在找不到满足解的情况下，则无法正确判断问题的可满足性。该文提出了两个时间复杂度为O（m^2）求解SAT问题的随机算法SatTestl和SatTest2，这里m为CNF公式中的子句数。这两个随机算法是通过对不满足解数的估计来判断SAT问题的可满足性，不同于传统的随机算法。其中第二个算法SatTest2在搜索满足解的同时又可以对不满足解数进行估计，是对传统随机算法的重要改进。试验结果表明，文中提出的算法对相变区域的难SAT实例有较好的求解能力。
|
| 关 键 词： | SAT问题 随机算法 数学期望 NP问题 计算机 |
| 修稿时间： | 2000-01-29 |
O(m2) Time Randomized Algorithms for SAT Problem |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 等数据库收录！ |
