Re: Labeling outside of fd_labeling?

[Daniel Diaz]

Le 18 juin 2012 à 18:46, Jan Burse a écrit :

> Hi Daniel,
> 
> Thank you very much for your explanation. BTW: found
> another "looping" example:
> 
>   | ?- X + 1 #= Y, Y + 1 #= Z, Z #< X.
>   (4555 ms) no
> 
> So basically, when one for example formulates
> scheduling problems etc.., one has to be careful
> with inconsistent problems?

Generally speaking, the answer is yes since an inconsistency problem implies a 
whole exploration of the search space. In some cases this can be very fast (if 
the pruning is efficient), in others it can be very expensive. It is the case 
in your examples: the domain of implied variables are reduced by 1 value at 
each step of the propagation resulting in a costly exploration (linear in the 
size of the domain). 

Daniel
 
> 
> Bye
> 
> Daniel Diaz schrieb:
>> 
>> 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.
>>> 
>> 
>> 
> 
> 
> 
> _______________________________________________
> 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.