168
A. Bernasconi et al.
Fig. 7.3 Canceling a literal
from a multiple choice using
step 2 of Rule 1. Literals are
denoted by a, b, c, d, e, f, g.
Literal c in cells v j , v h is
canceled from v j
a b
c d
d g
d f
a b
c e
v h
v j
v k
An example of application of step 2 of Rule 1 is shown in Fig. 7.3. Note that a
literal cancelation from L j may induce a further cancelation in an adjacent cell. In
the example of Fig. 7.3, if all the cells adjacent to v h except for v j do not contain
the literal c, the cancelation of c from L j induces the cancelation of c from L h if
step 1 of Rule 1 is subsequently applied to v h .
As suggested in [21], before running any algorithm for solving MPA the sets L i
may be reduced using Rule 1 through a scanning of the lattice. Moreover, several
successive scans may be applied for further reduction until no change occurs in a
whole scan. These operations constitute the first phase of any algorithm. Then, as
the problem is computationally intractable, a heuristic must be applied. The one
proposed in [21] is the simplest possible:
– scan the lattice row-wise: for any vertex v i reduce the associated set of literals
L i to just one of its elements chosen at random;
– for any vertex v i not yet included in an area, build a tree T i spanning the maximal
connected subgraph whose vertices hold the same label of T i and include the
vertices of T i in a new area.
Here we propose two new heuristics that can be applied after the preliminary phase
consisting of the application of Rule 1 to the whole lattice. Recall that we can
represent an N ×M lattice as a grid G. For simplicity a vertex of G corresponding to
cell (i, j ) will be indicated with an integer h, with 1 ≤ h ≤ NM. The first heuristic
called HMPA1 builds each area of G as a BFS tree, looking for a subset of adjacent
vertices that share a same literal and assigning that literal to them. The algorithm
makes use of an internal queue Z to store the vertices that will eventually become
the roots of the BFS trees, and of five vectors A, R, L, Q, P of NM elements with
the following contents for each vertex h:
A(h): number a assigned to the area A a to which vertex h belongs, with a =
1, 2, . . . ;
R(h): root of the BFS tree of A a ;
L(h): literal assigned to vertex h;
Q(h): indicator that vertex h is present (Q(h) = 1) or not (Q(h) = 0) in the queue
Z;
P (h): pointer to the ordered subset L h of literals associated with vertex h.
A. Bernasconi et al.
Fig. 7.3 Canceling a literal
from a multiple choice using
step 2 of Rule 1. Literals are
denoted by a, b, c, d, e, f, g.
Literal c in cells v j , v h is
canceled from v j
a b
c d
d g
d f
a b
c e
v h
v j
v k
An example of application of step 2 of Rule 1 is shown in Fig. 7.3. Note that a
literal cancelation from L j may induce a further cancelation in an adjacent cell. In
the example of Fig. 7.3, if all the cells adjacent to v h except for v j do not contain
the literal c, the cancelation of c from L j induces the cancelation of c from L h if
step 1 of Rule 1 is subsequently applied to v h .
As suggested in [21], before running any algorithm for solving MPA the sets L i
may be reduced using Rule 1 through a scanning of the lattice. Moreover, several
successive scans may be applied for further reduction until no change occurs in a
whole scan. These operations constitute the first phase of any algorithm. Then, as
the problem is computationally intractable, a heuristic must be applied. The one
proposed in [21] is the simplest possible:
– scan the lattice row-wise: for any vertex v i reduce the associated set of literals
L i to just one of its elements chosen at random;
– for any vertex v i not yet included in an area, build a tree T i spanning the maximal
connected subgraph whose vertices hold the same label of T i and include the
vertices of T i in a new area.
Here we propose two new heuristics that can be applied after the preliminary phase
consisting of the application of Rule 1 to the whole lattice. Recall that we can
represent an N ×M lattice as a grid G. For simplicity a vertex of G corresponding to
cell (i, j ) will be indicated with an integer h, with 1 ≤ h ≤ NM. The first heuristic
called HMPA1 builds each area of G as a BFS tree, looking for a subset of adjacent
vertices that share a same literal and assigning that literal to them. The algorithm
makes use of an internal queue Z to store the vertices that will eventually become
the roots of the BFS trees, and of five vectors A, R, L, Q, P of NM elements with
the following contents for each vertex h:
A(h): number a assigned to the area A a to which vertex h belongs, with a =
1, 2, . . . ;
R(h): root of the BFS tree of A a ;
L(h): literal assigned to vertex h;
Q(h): indicator that vertex h is present (Q(h) = 1) or not (Q(h) = 0) in the queue
Z;
P (h): pointer to the ordered subset L h of literals associated with vertex h.