[eclipse-clp-users] RES: RES: RES: minlist /2 in a Point list

Hello Joachim,

>
>Only after the constraints have done their work ("propagated the
consequences of the search decision"), and only of it didn't lead to
failure, is a new >child search node created.  The whole point of
constraint-based search is that you do NOT have to go all the way down to
the leaves of a search tree!

In my understanding I see the search tree of my (and many others) problem
having each variable (X1, Y1, X2, Y2, etc) at a distinct level of the search
tree, like shown in Page 124 of the Eclipse Tutorial. So a candidate
solution of my problem would only be found when the search tree reaches the
final node (a leaf). This way, what am I missing out?

Thank you for the support,


Igor Kondrasovas
Project Management
Inovativa Tecnologia
www.otimizecortes.com
+55 47 3027-6442
+55 47 8839-1592





-----Mensagem original-----
De: Joachim Schimpf [mailto:joachim.schimpf_at_...269...] 
Enviada em: sábado, 19 de junho de 2010 05:28
Para: Igor Kondrasovas
Assunto: Re: [eclipse-clp-users] RES: RES: minlist /2 in a Point list

Igor Kondrasovas wrote:
> 
 > Due the current deadlines I have I'm thinking about exploring a little
bit more the  > search heuristics built in eclipse library.

I don't think that is going to help much.  For variable selection
"first_fail"
is pretty much the only clever thing you can do, and for value choice,
"indomain_split" seems the most appropriate for coordinate variables.

You may of course experiment with the incomplete search methods, but the
heuristics is more important.


> 
> There is a concept that I still could not fully understand after reading
the tutorials:
 > In my understanding if we perform a search, all nodes (in case of a
complete search)  > on the search tree will be visited and then constrains
will be used to check if the  > solution is valid.

No, every individual branching decision at node imposes a new constraint,
e.g. X=3 (or e.g. X>=3 when using domain splitting).
This _immediately_ causes the the problem constraints to wake up and to
compute any consequences of the search decision (typically resulting in
further domain reductions or even failure).

Only after the constraints have done their work ("propagated the
consequences of the search decision"), and only of it didn't lead to
failure, is a new child search node created.  The whole point of
constraint-based search is that you do NOT have to go all the way down to
the leaves of a search tree!


In ECLiPSe, you make a search node by writing a disjunction, e.g.

(
     X #=< 3
     % constraints wake up here, and may fail ;
     X #> 3
     % constraints wake up here, and may fail
)

If you have a 2-D point, you could use something like try_quadrants in the
attached file: you split the remaining X/Y coordinates together to search
the 4 sub-quadrants in turn.  The space_search predicate uses a round-robin
strategy, i.e. it splits the coordinates for one point, and then all the
other points, before splitting the first one again.

This still isn't very clever because the points are blindly placed, but
maybe it gets you started.


-- Joachim