求解SAT问题的局部搜索算法及其平均时间复杂性分析

被引：5

作者：

刘涛，李国杰

机构：

[1] 中国科学院计算技术研究所，国家智能计算机研究开发中心

来源：

计算机学报 | 1997年 / 01期

关键词：

SAT问题，局部搜索，回溯算法，平均时间复杂性;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

ＳＡＴ问题在人工智能、ＶＬＳＩ设计和计算理论等领域有着广泛的应用背景．近年来，局部搜索算法在求解ＳＡＴ问题时得到了巨大的成功．本文除提出了多种改进策略之外，还对一般局部搜索算法进行了平均时间复杂性分析．假设ＳＡＴ问题中ＣＮＦ公式的子句数为ｎ，变量数为ｍ，每个子句长度为Ｌ，则局部搜索算法的平均时间复杂性分析结果为：当ｎ＜２Ｌｍ时，求解随机ＳＡＴ问题的算法复杂性为Ｏ（ｎＯ（１）Ｌ（１＋ｎ１＋ε／ｍ）），ε＞０，特别地，对于时的３－ＳＡＴ问题，算法复杂性为Ｏ（ｎ２（１＋ｎ１＋ε／ｍ））．当ｎｍ时，算法复杂性为Ｏ（ｎＬ）．

引用

页码：18 / 26

页数：9