users-prolog
[Top][All Lists]
Advanced

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

Re: Labeling outside of fd_labeling?


From: Daniel Diaz
Subject: Re: Labeling outside of fd_labeling?
Date: Sun, 17 Jun 2012 10:11:36 +0200

Le 16 juin 2012 à 16:44, Jan Burse a écrit :

> Dear All,
> 
> Small question. I just posed the following query:
> 
> ?- X #< Y, Y #< Z, Z #< X.
> 
> The interpreter then was busy for around ~4 secs
> and then responded with "no".
> 
> The "no" is actually correct, by transitivity we have
> X #< Z which conflicts with Z #< X.
> 
> What I wonder is what keeps the interpreter busy for
> ~4 secs and whether the "no" is reliable.

It is due to the arc-consistency filtering algorithm. Consider X@<Y, Y#<X. 
Basically for X#<Y the max(X) is set to max(Y)-1 each time the max(Y) is 
updated. Conversely for Y#<X, the max(Y) is set to max(X)-1 each time max(X) is 
updated.
This results on a decrement of the max(X) and max(Y) from FD_MAX_INT (e.g. 
268435455) to 0 (1 by 1). Once X or Y reaches a domain 0..0 the inconsistency 
is discovered on the other variable (domain 0..-1, i.e. empty).

This takes 4 sec on your machine.

About the "no": yes it is reliable.

Daniel

> 
> Bye
> 
> _______________________________________________
> Users-prolog mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/users-prolog
> 
> -- 
> Ce message a ete verifie par MailScanner
> pour des virus ou des polluriels et rien de
> suspect n'a ete trouve.
> 


-- 
Ce message a ete verifie par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a ete trouve.




reply via email to

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