1

前几天我问了一个关于如何将大学排课问题转化为布尔可满足性问题的问题。

（类调度到布尔可满足性[多项式时间减少]）

我得到了@Amit 的回答，他非常优雅且易于编码。基本上，他的回答是这样的：他没有考虑课程，而是考虑了时间间隔。

因此，对于第 i 个课程，他只是指出了该课程的所有可能间隔。当每门课程至少有 1 个真实区间并且没有区间重叠时，我们得到了一个解。

当我们只考虑课程而不考虑其他内容时，这种方法非常有效。我通过对区间内的房间进行编码来概括它。

例如，而不是 [8-10] 说课程可以在上午 8 点到 10 点之间进行。

我用 [0.00801 - 0.01001] 表示课程可以在上午 8 点到 10 点之间在房间 1 进行。

我确定您目前正在徘徊“为什么要使用 double ？” 好吧，因为我的问题来了：

为了继续推广这种方法，我还在这个区间内编码了教师的 n°。

我用 [1.00801 - 1.01001] 表示课程可以在上午 8 点到 10 点之间在 1 号房间进行，由 n°1 老师教授。

这是我现在得到的：

我的求解器在输出中给我的说明

像这样 [1.008XX - 1.010XX] 可以与 [2.008YY - 2.010YY] 同时发生，这是真的，如果老师 1 在上午 8 点到 10 点之间在房间 X 教学，那么老师 2 也可以在Y 上午 8 点到 10 点之间，当且仅当房间可用时。

问题是：使用这种方法，我不能保证 XX 和 YY 会不同并且 YY 将可用，因为 [1.008XX - 1.010XX] 不重叠 [2.008XX - 2.010XX]，所以现在，求解器考虑这可能。

而且我仍然不知道如何通过使用这种间隔方法来确保这一点......我需要一种编码 {Interval, room and teacher-id} 的方法，以便：

  • 一个老师不能在同一个区间的两个地方。
  • 同一房间不能有 2 位教师在同一时间间隔内。
  • 当然，至少有 1 个区间为真。

提前感谢您的帮助，最好的问候！

后续问题： Class Scheduling to Boolean satisfiability [Polynomial-time reduction] Final Part

4

1 回答 1

2

这个答案是第 1 部分答案的扩展，并尽可能使用相同的符号。

好的，假设每个时间间隔都分配给一位老师（如果不止一位老师可以占用该时间间隔，则只需有多个实例，每个实例有不同的老师），因此要指示老师t在教室里教的p时间xto y，我们可以使用给这个类的旧变量V_{i,j}- 用于类和间隔。

对于每个教师t和每对区间c=(x1,y1)，d=(x2,y2)在教师可能参与的课程 (a,b) 中，添加以下子句：

Q_{t,i,j} = Not(V_ac) OR Not(V_bd) OR Smaller(y1,x2) OR Smaller(y2,x1)

直观地说，上面的条款保证了一个老师不能同时在两个地方——没有时间间隔重叠，同一位老师被分配给他们。

(i,j)通过用 AND 将每个老师的每一对链接t到原始公式，它满足了您的第一个约束a teacher cannot be in 2 places in the same interval.- 因为每个老师不能同时在两个地方。

您的第二个约束there cannot be 2 teachers in the same room for the same interval.也满足以下事实，即不能有两个课程与时间和课程重叠。

there is a least 1 interval true by course.该子句满足第三个约束条件F1，因为您必须为每门课程选择至少一个间隔（指定一名教师）。

于 2015-03-19T15:35:02.637 回答