[Top][All Lists]

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

Re: Labeling outside of fd_labeling?

From: Jan Burse
Subject: Re: Labeling outside of fd_labeling?
Date: Mon, 18 Jun 2012 18:46:25 +0200
User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:13.0) Gecko/20120615 Firefox/13.0.1 SeaMonkey/2.10.1

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?


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.



Users-prolog mailing list

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]