.png){kind=icon}
返回
A comparative runtime analysis of heuristic algorithms for satisfiability problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2008.11.002.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 0((k - 1)(n)), and presents a k-SAT instance that has Theta((k - 1)(n)) expected runtime bound. (C) 2008 Elsevier B.V. All rights reserved.
Keyword:
Boolean satisfiability
Heuristic algorithms
Random walk
(1+1) EA
Hybrid algorithm
Expected first hitting time
Runtime analysis
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
引用论文
.png){kind=icon}
Molecular identification of white morphotype strains of endophytic fungi from Pinus tabulaeformis
PREAI
分享收藏
查看更多内容