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

Hello Joachim,

Thank you for your suggestions. I think that implementing a search heuristic is the best way to go. Due the current deadlines I have I'm thinking about exploring a little bit more the search heuristics built in eclipse library.

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. If so, what moment does constraint propagation helps improving the search performance? Would it be in reducing the number of backtrackings? 


Regards,

Igor.


-----Mensagem original-----
De: Joachim Schimpf [mailto:joachim.schimpf_at_...269...] 
Enviada em: quarta-feira, 16 de junho de 2010 22:35
Para: Igor Kondrasovas
Assunto: Re: RES: [eclipse-clp-users] minlist /2 in a Point list

Igor Kondrasovas wrote:
> Hello Joachim,
> 
> I'm still working in a way to improve the result I have. At this moment I'm still trying to find a way to get better results with the built-in predicates available on Eclipse in order to get better results.
> 
> Could you please give me some tips on how can I create the "2-D aware" search routine you mentioned? Is your idea based on implementing a search heuristic or a different constraint definition approach that will affect the way regular search methods woks?

I had a quick look at the paper you sent me.  They are not exactly forthcoming
with information about what constraints they used and what their search routine is!
You should try to locate more precise information about their work.

I think you need to implement some search heuristic
http://eclipse-clp.org/doc/tutorial/tutorial088.html#toc78

Using the idea of the nofit polygons, you could try in the search
routine to construct a chain of touching polygons:

1. pick and place some initial polygon A (e.g. at the edge of the board)
2. pick nondeterministically an unplaced polygon B, if that fails goto 5
3. select nondeterministically one edge of A's nofit polygon and constrain
   B's reference point to be somewhere on that edge.
   (This will eventually fail if B can't be placed adjacent to A, and
   backtrack to 2 for another candidate B)
4. A:=B; goto 2
5. if there are still unplaced polygons, try to place them non-touching
   (not sure that can happen)
6. We have not totally fixed the coordinates of the polygons, only
   constrained them to lie on line segments.  So do a standard search
   on the X/Y variables now to fix them.  Maybe this needs to be done
   after step 3 already to get better propagation.

So I suggest a hierarchy of decisions:
- polygons touch or not
- on which edge of the nofit polygon they touch
- where exactly on that edge they are placed

I have no idea whether that works, haven't done much in that area.
Hope it gives you some ideas!

-- Joachim