A comparative runtime analysis of heuristic algorithms for satisfiability problems.
A comparative runtime analysis of heuristic algorithms for satisfiability problems.
复制标题
可满足性问题的启发式算法的比较运行时分析
DOI：
10.1016/j.artint.2008.11.002
复制
发表时间：
2009-02
影响因子：
14.4
通讯作者：
Nie Q
中科院分区：
文献类型：
--
作者：
Zhou Y;He J;Nie Q
可满足性问题是一个基本的核心NP-完全问题。近年来，人们提出了许多启发式算法来解决这一问题，并通过大量的实验对不同启发式算法的性能进行了评估和比较。然而，严谨的理论分析和比较并不多见。分析比较了随机游走算法、(1+1)EA算法和混合算法三种基本启发式算法的预期运行时间。在两个2-SAT实例上对这些启发式算法的运行时间分析表明，这些启发式算法的预期运行时间可以是指数时间或多项式时间。此外，这些启发式算法在求解不同的SAT实例时也各有优缺点。证明了任意k-SAT(k≥3)上随机游走的期望运行时间上界为O((k−1)n)，并给出了一个具有Θ((k−1)n)期望运行时间上界的k-SAT实例.
The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT(k ≥ 3) is O((k − 1)n), and presents a k-SAT instance that has Θ((k − 1)n) expected runtime bound.
登录
查看更多内容
影响因子：
56.9
作者：
Mézard, M;Parisi, G;Zecchina, R
通讯作者：
Zecchina, R
影响因子：
3.7
作者：
HOEFFDING, W
通讯作者：
HOEFFDING, W
影响因子：
1
作者：
Braunstein, A;Mézard, M;Zecchina, R
通讯作者：
Zecchina, R
DOI：
10.1007/s10472-005-0421-9
发表时间：
2005-01-01
影响因子：
1.2
作者：
Hirsch, EA;Kojevnikov, A
通讯作者：
Kojevnikov, A
影响因子：
6.8
作者：
Lardeux, Frederic;Saubion, Frederic;Hao, Jin-Kao
通讯作者：
Hao, Jin-Kao