| 一个求解SAT问题的随机算法 |
| |
| 引用本文： | 吴学江,许道云.一个求解SAT问题的随机算法[J].贵州大学学报(自然科学版),2007,24(6):555-559. |
| |
| 作者姓名： | 吴学江 许道云 |
| |
| 作者单位： | 贵州大学,计算机科学与技术学院,计算机科学系,贵州,贵阳,550025 |
| |
| 摘 要： | 本文中引入了一个求解满足性问题的随机算法。在该算法中,利用CNF公式转换为其对偶式——DNF公式,通过对满足DNF公式的真值赋值数Y作出估计。根据Y与2n比较结果,对CNF公式的可满足性进行估计并对其满足性进行判断。
|
| 关 键 词： | SAT问题 随机算法 数学期望 NP完全问题 |
| 文章编号： | 1000-5269（2007）06-0555-05 |
| 修稿时间： | 2007-07-05 |
A Random Algorithm for SAT Problem |
| |
| WU Xue-jiang,XU Dao-yun.A Random Algorithm for SAT Problem[J].Journal of Guizhou University(Natural Science),2007,24(6):555-559. |
| |
| Authors: | WU Xue-jiang XU Dao-yun |
| |
| Institution: | Department of Computer Science, Guizhou University, Guiyang 550025, China |
| |
| Abstract: | In this paper,we proposed a random algorithm to solve the SAT problem.This algorithm transform firstly a CNF formula to a corresponding DNF formula and estimate the number Y of satisfiable solutions of the DNF formula.Comparing the Y with 2n,we can estimate the probability of satisfiable solution of CNF formula and judge whether the CNF formula is satisfiable or not. |
| |
| Keywords: | SAT problem random algorithms mathematical expectation NP complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
