Information Technology Reference
In-Depth Information
performance. However, IBMD can backtrack continuously until find a variable,
which is correlated with the inconsistency and not all values have been tried.
(2) Compared with graph-based backjumping
The topology connection of constraint network is an approximation of actual data
dependence. Under particular context, two graph-relevant variables probably will
not influence each other. And what IBMD utilized is actual influence.
(3) Compared with conflict-based backjumping
Prosser,et al. proposed some improvement of backjumping on IJCAI conference
in 1993, such as CBJ (Conflict-based BackJumping). The starting points of
IBMD and CBJ are similar, but in realizing they differ a lot. CBJ has a drawback.
Each variable has a dependence variable set. When backjumping is done once,
the merge of sets should be carried on, therefore CBJ causes very large time cost.
However, this problem does not exist in IBMD algorithm.
A aspect that IBMD is superior to all other algorithms described above is that
IBMD combines the most-constrained-first and domain filtering strategies
together.
Table 3.1 Execution time of running N queen's problem(unit :sec)
n
BT
CBJ
IBMD
n
BT
CBJ
IBMD
8
0.0
0.0
0.0
26
324.0
323.6
0.0
9
0.0
0.0
0.0
27
389.4
389.5
0.0
10
0.0
0.0
0.0
28
2810.2
2799.0
0.0
11
0.0
0.0
0.0
29
1511.1
1517.2
0.0
12
0.1
0.0
0.0
30
*
*
0.1
13
0.0
0.1
0.0
40
*
*
0.3
14
0.5
0.5
0.0
50
*
*
1.8
15
0.4
0.5
0.0
60
*
*
0.7
16
3.3
3.7
0.0
70
*
*
1.4
17
1.9
2.2
0.0
80
*
*
1.0
18
16.9
17.9
0.0
90
*
*
1155.7
19
1.1
1.3
0.0
100
*
*
1.8
20
101.6
105.5
0.0
110
*
*
158.9
21
4.6
4.7
0.0
120
*
*
*
22
1068.1
1048.4
0.0
130
*
*
11.5
23
16.2
16.2
0.0
140
*
*
*
24
290.5
289.6
0.0
160
*
*
7.1
25
35.8
35.9
0.0
200
*
*
14.0
note: “*” represents the time ≥2 hours
