微信服务号

微信订阅号

2025年4月6日 12:59 星期日
首页 > 过刊浏览>1998年第9卷第12期 >922-926
PDF HTML阅读 XML下载 导出引用 引用提醒
二元约束满足问题求解的结点开销模型
作者:
基金项目:

本文研究得到国家自然科学基金和国家教委博士点基金资助.


A Node Cost Model in Solving Binary Constraint Satisfaction Problems
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [1]
    • |
  • 相似文献
    • | | |
  • 文章评论
    摘要:

    提出了在二元约束满足问题中以搜索结点个数为衡量标准的求解开销模型,该模型被应用于随机二元约束满足问题的求解开销相变分析中,并且比较了模型所导出的理论开销和实际中的搜索结点个数、约束检查次数、求解时间3种衡量标准的开销之间的相似性.在模型的基础上，探讨了求解启发式减少求解开销的作用，给出了一个新的变量选择启发式.

    Abstract:

    A model of evaluating cost by number of nodes searched in solving binary constraint satisfaction problems is introduced in this paper. It has been applied to the random binary constraint satisfaction problems to analyze the phase transition property of solving cost. The theoretical cost induced from the model is compared with those practical costs evaluated by number of nodes searched, number of constraints checked and time consumed respectively. Based on this model, the effect of using solving heuristics to reduce cost is discussed and a new variable ordering heuristic is given.

    参考文献
    1　 Detcher R, Meiri I. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelligence, 1994,68(2):211～241 2　 Prosser P. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 1996,81(1):81～109 3　 Gent I P, Walsh T. Easy problems are sometimes hard. Artificial Intelligence, 1994,70(1):335～345 4　 Williams C P, Hogg T. Exploiting the deep structure of constraint problems. Artificial Intelligence, 1994,70(1):73～118 5　 Prosser P. Binary constraint satisfaction problems: some are hard than others. In: Cohn A ed. Proceedings of ECAI-94. New York: John Wiley and Sons Inc., 1994. 95～99 6　 Crawford J M, Auton L D. Experimental results on the crossover point in satisfiability problems. In: Proceedings of the 11th National Conference on Artificial Intelligence. Menlo Park, Cambridge, London: AAAI Press/the MIT Press, 1993. 21～27 7　 Smith B M, Dyer M E. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 1996,81(1):155～181 8　 Gent I P, MacIntyre E, Prosser P et al. The constraintedness of search. In: Proceedings of the 13th National Conference on Artificial Intelligence and the 8th Innovative Applications of Artificial Intelligence Conference. Menlo Park, Cambridge, London: AAAI Press/the MIT Press, 1996. 246～252 9　 Haralick R M, Elliot G L. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 1980,14(2):263～313 10　 Haselbck A. Exploiting interchangeabilities in constraint satisfaction problems. In: Bajcsy Ruzena ed. Proceedings of the 13th International Joint Conference on Artificial Intelligence. San Mateo, California: Morgan Kaufumann Publishers, Inc., 1993. 282～287 11　 Frost D, Dechter R. In search of the best constraint satisfaction. In: Proceedings of the 12th National Conference on Artificial Intelligence. Menlo Park, Cambridge, London: AAAI Press/the MIT Press, 1994. 301～306 12　 Frost D, Dechter R. Dead-end driven learning. In: Proceedings of the 12th National Conference on Artificial Intelligence. Menlo Park, Cambridge, London: AAAI Press/the MIT Press. 1994. 294～300 13　 Smith B M. Phase transition and the mushy region in constraint satisfaction problems. In: Proceedings of ECAI-94. Amsterdam, Netherlands, 1994.100～104 14　 Sabin D, Freuder E. Contradicting conventional wisdom in constraint satisfaction. In: Alan Borning ed. Proceedings of PPCP'94: 2nd Workshop on Principles and Practice of Constraint Programming. Seattle, WA, 1994
    相似文献
    引证文献
引用本文

薛瀚宏,蔡庆生.二元约束满足问题求解的结点开销模型.软件学报,1998,9(12):922-926

复制
分享
文章指标
  • 点击次数:3570
  • 下载次数: 4105
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1997-07-25
  • 最后修改日期:1997-11-12
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19794055位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号