An Extended Rcsp Generating Model and its Application
Yonggang Zhang, Jigui Sun, Jian Gao · 2006
In recent years there has been plenty of interest in random constraint satisfaction problem, both from an experimental and a theoretical point of view. In this paper we study and analyze the four popular problem instance generating models, and present the extended model B+based on the most used model B, which has the different domains and constraint tightness meeting some probability distribution function. In the subsequent section we give the relation matrix version of backtracking integrated forward checking algorithms, and introduce the implementation of instances generator and solver based on the new model. Finally we show the experiment results and conclude the paper, point that our extended model B+has the common phase transition region with the transitional models and it has the advantage of being suited to the testing of heuristic based constraint solving algorithms, such as variables selection heuristic algorithms