Information Technology Reference
In-Depth Information
procedure REVISE(
V
i
,
V
j
)
DELETE
ŕ
false;
for each
x
∈ D
i
do
if there is no such
V
j
∈ D
j
such that (
x
,
V
j
) is consistent,
then
delete
from Di;
DELETE
ŕ
true;
endif
endfor
return DELETE;
end REVISE
To make every arc of constraint network consistent, it is not sufficient to
execute REVISE for each arc just once. Once REVISE reduces the variable
x
v
i
,
then each previously revised arc(
v
i
,
v
j
) has to be revised again because the domain
of
might become smaller than before. The following algorithm obtains arc
consistency for the whole constraint network.
v
i
Algorithm 3.3
Constraint Propagation Algorithm AC-1 [Mackworth 1977]
procedure AC-1
Q
ŕ
{(
V
i
,
V
j
)∈arcs(
G
) ,
i
≠
j
};
repeat
CHANGE
ŕ
false;
for each (
V
j
)∈Q do
CHANGE
ŕ
REVISE(
V
i
,
V
i
,
V
j
)∨CHANGE;
endfor;
until not(CHANGE) ;
end AC-1
The main shortcoming of AC-1 is that a successful revision will force all arcs
to be revised in the next iteration, although only a small number of arcs are
affected . AC-3 performs re-revision only for those arcs that are possibly affected
by a previous revision, which improves AC-1 algorithm.
Algorithm 3.4
Constraint Propagation Algorithm AC-3 [Mackworth 1977]
procedure AC-3
Q
ŕ
{(
V
i
,
V
j
)∈arcs(
G
) ,
i
≠
j
};
while Q not empty
