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

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Wed, 19 May 2010 15:24:09 +1000
Igor Kondrasovas wrote:
> Hello,
> 
> I would like to use the the bb_min /3 predicate to find the lowest
> “Cost” solution available in my search / 6 results:
> 
> The search is: search(XYs, 0, first_fail, indomain_split, complete, []),
> 
> XYs is a list of points (X,Y) elements and the cost is equals to the
> maximum X value on the entire list, so my goal is to minimize this cost.
> 
> I would like to know if I could use maxlist /2 to define the cost value
> or if there is any built-in predicate I could use, since it is not a
> simple scalar numeric list (only X value is considered).

Your code is perfectly fine (you do need to construct the auxiliary list
of Xs).  By the way, maxlist(Xs,Cost) is the same as Cost #= max(Xs).


> Here is the way I´m defining the predicate. In fact the code hangs when
> the bb_min is used.

First try doing the search without the bb_min: does it find a solution?

If yes, it should at least find that same first solution with the bb_min,
print "Found a solution with cost ....", and then go on trying to find a
better one.

It is also quite likely that you need to consider a search heuristic that
is better suited to the geometrical problem you have.  What I mean is that
your overlap constraints are of the form "no x overlap OR no y overlap".
When you have an object at (x1,y1) which must not overlap with (X,Y), then
that does not restrict the domains of X or Y, because they are allowed to
overlap in one of the dimensions.  A 2-D aware search routine could explore
the possible relative position of pairs of objects by imposing branching
constraints of the form X>x1 or X<x1 or Y>y1 or Y<y1.


-- Joachim
Received on Wed May 19 2010 - 05:22:28 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET