QQ客服 官方微博 反馈留言

	Focused Random Walk with Configuration Checking and Break Minimum for Satisfiability
	Luo, Chuan ; Cai, Shaowei ; Wu, Wei ; Su, Kaile
	2013
关键词	LOCAL SEARCH VERTEX COVER SAT ALGORITHM
英文摘要	Stochastic local search (SLS) algorithms, especially those adopting the focused random walk (FRW) framework, have exhibited great effectiveness in solving satisfiable random 3-satisfiability (3-SAT) instances. However, they are still unsatisfactory in dealing with huge instances, and are usually sensitive to the clause-to-variable ratio of the instance. In this paper, we present a new FRW algorithm dubbed FrwCB, which behaves more satisfying in the above two aspects. The main idea is a new heuristic called CCBM, which combines a recent diversification strategy named configuration checking (CC) with the common break minimum (BM) variable-picking strategy. By combining CC and BM in a subtle way, CCBM significantly improves the performance of FrwCB, making FrwCB achieve state-of-the-art performance on a wide range of benchmarks. The experiments show that FrwCB significantly outperforms state-of-the-art SLS solvers on random 3-SAT instances, and competes well on random 5-SAT, random 7-SAT and structured instances.; Computer Science, Theory & Methods; Logic; EI; CPCI-S(ISTP); 0
语种	英语
DOI标识	10.1007/978-3-642-40627-0_37
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/405778]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Luo, Chuan,Cai, Shaowei,Wu, Wei,et al. Focused Random Walk with Configuration Checking and Break Minimum for Satisfiability. 2013-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。