[1]谷文祥,朱磊,黄平,等.可满足问题中的模型计数[J].智能系统学报,2012,7(1):33-39.
GU Wenxiang,ZHU Lei,HUANG Ping,et al.The model counting of a satisfiability problem[J].CAAI Transactions on Intelligent Systems,2012,7(1):33-39.
点击复制
GU Wenxiang,ZHU Lei,HUANG Ping,et al.The model counting of a satisfiability problem[J].CAAI Transactions on Intelligent Systems,2012,7(1):33-39.
可满足问题中的模型计数
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
7
期数:
2012年第1期
页码:
33-39
栏目:
学术论文—人工智能基础
出版日期:
2012-02-25
- Title:
- The model counting of a satisfiability problem
- 文章编号:
- 1673-4785(2012)01-0033-07
- Keywords:
- artificial intelligence; constraint satisfaction problem; propositional satisfiability problem; model counting
- 分类号:
- TP18
- 文献标志码:
- A
- 摘要:
- 模型计数问题是指计算给定问题的解的个数，这是一类比决策更困难的问题，也是人工智能领域研究的一个热点问题.对模型计数问题的研究不仅可以提高算法的求解效率，更能促进对问题困难本质的了解.以可满足问题（命题可满足（SAT）和约束可满足问题（CSP））为例，从精确算法和近似求解两方面综述了模型计数问题的研究现状，重点介绍了相关概念以及各个算法之间的优缺点，并提出了有待解决的开放性问题，对模型计数问题的研究予以了总结和展望.
- Abstract:
- A model counting problem refers to computing the number of solutions for a given problem which is harder than the decisionmaking problem. Model counting problems are also a hot topic in the field of artificial intelligence. Research on model counting problems can not only improve the efficiency of an algorithm, but also enhance the understanding of the nature of hard problems. Taking a satisfiability problem in propositional logic, known as an SAT, and a constraint satisfaction problem (CSP) as an example, a model counting problem was reviewed from two aspects: an exact algorithm and approximate algorithm. For each aspect, the development and related concepts along with the advantages and disadvantages were emphasized. Moreover, this paper proposed some unsolved questions of the model counting and gave a summary and outlook of the research on model counting.
- 参考文献/References:
-
［1］COOK S A. The complexity of theoremproving procedures［C］//Proceedings of the Third Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 1971: 151158.
［2］VALIANT L G. The complexity of computing the permanent［J］. Theoretical Computer Science, 1979, 8(2): 189201.
［3］DARWICHE A. The quest for efficient probabilistic inference［R］. Edinburgh, UK: IJCAI, 2005.
［4］DUBOIS O. Counting the number of solutions for instances of satisfiability［J］. Theoretical Computer Science, 1991, 81(1): 4964.
［5］ZHANG Wenhui. Number of models and satisfiability of sets of clauses［J］. Theoretical Computer Science, 1996, 155(1): 277288.
［6］BIRNBAUM E, LOZINSKII E L. The good old DavisPutnam procedure helps counting models［J］. Journal of Artificial Intelligence Research, 1999, 10(1): 457477.
［7］BAYARDO R J Jr, PEHOUSHEK J D. Counting models using connected components［C］//Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence. Austin, USA, 2000: 157162.
［8］SANG T, BACCHUS F, BEAME P, et al. Combining component caching and clause learning for effective model counting［C/OL］. ［20110720］. http://cs.rochester.edu/~kautz/papers/modelcountsat04.pdf.
［9］THURLEY M. SharpSAT: counting models with advanced component caching and implicit BCP［M］//BIERE A, GOMES C P. Theory and Applications of Satisfiability Testing. Seattle, USA: Springer, 2006: 424429.
［10］DAVIES J, BACCHUS F. Using more reasoning to improve #SAT solving［C］//Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada, 2007: 185190.
［11］YIN Minghao, LIN Hai, SUN Jigui. Counting models using extension rules［C］//Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada, 2007: 19161917.
［12］DARWICHE A. New advances in compiling CNF into decomposable negation normal form［C］//Proceedings of the 16th Eureopean Conference on Artificial Intelligence. Valencia, Spain, 2004: 328332.
［13］WEI W, SELMAN B. A new approach to model counting［M］//FAHIEM B, WALSH T. Theory and Applications of Satisfiability Testing. St.Andrews, UK: Springer, 2005: 324339.
［14］WEI W, ERENRICH J, SELMAN B. Towards efficient sampling: exploiting random walk strategies［C］//Proceedings of the 19th National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence. San Jose, USA, 2004: 670676.
［15］GOMES C P, HOFFMANN J, SABHARWAL A, et al. From sampling to model counting［C］//Proceedings of the 20th International Joint Conference on Artificial Intelligence. San Francisco, USA: Morgan Kaufmann Publishers Inc, 2007: 22932299.
［16］GOMES C P, SABHARWAL A, SELMAN B. Model counting: a new strategy for obtaining good bounds［C］//Proceedings of the TwentyFirst National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference. Boston, USA, 2006: 5461.
［17］ANGELSMARK O, JONSSON P, LINUSSON S, et al. Determining the number of solutions to binary CSP instances［C］//Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming. Ithaca, USA, 2002: 327340.
［18］ANGELSMARK O, JONSSON P. Improved algorithms for counting solutions in constraint satisfaction problems［C］//Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming. Kinsale, Ireland, 2003: 8195.
［19］FAVIER A, GIVRY S D, JEGOU P. Exploiting problem structure for solution counting［C］//Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming. Lisbon, Portugal, 2009: 335343.
［20］GOMES C P, Van HOEVE W J, SABHARWAL A, et al. Counting CSP solutions using generalized XOR constraints［C］//Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada, 2007: 204209.
［21］XU Ke, LI Wei. Exact phase transitions in random constraint satisfaction problems［J］. Journal of Artificial Intelligence Research, 2000, 12: 93103.
［22］HUANG Ping, YIN Minghao, XU Ke. Exact phase transitions and approximate algorithm of #CSP［C/OL］. ［20110720］. http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3508/4142.
- 相似文献/References:
-
[1]李德毅.网络时代人工智能研究与发展[J].智能系统学报,2009,4(1):1.
LI De-yi.AI research and development in the network age[J].CAAI Transactions on Intelligent Systems,2009,4():1.
[2]赵克勤.二元联系数A+Bi的理论基础与基本算法及在人工智能中的应用[J].智能系统学报,2008,3(6):476.
ZHAO Ke-qin.The theoretical basis and basic algorithm of binary connection A+Bi and its application in AI[J].CAAI Transactions on Intelligent Systems,2008,3():476.
[3]徐玉如,庞永杰,甘?? 永,等.智能水下机器人技术展望[J].智能系统学报,2006,1(1):9.
XU Yu-ru,PANG Yong-jie,GAN Yong,et al.AUV—state-of-the-art and prospect[J].CAAI Transactions on Intelligent Systems,2006,1():9.
[4]王志良.人工心理与人工情感[J].智能系统学报,2006,1(1):38.
WANG Zhi-liang.Artificial psychology and artificial emotion[J].CAAI Transactions on Intelligent Systems,2006,1():38.
[5]赵克勤.集对分析的不确定性系统理论在AI中的应用[J].智能系统学报,2006,1(2):16.
ZHAO Ke-qin.The application of uncertainty systems theory of set pair analysis (SPU)in the artificial intelligence[J].CAAI Transactions on Intelligent Systems,2006,1():16.
[6]秦裕林,朱新民,朱? 丹.Herbert Simon在最后几年里的两个研究方向[J].智能系统学报,2006,1(2):11.
QIN Yu-lin,ZHU Xin-min,ZHU Dan.Herbert Simons two research directions in his lost years[J].CAAI Transactions on Intelligent Systems,2006,1():11.
[7]谷文祥,李 丽,李丹丹.规划识别的研究及其应用[J].智能系统学报,2007,2(1):1.
GU Wen-xiang,LI Li,LI Dan-dan.Research and application of plan recognition[J].CAAI Transactions on Intelligent Systems,2007,2():1.
[8]杨春燕,蔡 文.可拓信息-知识-智能形式化体系研究[J].智能系统学报,2007,2(3):8.
YANG Chun-yan,CAI Wen.A formalized system of extension information-knowledge-intelligence[J].CAAI Transactions on Intelligent Systems,2007,2():8.
[9]赵克勤.SPA的同异反系统理论在人工智能研究中的应用[J].智能系统学报,2007,2(5):20.
ZHAO Ke-qin.The application of SPAbased identicaldiscrepancycontrary system theory in artificial intelligence research[J].CAAI Transactions on Intelligent Systems,2007,2():20.
[10]王志良,杨?? 溢,杨?? 扬,等.一种周期时变马尔可夫室内位置预测模型[J].智能系统学报,2009,4(6):521.[doi:10.3969/j.issn.1673-4785.2009.06.009]
WANG Zhi-liang,YANG Yi,YANG Yang,et al.A periodic time-varying Markov model for indoor location prediction[J].CAAI Transactions on Intelligent Systems,2009,4():521.[doi:10.3969/j.issn.1673-4785.2009.06.009]
备注/Memo
收稿日期： 2011-07-25.
网络出版时间： 2012-02-17.
基金项目：国家自然科学基金资助项目(61070084,60573067,60803102).
通信作者：黄平.????????E-mail:huangp218@nenu.edu.cn.
作者简介：
谷文祥，男，1947年生，教授，博士生导师，主要研究方向为智能规划与规划识别、形式语言与自动机、模糊数学及其应用.参与或承担多项国家自然科学基金项目、教育部重点项目、省科委项目，发表学术论文100余篇.
朱磊，男，1987年生，硕士研究生，主要研究方向为智能规划、智能信息处理.
黄平，女，1986年生，硕士研究生，主要研究方向为智能规划与规划识别.
更新日期/Last Update:
2012-05-07