计算机应用与软件2025，Vol.42Issue(10)：13-23,52,12.DOI:10.3969/j.issn.1000-386x.2025.10.003
可满足性问题研究进展
RESEARCH PROGRESS OF BOOLEAN SATISFIABILITY PROBLEM
摘要
Abstract
The Boolean satisfiability problem is a kind of NP-complete problem,which is widely-used in artificial intelligence and machine learning.Based on the research of satisfiability problem in recent years,the definition of satisfiability problem and the feature of factor graph were introduced.From the structural characteristics of satisfiability problem,phase transformation,tree width and decomposition,structural entropy and so on were introduced.The algorithms were divided into four categories(completeness algorithm,message passing algorithm,stochastic local search algorithm and intelligent optimization algorithm).The practical application of satisfiability problem was analyzed.The development trend of satisfiability research was prospected and summarized.关键词
可满足性问题/结构特征/局部搜索算法/信息传播算法Key words
Satisfiability problem/Structure characteristics/Local search algorithm/Message passing algorithm分类
信息技术与安全科学引用本文复制引用
赵星宇,王晓峰,庞立超,杨易,杨澜..可满足性问题研究进展[J].计算机应用与软件,2025,42(10):13-23,52,12.基金项目
国家自然科学基金项目(62062001) （62062001）
宁夏青年拔尖人才项目. （）
