.png){kind=icon}
.png){kind=icon}
Return
A randomized diversification strategy for solving satisfiability problem with long clauses
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-016-0258-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Satisfiability problem (SAT) is a central problem in artificial intelligence due to its computational complexity and usefulness in industrial applications. Stochastic local search (SLS) algorithms are powerful to solve hard instances of satisfiability problems, among which CScoreSAT is proposed for solving SAT instances with long clauses by using greedy mode and diversification mode. In this paper, we present a randomized variable selection strategy to improve efficiency of the diversification mode, and thus propose a new SLS algorithm. We perform a number of experiments to evaluate the new algorithm comparing with the recently proposed algorithms, and show that our algorithm is comparative with others for solving random instances near the phase transition threshold.
Keywords:
SAT
local search
randomized diversification strategy
phase transition
long clause
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K