Information Technology Reference
In-Depth Information
variable. Two dimension array domain[][] is used to record state of each assigned
value of each variable: belonging to current domain or has been deleted by some
instantiated variable. The values which belong to current domain are chained
together with the suffix, as well as those values have been deleted by the same
variable instantiation.
The algorithm implements exhaustive search, thus has exponential time
complexity. The space complexity is O(n(n+d)),where n is the number of
variable, d is the size of variable domain(suppose all variables have equal domain
size).
IBMD has been used to test a series of examples and compared with some
other algorithms, which includes backtracking(BT), conflict-based
backtracking(CBJ), the algorithm only adopting most-constrained-first
method(MCF) and the algorithm only adopting most-constrained-first and
domain filtering methods(MD). The experimental results show that IBMD is
superior to these algorithms to some extent. For example, N queen's problem is
solved with IBMD on the workstation sparc-1. For N =100, IBMD algorithm
takes less 2 seconds. On the same machine, BT algorithm takes more than 10
seconds for 2 queen's problem. For N ≥ 30, BT algorithm takes several hours at
least. For N=50 MCF algorithm takes more than 10 seconds and takes several
hours for N≥60. For N queen's problem, MD algorithm and IBMD algorithm
nearly have the same performance and IBMD is slightly superior to MD. There
are several reasons here. First of all, in N queen's problem, there is little one-step
backtracking. Domain filtering strategy can reduce much “out-layer”
inconsistency. However “deep-layer” inconsistency involves many other
variables. Secondly the extra cost of IBMD are less than MD. Table 3.1 shows
the execution time of different algorithms operating on N queen's problem.
We have also tested the graph-coloring case. When the connection degree of
vertexes is small(≤7), backtracking is hardly used and the IBMD performance is
equivalent to MD performance. When increasing connection degree, IBMD
performance is obviously superior to MD.
Compare the IBMD algorithm with other similar algorithms as follows.
(1) Compared with backjumping(BJ)
BJ can only backjump to latest variable caused by inconsistent variables. But if
the latest variable has already tried all values, backtracking is to be the same as
common backtracking. Therefore BJ is very limited in improvement of
