Solving quantified constraint satisfaction problems with value selection rules  

作　　者：Jian Gao Jinyan Wang Kuixian Wu Rong Chen 

机构地区：[1]College of Information Science and Technology,Dalian Maritime University,Dalian,116026,China [2]Logistics Research Institute,Dalian Maritime University,Dalian,116026,China [3]College of Computer Science and Information Engineering,Guangxi Normal University,Guilin,541004,China

出　　处：《Frontiers of Computer Science》2020年第5期153-163,共11页中国计算机科学前沿（英文版）

基　　金：We would like to thank Dr.Peter Nightingale for the source code of QCSP-Solve.The work described in this paper was supported by the National Natural Science Foundation of China(Granted Nos.61972063,61763003,61672122,61602077,61402070);the Fundamental Research Funds for the Central Universities(3132019029,3132019355).

摘　　要：Solving a quantified constraint satisfaction problem(QCSP)is usually a hard task due to its computational complexity.Exact algorithms play an important role in solving this problem,among which backtrack algorithms are effective.In a backtrack algorithm,an important step is assigning a variable by a chosen value when exploiting a branch,and thus a good value selection rule may speed up greatly.In this paper,we propose two value selection rules for existentially and universally quantified variables,respectively,to avoid unnecessary searching.The rule for universally quantified variables is prior to trying failure values in previous branches,and the rule for existentially quantified variables selects the promising values first.Two rules are integrated into the state-of-the-art QCSP solver,i.e.,QCSP-Solve,which is an exact solver based on backtracking.We perform a number of experiments to evaluate improvements brought by our rules.From computational results,we can conclude that the new value selection rules speed up the solver by 5 times on average and 30 times at most.We also show both rules perform well particularly on instances with existentially and universally quantified variables occurring alternatively.

关 键 词：quantified CSP BACKTRACKING value selection fail-first principle 

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