[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: partial/full AC

From: PRADOS Julien
Subject: Re: partial/full AC
Date: Mon, 31 Mar 2003 10:28:55 +0200
User-agent: Mozilla/5.0 (X11; U; SunOS sun4u; en-US; rv:1.1) Gecko/20020827

fred bapst wrote:

Keywords: constraints, CLP, arc consistency, propagation


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),
       AA#=#A*A, BB#=#B*B, CC#=#C*C,  % full AC
        AA + BB #= CC,
probl2(Ls) :- Ls = [A,B,C], fd_domain(Ls,5,20),
       AA#=A*A, BB#=B*B, CC#=C*C,     % partial AC
        AA + BB #= CC,

| ?- 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

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


Good Luck !!!

reply via email to

[Prev in Thread] Current Thread [Next in Thread]