[gecode-users] Search and Recomputation

[Christian Schulte]

Before reading part S you should read all of Chapter 7. Your questions are
answered there.

Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Guido Tack
Sent: Friday, November 18, 2011 1:39 PM
To: Max Ostrowski
Cc: users at gecode.org
Subject: Re: [gecode-users] Search and Recomputation

On 18 Nov 2011, at 13:29, Max Ostrowski wrote:

> I have 2 general questions on how search works in gecode.
> 
> Search and Propagation
> 
> I just read on page 306 in "Modelling and Programming with Gecode", 
> that during search "pristine" clones are stored, where no propagation was
made.
> How is this possible. Considering the simple case, without 
> recomputation, having a full "trail" of spaces.
> having space[0] to space[n] for the first n decision levels.
> Now i do a choice on some variable x==1.
> Now i would expect doing some propagation.
> Do you copy the space[n+1], do some propagation, and afterwards delete 
> the propagated space to do another choice ?
> Do you always propagate all constraints with all choices without 
> storing intermediate, usable, results of this propagation?

I'm not sure I understand this question.  The only way to store results of
propagation is to store a clone of a space.  That's what a search engine
does. either for every choice point, or only for some (in case of
recomputation).  Please read the chapter about search engines, it will
answer your questions about which spaces are stored (in particular 36.5,
hybrid recomputation).  

> 2nd Question:
> 
> Using Recomputation:
> 
> 
> If i have stored a space S and done some choices C1,C2,C3
> 
> S->C1->S1->C2->S2->C3->S3
> 
> and now recognize that space S3 is failed and want to "backtrack" to 
> S2 i would do
> 
> S->commit(C1)
> S->commit(C2)
> 
> This should lead to a space equivalent to S2. Is this space already 
> propagated ?
> If i now call status() on S, is any propagator invoked?
> Does commit redo the propagation?
> Does it just restore the effects of the propagation?
> Does it just repost the decision (as i could do by hand saying post(x==1)
)?

It just posts the decision (that's the point of having choices, you only run
the entire propagation once, after posting all the choices).  Calling
status() will trigger all the propagation that results from the choices you
committed to.  Committing to choices is therefore the same as posting
constraints (no propagation happens until you call status()).

Cheers,
Guido

--
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/


_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users