可满足性问题研究进展
来源：计算机应用与软件杂志2025年第10期北京时间：
作者：赵星宇, 王晓峰, 庞立超, 杨易, 杨澜
摘要：可满足性问题是一种NP完全问题,被广泛运用于人工智能和机器学习等研究方面。基于近年来对可满足性问题的研究,对可满足性问题的定义与因子图的特征进行介绍;从可满足性问题的结构特征入手,分类介绍相变、树宽与树分解、结构熵等;将求解算法分为四类(完备性算法、信息传播算法、局部搜索算法和智能优化算法)分别进行归纳;分析可满足性问题的各类实际应用;对可满足性问题研究的发展趋势进行展望与总结。
关键词：可满足性问题, 结构特征, 局部搜索算法, 信息传播算法
