Information Technology Reference
In-Depth Information
Fig. 6.1
Search for an
idempotent Latin square
(a)
(b)
(c)
0 ???
? 1 ??
??2 ?
???3
02??
? 1 ??
??2 ?
???3
0231
3102
1320
2013
⇒
⇒
The constraint propagation algorithm proceeds as follows. Constraints are used
actively to reduce domain sizes by filtering values that cannot take part in any solution.
Once the domain of a variable is reduced, more consistencies might be triggered.
Therefore the algorithm recomputes the candidate value sets of all its dependent
variables by detecting inconsistency w.r.t. the constraints. This process continues
recursively until there is no more propagation. It is worth noticing that constraint
propagation preserves all solutions to the original problem. There are several methods
for constraint propagation, with different power and cost.
Example 6.1
Let us see how we can find an idempotent Latin square of order 4.
Assumethecellatrow
i
and column
j
is
L
(
i
,
j
)
(0
≤
i
,
j
<
4). Then an
idempotent
Latin square has the property that, for each
i
,
L
(
i
,
i
)
=
i
. So, initially, the matrix is
like that of Fig.
6.1
a.
Now let us choose a value for the second cell on the first row, i.e.,
L
.
According to the properties of Latin squares, this cell can not take the value 0 or
1; it can only be 2 or 3. Assume that
L
(
0
,
1
)
2, as shown by Fig.
6.1
b. After this
choice, the domains of other variables become smaller. For instance,
L
(
0
,
1
)
=
(
0
,
2
)
can
only be 1 or 3.
If the reasoning of the algorithm is powerful, we may find that there is only
one value for
L
(
0
,
2
)
. It can not be 1. Otherwise, we have
L
(
0
,
3
)
=
3. This will
(
,
)
=
(
,
)
=
contradict with the fact that
L
3. After
similar reasoning (constraint propagation), we get the solution as shown by Fig.
6.1
c.
3
3
3. So we conclude that
L
0
2
6.1.3 Symmetry Breaking
For a constraint solving problem, a
symmetry
is a one to one mapping (bijection) on
variables that preserves solutions and non-solutions. We say two solutions or search
states are
isomorphic
if there is a symmetry mapping one of them to the other.
Since isomorphism is caused by symmetry, in the remainder of the chapter, we use
symmetry breaking and isomorphism elimination without distinction.
It has long been recognized that symmetries can cause significant problems to
systematic solvers that unnecessarily explore redundant parts of the search tree. As a
result, symmetry breaking becomes a vital technique in CSP. The goal of symmetry
breaking is to avoid exploring as much as possible two isomorphic search states,
since the results in both cases must be the same.
There are mainly two approaches to symmetry breaking for a CSP problem.
One is to statically add symmetry breaking constraints before search starts, thereby
Search WWH ::
Custom Search