Class 布尔可满足性调度 [多项式时间缩减] 第 2 部分
Class Scheduling to Boolean satisfiability [Polynomial-time reduction] part 2
几天前我问了一个关于如何将大学 Class 调度问题转化为布尔可满足性问题的问题。
()
我得到了@Amit 的回答，他非常优雅且易于编码。
基本上，他的回答是这样的：他考虑的不是课程，而是时间间隔。
所以对于第 i 门课程，他只是指出了这门课程的所有可能间隔。当每个课程至少有 1 个真实区间并且没有区间重叠时，我们得到一个解决方案。
当我们只考虑课程而不考虑其他时，这种方法非常有效。我通过对间隔内的房间进行编码来概括它。
例如，而不是 [8-10] 表示课程可以在上午 8 点到 10 点之间进行。
我用 [0.00801 - 0.01001] 表示课程可以在早上 8 点到 10 点之间在房间 1 进行。
我确定您目前正在徘徊 "why use double ?" 好吧，因为我的问题来了：
为了继续推广这个方法，我也在这个区间内编码了教师的编号。
我用 [1.00801 - 1.01001] 表示课程可以在早上 8 点到 10 点之间在房间 1 上课，由老师 n°1 教授。
这是我现在得到的：
像这样 [1.008XX - 1.010XX] 可以与 [2.008YY - 2.010YY] 同时发生，这是真的，如果老师 1 在早上 8 点到 10 点之间在 X 教室上课，老师2 也可以在上午 8 点到 10 点之间在 Y 教学，当且仅当房间可用时。
问题是：使用这种方法我无法保证 XX 和 YY 会不同并且 YY 可用，因为 [1.008XX - 1.010XX] 不与 [2.008XX - 2.010XX] 重叠，所以目前，求解器认为这是可能的。
而且我仍然不知道如何通过使用这种间隔方法来确保这一点...
我需要一种编码 {Interval, room and teacher-id} 的方法，以便：
- 一个老师不能在同一时间间隔出现在两个地方。
- 同一个房间不能有 2 位老师在同一个时间间隔内。
- 至少有 1 个区间为真。
在此先感谢您的帮助，
最好的祝福 ！
跟进问题：
此答案是 r 的扩展，并尽可能使用相同的符号。
好的，假设每个间隔都分配给一位老师（如果不止一位老师可以使用该间隔，只需有多个实例，每个实例有不同的老师），所以表示老师 t 教在时间 x 到 y 的 class 房间 p 中，我们可以使用这个 class 给出的旧变量 - V_{i,j} - 对于class 和间隔。
对于每位教师 t ，以及教师可能参与的 classes (a,b) 中的每对区间 c=(x1,y1), d=(x2,y2)，添加子句：
Q_{t,i,j} = Not(V_ac) OR Not(V_bd) OR Smaller(y1,x2) OR Smaller(y2,x1)
直觉上，上面的条款保证了一个老师不能同时出现在两个地方——分配给他们的同一个老师没有间隔重叠。
通过将每位教师 t 的每对 (i,j) 与原始公式链接起来，它满足您的第一个约束 - a teacher cannot be in 2 places in the same interval. - 因为每位教师不能在两个地方同时。
你的第二个约束 there cannot be 2 teachers in the same room for the same interval. 也满足了这样一个事实，即不能有两个 class 重叠时间和 class.
第 3 个约束条件 there is a least 1 interval true by course. 满足 F1 子句，因为您必须为每门课程至少选择一个间隔（分配一位教师）。
几天前我问了一个关于如何将大学 Class 调度问题转化为布尔可满足性问题的问题。
(
我得到了@Amit 的回答，他非常优雅且易于编码。 基本上，他的回答是这样的：他考虑的不是课程，而是时间间隔。
所以对于第 i 门课程，他只是指出了这门课程的所有可能间隔。当每个课程至少有 1 个真实区间并且没有区间重叠时，我们得到一个解决方案。
当我们只考虑课程而不考虑其他时，这种方法非常有效。我通过对间隔内的房间进行编码来概括它。
例如，而不是 [8-10] 表示课程可以在上午 8 点到 10 点之间进行。
我用 [0.00801 - 0.01001] 表示课程可以在早上 8 点到 10 点之间在房间 1 进行。
我确定您目前正在徘徊 "why use double ?" 好吧，因为我的问题来了：
为了继续推广这个方法，我也在这个区间内编码了教师的编号。
我用 [1.00801 - 1.01001] 表示课程可以在早上 8 点到 10 点之间在房间 1 上课，由老师 n°1 教授。
这是我现在得到的：
像这样 [1.008XX - 1.010XX] 可以与 [2.008YY - 2.010YY] 同时发生，这是真的，如果老师 1 在早上 8 点到 10 点之间在 X 教室上课，老师2 也可以在上午 8 点到 10 点之间在 Y 教学，当且仅当房间可用时。
问题是：使用这种方法我无法保证 XX 和 YY 会不同并且 YY 可用，因为 [1.008XX - 1.010XX] 不与 [2.008XX - 2.010XX] 重叠，所以目前，求解器认为这是可能的。
而且我仍然不知道如何通过使用这种间隔方法来确保这一点... 我需要一种编码 {Interval, room and teacher-id} 的方法，以便：
- 一个老师不能在同一时间间隔出现在两个地方。
- 同一个房间不能有 2 位老师在同一个时间间隔内。
- 至少有 1 个区间为真。
在此先感谢您的帮助， 最好的祝福 ！
跟进问题：
此答案是
好的，假设每个间隔都分配给一位老师（如果不止一位老师可以使用该间隔，只需有多个实例，每个实例有不同的老师），所以表示老师 t 教在时间 x 到 y 的 class 房间 p 中，我们可以使用这个 class 给出的旧变量 - V_{i,j} - 对于class 和间隔。
对于每位教师 t ，以及教师可能参与的 classes (a,b) 中的每对区间 c=(x1,y1), d=(x2,y2)，添加子句：
Q_{t,i,j} = Not(V_ac) OR Not(V_bd) OR Smaller(y1,x2) OR Smaller(y2,x1)
直觉上，上面的条款保证了一个老师不能同时出现在两个地方——分配给他们的同一个老师没有间隔重叠。
通过将每位教师 t 的每对 (i,j) 与原始公式链接起来，它满足您的第一个约束 - a teacher cannot be in 2 places in the same interval. - 因为每位教师不能在两个地方同时。
你的第二个约束 there cannot be 2 teachers in the same room for the same interval. 也满足了这样一个事实，即不能有两个 class 重叠时间和 class.
第 3 个约束条件 there is a least 1 interval true by course. 满足 F1 子句，因为您必须为每门课程至少选择一个间隔（分配一位教师）。