类布尔到布尔可满足性[多项式时间减少]第2部分

Question

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

（Class Scheduling to Boolean satisfiability [Polynomial-time reduction]）

我通过@Amit回答谁是非常优雅，易于代码。 基本上，他的答案是这样的：他不考虑课程，而是考虑时间间隔。

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

当我们只考虑课程而不考虑其他因素时，这种方法效果很好。我通过在区间内对房间进行编码来概括它。

例如，而不是[8-10]说，课程可能发生在上午8点到上午10点之间。

我用[0.00801 - 0.01001]说一门课程可以在房间上午8时和10时之间发生1

我敢肯定，你目前徘徊“为什么双用？”那么，因为这里来我的问题：

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

我用[1.00801 - 1.01001]表示一个课程可以在房间1的早上8点到上午10点之间发生，并由老师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]，所以对于现在，解决者认为这是可能的。

我仍然没有就如何确保这一点，通过使用此区间方法任何线索...... 我需要一种方法，以便编码{间隔，房间和老师-ID}指出：

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

在此先感谢您的帮助， 此致敬意！

---

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

Answer 1

这个答案是Part 1's answe为r的扩展，并使用在相同的标记可能。好吧，假设每个时间间隔都分配给一位教师（如果不止一位教师可以采取这个时间间隔，只是有多个实例，每个实例有不同的教师），所以表示教师t在教室p时间x到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)每个老师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.也由一个事实，即不能有重叠的时间和类两类满足。

第3个约束there is a least 1 interval true by course.由F1子句满足，因为您必须为每个课程至少选择一个时间间隔（只分配一个教师）。