3

我在 miniKanren 学习关系编程，我决定实现一个时间调度系统。基本上，它归结为有限域上的三个关系。

首先，有一个时间带，它具有开始、持续时间、结束并出现在空间中：

(l/defne stripo
  "Defines time strip relationship. Time strip start must be before end, and have a duration."
  [work] ([[start duration end _]]
          (fd/+ start duration end)))

然后，在条带列表（这是一个 4 元素列表的列表）上存在发生之前的关系。这是两个事件的结束和开始之间的成对关系：

(l/defne happens-beforo
         "Defines a happens-before relationship between consecutive time strips in a list."
         [elements]
         ([[]])
         ([[a]])
         ([[a b . d]]
          (l/matche [a b] ([ [_ _ e _] [s _ _ _] ] (fd/<= e s)))
          (happens-beforo (l/llist b d))))

最后，有一个非重叠关系，即两个时间带在共享相同空间时不能重叠：

(l/defne non-overlappo
  "Two time strips must not overlap in time, if they share the same space"
  [a b]
  ([[_ _ _ sp1] [_ _ _ sp2]]
   (l/conde
     [(l/== sp1 sp2)
      (l/conde
        [(happens-beforo [a b])]
        [(happens-beforo [b a])])]
     [(l/!= sp1 sp2)])))

我可以对关系链运行很长的查询happens-beforo，数千个时间带都可以。当我限制这些时间带的空间时，问题就开始出现了。这是一个功能：

(l/defne constrain-spaceo
  "This constraint will assure that all time strips within the argument
  obey non-overlapping relationship with each other. Quadratic."
  [strips]
  ([[]])
  ([[w . ws]]
   (let [space' (l/defne space' [c a]
                  ([_ []])
                  ([_ [f . d]]
                   (non-overlappo c f)
                   (space' c d)))]
     (l/all (space' w ws) (constrain-spaceo ws)))))

对于条带 q 的列表，它在每两个元素之间建立non-overlappo关系。由于是双向关系，所以小于n^2。

当我constrain-spaco只使用 10 条时，搜索时间就会增加，我无法产生任何结果。

到目前为止，我一直在尝试减少这个时间的方法，似乎它与竞争一个空间的条带数量有关，而不管总共有多少条带。如果我创建两组条带，一组在空间 0 中，另一组在空间 1 中并应用于constrain-spaco整个条带列表，那么时间是这些条带分别计算的时间之和。

我的问题是：

  1. 为什么有限域约束的数量会对时间产生如此大的影响？我的印象是约束的数量有助于搜索时间。
  2. 有什么办法可以缩短搜索时间？也许改变数据表示？
4

0 回答 0