二元约束满足问题求解的结点开销模型  

A Node Cost Model in Solving Binary Constraint Satisfaction Problems

作　　者：薛瀚宏[1] 蔡庆生[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系

出　　处：《软件学报》1998年第12期922-926,共5页Journal of Software

基　　金：国家自然科学基金;国家教委博士点基金

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

关 键 词：约束满足 求解开销 求解启发式 机器学习 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]