AN EXTENDED RCSP GENERATING MODEL AND ITS APPLICATION
In recently 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.
Constraint programming RCSP constraint solving generating model testing
YONG-GANG ZHANG JI-GUI SUN JIAN GAO
College of Computer Science and Technology, Jilin University, Changchun 130012, China Key Laboratory for Symbolic Computation and Knowledge Engineering of Ministry of Education, Changchu
国际会议
2006 International Conference on Machine Learning and Cybernetics(IEEE第五届机器学习与控制论坛)
大连
英文
1522-1527
2006-08-13（万方平台首次上网日期，不代表论文的发表时间）