期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2007
卷号：28
页码：517-557
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：In this paper, we study the possibility of designing non-trivial random CSP
models by exploiting the intrinsic connection between structures and
typical-case hardness. We show that constraint consistency, a notion that has
been developed to improve the efficiency of CSP algorithms, is in fact the key
to the design of random CSP models that have interesting phase transition
behavior and guaranteed exponential resolution complexity without putting much
restriction on the parameter of constraint tightness or the domain size of the
problem. We propose a very flexible framework for constructing problem instances
withinteresting behavior and develop a variety of concrete methods to construct
specific random CSP models that enforce different levels of constraint
consistency.
A series of experimental studies with interesting
observations are carried out to illustrate the effectiveness of introducing
structural elements in random instances, to verify the robustness of our
proposal, and to investigate features of some specific models based on our
framework that are highly related to the behavior of backtracking search
algorithms.
