利用膨胀图求解SAT问题

摘要：

一般的求解SAT问题的随机算法是对一个CNF公式的解进行f次随机搜索，共需要tn(n为变元个数)个随机位。本文提出的算法，利用膨胀图的性质诱导随机步搜索CNF公式的t个解，只需要(n+tlogn)位随机位，降低了算法对随机位的依赖。

关键词： SAT问题 膨胀图 随机算法 随机搜索

作者: 吴学江

作者单位: 贵州大学计算机学院,贵州 贵阳,550025

会议类型: 国内会议

会议名称: 中国通信学会第五届学术年会

会议地点: 南京

会议语种:中文

页码: 154-157

在线出版日期: 2008-02-01（万方平台首次上网日期，不代表论文的发表时间）