Re: partial/full AC

[PRADOS Julien]

fred bapst wrote:

> Keywords: constraints, CLP, arc consistency, 
>          propagation
>
> Hello,
>
> I thought that the difference between '#=' and '#=#' 
> was efficiency, not semantic...
>
> Can anybody explain why the following 2 versions
> produces different results on gprolog 1.2.8 ?
>
> Thanks in advance.
>
> %----------------------------
> probl(Ls) :- 
>        Ls = [A,B,C], 
> 	fd_domain(Ls,5,20),
>         fd_domain([AA,BB,CC],1,400),
>        AA#=#A*A, BB#=#B*B, CC#=#C*C,  % full AC
>         AA + BB #= CC,
>         fd_labeling(Ls).
> %----------------------------
> probl2(Ls) :- 
>        Ls = [A,B,C], 
> 	fd_domain(Ls,5,20),
>         fd_domain([AA,BB,CC],1,400),
>        AA#=A*A, BB#=B*B, CC#=C*C,     % partial AC
>         AA + BB #= CC,
>         fd_labeling(Ls).
>
> %----------------------------
> | ?- probl1(Ls).
> Ls = [6,8,10] Ls = [8,6,10]
>
> | ?- probl2(Ls).
> Ls = [5,12,13] Ls = [6,8,10]   Ls = [8,6,10]
> Ls = [8,15,17] Ls = [9,12,15]  Ls = [12,5,13]
> Ls = [12,9,15] Ls = [12,16,20] Ls = [15,8,17]
> Ls = [16,12,20]
>
>
>  

exact... there is no semantic difference...
it is  two different method of evaluating the constraints and storing 
the variables !!!

the partial arc consistency just reduce the lower and the upper bound of 
the variables and can deal with large variable domain.
the full arc consistency evaluate the constraint for each of the value 
that the variables can take (and the domain of the variable is reduce 
1..128 by default)

example: "constraint A to be a multipy of 3 and less than 500"

with partial arc consistency:
| ?- A #=< 500, A rem 3 #= 0.
A = _#2(0..498)
only the bounds are reduce... so 499 and 500 are discarded, but 2 is 
still a candidate.

with full arc consistency:
| ?- A #=< 500, A rem 3 #=# 0.
A = 
_#2(0:3:6:9:12:15:18:21:24:27:30:33:36:39:42:45:48:51:54:57:60:63:66:69:72:7
5:78:81:84:87:90:93:96:99:102:105:108:111:114:117:120:123:126@)

all the values are tested for A so more values are discarded... but the 
variable domain is reduce to 128 and @(at the end of the result) 
indicate that the domain of A was truncated.


choosing one of the method depend of the problem... puting a full arc 
consistency at a chosen point can increase the efficency, but often it 
is better to use partial arc consistency.

the semantics are the same, and at the end of labeling you get the same 
result.


In your example, you don't have the same result, because in the full arc 
consistency, the domain of the variables are restricted to 128...
it seems that you don't have variables greater than 400 so you can 
increase the domains of your variables from 128 to 512 by using

fd_set_vector_max(512).



Good Luck !!!