Clojure core.logic CLP（FD）投影FD变量 [英] Clojure core.logic CLP(FD) projecting FD variables

问题描述

我正在使用Clojure的core.logic CLP（FD）库（core.logic版本0.8.3）使用一个朴素的方块打包算法。

表示如下：

  [[[x11 y11] [x12 y12]] 
 [[x21 y21] [ x22 y22] ...]] 
  

，每个正方形表示为其左上角和右下角。

坐标是FD变量，在一定的时间间隔内。

 <$ c> 
 $ c>（最近最远的
 x11 y11 x22 y22 _1 _2] 
（最近的 - square [[x11 y11] _1] sqrs）
（farthest-square [_2 [x22 y22]] sqrs）
（project [x11 y11 x22 y22] 
（let [a y11）
b（ -  x22 x11）] 
（== s（ - > （+（* aa）（* bb））Math / sqrt Math / ceil int）））））））
  

$ b b

这似乎与纯整数很好：

 （运行1 [q] size-o q [[[0 0] [11]] [[1 1] [2 2]]]））
 => （3）
  

甚至使用完全约束的FD变量

 （defn constrained-solution-size [] 
（run 1 [q] 
（new [size x11 y11 
 x12 y12 
 x21 y21 
 x22 y22 square] 
（fd / in x11 y11 x12 y12 x21 y21 x22 y22（fd / interval 0 2））
（fd / eq 
 = x11 0）（= y11 0）（= x21 1）（= y21 1）
（= x12（+ x11 1） x21 y12]] [x21 y21] [x22 y22]]] 
（x21 y11）[x21 y12]解决方案大小正方形）
（== q {：squares squares：size size}））））
 
（constrained-solution-size）
 = （{：squares [[[0 0] [1 1]] [[1 1] [2 2]]]：：size 3}）
   
 
但是当变量的域没有完全约束时，它似乎断开了。例如，如果我删除 y21 = 1 ，意味着 y11 和 y21 在其域中留有多个值：
 （defn unconstrained- solution-size [] 
（run 1 [q] 
（fresh [size x11 y11 
 x12 y12 
 x21 y21 
 x22 y22 squares] 
（fd / in x11 y11 x12 y12 x21 y21 x22 y22（fd / interval 0 2））
（fd / eq 
（= x11 0）（= y11 0）（= x21 1）
（= x12 1））（= y12（+ y11 1））
（= x22（+ x21 1））（= y22（+ y21 1） x12 y12]] [x21 y21] [x22 y22]]））
（解决方案大小正方形）
（== q {：正方形：尺寸大小}））））
  
我得到
 （unconstrained- solution-size）
 => ClassCastException clojure.core.logic.LVar不能转换为java.lang.Number clojure.lang.Numbers.minus（Numbers.java:135）
  
看来项目只有在其域完全受约束时才适用于FD变量。这是怎么回事？如果是，是否有任何建议如何对FD变量进行非关系算术？
 
 
 
谢谢！
解决方案
是的，你不能投影没有被限制为单一值的有限域变量。我建议查看现有的解决方案，你的问题在Prolog中利用CLP（FD）。很可能我们不支持足够的约束，使这个问题简单易懂 - 我们正在努力。
 
I'm working on a naive square-packing algorithm using Clojure's core.logic CLP(FD) library (core.logic version 0.8.3).

Squares are represented like so:
[[[x11 y11] [x12 y12]] 
 [[x21 y21] [x22 y22] ...]]
with each square represented as the coordinates of its top-left and bottom-right corners.

Coordinates are FD variables, within a certain interval.

I want to define the size of a solution as the distance between the top-right corner and bottom-right corners of the closest and farthest squares to the origin, respectively
(defne solution-size-o [size squares]
  ([s sqrs]
    (fresh [closest farthest 
            x11 y11 x22 y22 _1 _2]
    (closest-square   [[x11 y11] _1] sqrs)
    (farthest-square  [_2 [x22 y22]] sqrs)
    (project [x11 y11 x22 y22]
      (let [a (- y22 y11)
            b (- x22 x11)]
        (== s (-> (+ (* a a) (* b b)) Math/sqrt Math/ceil int)))))))
This seems to work fine with plain integers:
(run 1 [q]
  (solution-size-o q [[[0 0] [1 1]] [[1 1] [2 2]]]))
=> (3)
And even with fully-constrained FD variables
(defn constrained-solution-size []
  (run 1 [q] 
    (fresh [size x11 y11 
                 x12 y12 
                 x21 y21 
                 x22 y22 squares]
      (fd/in x11 y11 x12 y12 x21 y21 x22 y22 (fd/interval 0 2))
      (fd/eq 
        (= x11 0) (= y11 0) (= x21 1) (= y21 1)
        (= x12 (+ x11 1)) (= y12 (+ y11 1))
        (= x22 (+ x21 1)) (= y22 (+ y21 1)))
      (== squares [[[x11 y11] [x12 y12]] [[x21 y21] [x22 y22]]])
      (solution-size-o size squares)
      (== q {:squares squares :size size}))))

(constrained-solution-size)
=> ({:squares [[[0 0] [1 1]] [[1 1] [2 2]]], :size 3})
But it seems to break when the domains of the variables isn't fully constrained. For example, if I remove the constraint that y21 = 1, meaning y11 and y21 have more than one value left in their domains:
(defn unconstrained-solution-size []
  (run 1 [q] 
    (fresh [size x11 y11 
                 x12 y12 
                 x21 y21 
                 x22 y22 squares]
      (fd/in x11 y11 x12 y12 x21 y21 x22 y22 (fd/interval 0 2))
      (fd/eq 
        (= x11 0) (= y11 0) (= x21 1)
        (= x12 (+ x11 1)) (= y12 (+ y11 1))
        (= x22 (+ x21 1)) (= y22 (+ y21 1)))
      (== squares [[[x11 y11] [x12 y12]] [[x21 y21] [x22 y22]]])
      (solution-size-o size squares)
      (== q {:squares squares :size size}))))
I get
(unconstrained-solution-size)
=> ClassCastException clojure.core.logic.LVar cannot be cast to java.lang.Number     clojure.lang.Numbers.minus (Numbers.java:135)
It seems that project only works on FD variables when their domains are fully constrained. Is this how it should be? If it is, does anyone have any suggestions on how to carry out non-relational arithmetic on FD variables?

Thanks!
解决方案
Yes you cannot project finite domain vars that haven't been constrained to single value. I recommend looking at existing solutions to your problem in Prolog that leverage CLP(FD). It may very well be that we don't support enough constraints to make this problem simple to express - we're working on that.

                        
这篇关于Clojure core.logic CLP（FD）投影FD变量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！