您当前所在位置: 首页 > 学者

许可

  • 35浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 137下载

  • 0评论

  • 引用

期刊论文

Random constraint satisfaction: Easy generation of hard (satisfiable) instances

许可Ke Xu a Frédéric Boussemart b Fred Hemery b Christophe Lecoutre b

Artificial Intelligence 171(2007)514-534,-0001,():

URL:

摘要/描述

In this paper, we show that the models of random CSP instances proposed by Xu and Li [K. Xu, W. Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research 12 (2000) 93-103; K. Xu, W. Li, Many hard examples in exact phase transitions with application to generating hard satisfiable instances, Technical report, CoRR Report cs.CC/0302001, Revised version in Theoretical Computer Science 355 (2006) 291-302] are of theoretical and practical interest. Indeed, these models, called RB and RD, present several nice features. First, it is quite easy to generate random instances of any arity since no particular structure has to be integrated, or property enforced, in such instances. Then, the existence of an asymptotic phase transition can be guaranteed while applying a limited restriction on domain size and on constraint tightness. In that case, a threshold point can be precisely located and all instances have the guarantee to be hard at the threshold, i.e., to have an exponential tree-resolution complexity. Next, a formal analysis shows that it is possible to generate forced satisfiable instances whose hardness is similar to unforced satisfiable ones. This analysis is supported by some representative results taken from an intensive experimentation that we have carried out, using complete and incomplete search methods.

【免责声明】以下全部内容由[许可]上传于[2010年02月05日 10时13分01秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。

我要评论

全部评论 0

本学者其他成果

    同领域成果