%0 Journal Article
%T A Node Cost Model in Solving Binary Constraint Satisfaction Problems<br>二元约束满足问题求解的结点开销模型
%A XUE Han-hong
%A CAI Qing-sheng
%A <br>薛瀚宏
%A 蔡庆生
%J 软件学报
%D 1998
%I 
%X 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.
%K Constraint satisfaction
%K solving cost
%K phase transition
%K solving heuristics<br>约束满足，求解开销，相变，求解启发式.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=872EB7A134919A0700BC8DF73011CB05&yid=8CAA3A429E3EA654&vid=9CF7A0430CBB2DFD&iid=59906B3B2830C2C5&sid=55434AEC30CBAE6B&eid=BD0BCC5CD284A664&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=14