基于函数变换的求解SAT问题的新算法

• 作者: 任世军 胡显伟
• 来源期刊: 智能计算机与应用
• 学科: 工学
• 关键词: SAT问题 局部搜索算法 函数变换 最速下降法
• 年，卷（期）: 2012,（3）
• 页码范围: 33-36,39
• 分类号: TP391.5
• 字数: 5028字
• 语种: 中文
• DOI: 10.3969/j.issn.2095-2163.2012.03.008

摘要

提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题.随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的.实验结果表明:与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	任世军	哈尔滨工业大学计算机科学与技术学院	18	228	7.0	15.0
2	胡显伟		5	4	1.0	2.0