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...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.展开更多
基金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.
