Zhou Yuren, He Jun, Nie Qing
School of Computer Science and Engineering, South China University of Technology, Guangzhou 510640, China.
Artif Intell. 2009 Feb;173(2):240-257. doi: 10.1016/j.artint.2008.11.002.
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 Theta((k - 1)(n)) expected runtime bound.
可满足性问题是一个基本的核心NP完全问题。近年来，人们开发了许多启发式算法来解决这个问题，并且进行了许多实验来评估和比较不同启发式算法的性能。然而，严格的理论分析和比较却很少见。本文分析并比较了三种基本启发式算法的期望运行时间：随机游走算法、(1+1)进化算法和混合算法。这些启发式算法在两个2-SAT实例上的运行时间分析表明，这些启发式算法的期望运行时间可能是指数时间或多项式时间。此外，这些启发式算法在解决不同的SAT实例时各有优缺点。它还证明了随机游走算法在任意k-SAT(k≥3)上的期望运行时间上界为O((k - 1)(n))，并给出了一个期望运行时间界为Θ((k - 1)(n))的k-SAT实例。
