python - 建立具有大量变量的时间表问题

Question

我有一个经典的时间表问题，由变量类 (~100)、房间 (20)、学期 (8) 和工作日 (5) 组成。

为了简化问题，以下是减少的约束。

一天有 9 个小时。

有些类(class)是学生的必修课，并且条款 1、3、5、7(以及 2、4、6、8)的必修课不得相互重叠。

类(class)在小时数方面有不同的权重，有些是 2 小时，有些是 3 小时。

一些类(class)应该在特定的房间。

同一个类不能同时有两堂课。

我要使用 logilabs python 约束模块。而且我知道明智地选择变量和域将减少解决问题的时间。问题是我以前从未做过约束编程，并且很难构建问题以找出从哪里开始以及从什么开始。例如:

我可以设置一个约束，比如“没有两个类(class)同一个房间，同一天可以重叠彼此的时间段”。或者从“没有房间可以在同一天预订超过 9 小时”开始，然后继续减少解决方案域。我估计(没有尝试)第一个约束比另一个约束需要更长的时间来解决。但它也需要(我猜)改变变量和解决方案域或重建一个较小的问题。我已经有点迷失在变量、域、区间、实现等方面了。

长话短说，我需要一些指导来构建问题、解决方案域、明智地选择变量等。

谢谢

更新

我使用 logilab-constraint 包制作了一个基本应用程序并将其上传到 github

Answer 1

看看 curriculum course example code的 Drools Planner .它基本上是同一件事，但术语略有不同:每门类(class)(=类(class))都有许多讲座需要安排到一个房间(=房间)和时段(=每个工作日的每个学期都是一个时段)。

诀窍是保持干净的域模型并将其与约束规则分开。 因为您的类(class)在小时数方面有不同的权重，所以我建议只为 Lecture 分配一个 startingPeriod，这样将 Lecture 移动到另一组的代码并不多Period(只需重新分配第一个 Period)。