Re: [eclipse-clp-users] RES: RES: Domain Definiton in Cut and Packing Problem

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Thu, 08 Apr 2010 14:57:05 +1000
Igor Kondrasovas wrote:
> Hello,
> 
> Please let me rewrite a predicate that was erroneously copied while editing
> the previous e-mail:
> 
> solve((X1,Y1),(X2,Y2), [NFAB| NFBA]):-

Your first mistake is here   ^^^
This should be a comma because you want to make a list with 2 elements.

With this fix you get:

?- solve((X1, Y1), (X2, Y2), [[[(0, 0), (0, 2)], [(0, 2), (2, 0)], [(2, 0), (0, 0)]],
[[(0, 2), (2, 2)], [(2, 2), (2, 0)], [(2, 0), (0, 2)]]]), [X1, Y1, X2, Y2] :: -100 .. 100.
X1 = X1{-100 .. 100}
Y1 = Y1{-100 .. 100}
X2 = X2{-100 .. 100}
Y2 = Y2{-100 .. 100}
There are 2 delayed goals.
Yes (0.04s cpu)


As is usually the case with constraint programming, propagation alone is not
enough to find the actual solutions, and you need to add search, e.g.

solve((X1,Y1),(X2,Y2), [NFAB, NFBA]):-
	outside_polygon1((X1,Y1), (X2,Y2), NFAB),
	outside_polygon1((X2,Y2), (X1,Y1), NFBA),
	search([X1,X2,Y1,Y2], 0, first_fail, indomain_split, complete, []).

Now you can compute all solutions:

?- [X1, Y1, X2, Y2] :: -2 .. 2, solve((X1, Y1), (X2, Y2), [[[(0, 0), (0, 2)], [(0, 2), (2,
0)], [(2, 0), (0, 0)]], [[(0, 2), (2, 2)], [(2, 2), (2, 0)], [(2, 0), (0, 2)]]]).
X1 = -2
Y1 = -2
X2 = -2
Y2 = -1
Yes (0.02s cpu, solution 1, maybe more)
X1 = -2
Y1 = -2
X2 = -2
Y2 = 1
Yes (0.03s cpu, solution 2, maybe more)
X1 = -2
Y1 = -2
X2 = -2
Y2 = 2
Yes (0.03s cpu, solution 3, maybe more)

etc.


> You can use as an example:
> 
> solve((X1,Y1),(X2,Y2),
> [[[(0,0),(0,2)],[(0,2),(2,0)],[(2,0),(0,0)]],[[(0,2),(2,2)],[(2,2),(2,0)],[(
> 2,0),(0,2)]]]), [X1,Y1,X2,Y2] :: -100..100.

As an general note, it is a good habit to use unique functors to identify
your data structures, instead of simply using lists for everything.

So instead of      [(0,0),(0,2)]
better use     line((0,0),(0,2))

Instead of          [     [(0,0),(0,2)],     [(0,2),(2,0)],     [(2,0),(0,0)] ]
use         polygon([ line((0,0),(0,2)), line((0,2),(2,0)), line((2,0),(0,0)) ])

With such an encoding, the initial bug would have been more obvious.

I would probably also use point(X,Y) instead of (X,Y), but that's debatable.
Note that (X,Y) is the same as ','(X,Y), but (X,Y,Z) is ','(X, ','(Y,Z)).




-- Joachim
Received on Thu Apr 08 2010 - 04:55:44 CEST

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