Value Ordering Heuristic for Solving Algorithm
Based on the AC-4 Algorithm
Zhan-shan Li
School of Computer Science and Technology, Jilin
University, Changchun, P.R. China
Key Laboratory of Symbolic Computation and Knowledge
Engineering of Ministry of Education, Jilin University,
Changchun, P.R. China
Email:lizs@jlu.edu.cn
Hui-ying Du
School of Computer Science and Technology, Jilin
University, Changchun, P.R. China
Key Laboratory of Symbolic Computation and Knowledge
Engineering of Ministry of Education, Jilin University,
Changchun, P.R. China
Email:dhyingican@163.com
Shi-mei Xing
School of Computer Science and Technology, Jilin University,
Changchun, P.R. China
Key Laboratory of Symbolic Computation and Knowledge
Engineering of Ministry of Education, Jilin University,
Changchun, P.R. China
Fan-wei Meng
School of Computer Science and Technology, Jilin University,
Changchun, P.R. China
Abstract—We have studied the AC-4 algorithm and then present
value ordering heuristic for solving algorithm BT-MSV which is
based on the AC-4 algorithm. This algorithm takes full
advantage of supported information which is recorded in the
data structure of the AC-4 algorithm during the process of arc
consistency. The algorithm sorts the value of the variables’
domain according to the supported information. So this order
enforces the algorithm to extend the values of variables which
have more support. In this way, the efficiency of the algorithm
can be improved. The result of our experiments shows that our
algorithm has much more advantage over other solving
algorithms.
Keywords- arc consistency; AC-4; value ordering heuristic;
solving algorithm;
I. INTRODUCTION
Constraint Satisfaction Problems (CSP) usually can model
the real-world problems into a finite set of variables and a set
of value domain for variables while the assignments to the
variables are restricted by the constraints. A constraint usually
consists of a list of variables and a list of triple which is the
values the variables can take. A solution to a CSP is an
assignment of values to variables satisfying all constraints.
Most problems of the real-world can be effectively viewed
as constraint satisfaction problems (CSP), then use the
constraint solving technology to solve, such as temporal
reasoning, spatial analysis, symbolic reasoning, diagnosis,
decision support, scheduling, hardware design and certification.
These make the constraint satisfaction problems become an
important problem in artificial intelligence area. Constraint
satisfaction problem usually is NP-hard. Nevertheless, there are
a lot of efficient solving technologies. In most solving
algorithms, BT (backtracking algorithm) is a complete core
solving algorithm and then a lot of related algorithms were
proposed [4,14]. When choose a variable to initialize, the BT
algorithm adopts the depth-first strategy. When the constraint
checking fails, the backtracking mechanism, which is
integrated with consistency technology to improve the
efficiency of the algorithm, is triggered. Arc consistency is a
very efficient consistent technology, such as AC-3 [9], AC-4
[1,6], AC-6 [3], AC-7 [15], AC-2001 [9] and so on. They all
can remove the values that cannot appear in any solution to
reduce the search space before or during searching. In 1994,
Daniel Sabin and Eugene C.Freuder proposed MAC
(Maintaining Arc Consistency) algorithm based on AC-4 in [2].
It was studied further in [10]. The MAC algorithm has
characteristics of highly solving efficiency and low cost of
space, so that this algorithm becomes the main search
technology for the constraint satisfaction problems.
In this paper, we propose a new algorithm, value ordering
heuristic for solving algorithm BT-MSV which is based on the
data structure used in AC-4. This algorithm takes full
advantage of the information that is recorded in data structure.
There is counter for each arc-value pair, counter[x
i
,v
i
,x
j
],
representing the number of values in the domain of x
j
supporting (x
i
,a), the value a for x
i
. After the original problem
is made to full arc consistency by the AC-4, we can easily get
the number of every pair (x
i
,v
i
)’s support which is for other
variables according to the counter, counter[x
i
,v
i
,x
j
], then sort
the values in the variables’ domain according to number of
support and arrange the value whose supports are the most in
the front of the domain. So that the algorithm will be forced to
expand the value which has the more supports, that is, it more
likely be a part of solution. Through this way, we can avoid
expanding the values which can not be expanded to a global
solution, so that we can reach the aim of improving the
efficiency of solving algorithm.
II. B
ACKGROUND
Constraint Satisfaction Problems is usually represented as a
triple P=(X,D,C), X={x
1
,x
2
,…,x
m
} is a finite set of variables, a
set of domains D={D
1
,D
2
,…D
n
}, where D
i
(i∈1…n) is the finite
978-1-4244-5874-5/10/$26.00 ©2010 IEEE