[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.
点击复制

可满足问题中的模型计数

参考文献/References:
[1]COOK S A. The complexity of theoremproving procedures[C]//Proceedings of the Third Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 1971: 151158.
[2]VALIANT L G. The complexity of computing the permanent[J]. Theoretical Computer Science, 1979, 8(2): 189201.
[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): 4964.
[5]ZHANG Wenhui. Number of models and satisfiability of sets of clauses[J]. Theoretical Computer Science, 1996, 155(1): 277288. 
[6]BIRNBAUM E, LOZINSKII E L. The good old DavisPutnam procedure helps counting models[J]. Journal of Artificial Intelligence Research, 1999, 10(1): 457477.
[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: 157162.
[8]SANG T, BACCHUS F, BEAME P, et al. Combining component caching and clause learning for effective model counting[C/OL]. [20110720]. http://cs.rochester.edu/~kautz/papers/modelcountsat04.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: 424429.
[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: 185190.
[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: 19161917.
[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: 328332.
[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: 324339.
[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: 670676.
[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: 22932299.
[16]GOMES C P, SABHARWAL A, SELMAN B. Model counting: a new strategy for obtaining good bounds[C]//Proceedings of the TwentyFirst National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference. Boston, USA, 2006: 5461.
[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: 327340.
[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: 8195.
[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: 335343.
[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: 204209.
[21]XU Ke, LI Wei. Exact phase transitions in random constraint satisfaction problems[J]. Journal of Artificial Intelligence Research, 2000, 12: 93103.
[22]HUANG Ping, YIN Minghao, XU Ke. Exact phase transitions and approximate algorithm of #CSP[C/OL]. [20110720]. 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):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(1):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(1):9.
[4]王志良.人工心理与人工情感[J].智能系统学报,2006,1(1):38.
 WANG Zhi-liang.Artificial psychology and artificial emotion[J].CAAI Transactions on Intelligent Systems,2006,1(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(1):16.
[6]秦裕林,朱新民,朱 丹.Herbert Simon在最后几年里的两个研究方向[J].智能系统学报,2006,1(2):11.
 QIN Yu-lin,ZHU Xin-min,ZHU Dan.Herbert Simons two research directions in his lost years[J].CAAI Transactions on Intelligent Systems,2006,1(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):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(1):8.
[9]赵克勤.SPA的同异反系统理论在人工智能研究中的应用[J].智能系统学报,2007,2(5):20.
 ZHAO Ke-qin.The application of SPAbased identicaldiscrepancycontrary system theory in artificial intelligence research[J].CAAI Transactions on Intelligent Systems,2007,2(1):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(1):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
Copyright @ 《 智能系统学报》 编辑部
地址:(150001)黑龙江省哈尔滨市南岗区南通大街145-1号楼 电话:0451- 82534001、82518134