谷文祥，朱磊，黄平，殷明浩

(东北师范大学计算机科学与信息技术学院，吉林长春 130117)

可满足问题中的模型计数

谷文祥，朱磊，黄平，殷明浩

(东北师范大学计算机科学与信息技术学院，吉林长春 130117)

模型计数问题是指计算给定问题的解的个数，这是一类比决策更困难的问题，也是人工智能领域研究的一个热点问题.对模型计数问题的研究不仅可以提高算法的求解效率，更能促进对问题困难本质的了解.以可满足问题(命题可满足(SAT)和约束可满足问题(CSP))为例，从精确算法和近似求解两方面综述了模型计数问题的研究现状，重点介绍了相关概念以及各个算法之间的优缺点，并提出了有待解决的开放性问题，对模型计数问题的研究予以了总结和展望.

人工智能;约束可满足问题;命题可满足问题;模型计数

命题可满足问题(propositional satisfiability problem，SAT)的求解是近年来人工智能领域研究的热点问题，这类问题的计算复杂度是属于NP完全的［1］，也即意味着如果P≠NP成立，即无法在多项式时间内解决SAT问题.而模型计数问题是比这类决策问题更难解决的问题，它的计算复杂度是属于#P完全的.一些原本是多项式时间的决策问题的模型计数也是属于#P完全的，例如2SAT［2］.模型计数问题是指计算给定问题的解的个数，即使得公式值为真的不同的变量的赋值数.高效地解决模型计数问题对人工智能的很多领域都有着深远的影响，许多的概率推理如贝叶斯网络推理［3］等都可以转……