3

我有一个经典的时间表问题，由变量 classes(~100)、rooms(20)、terms(8) 和 weekdays(5) 组成。

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

一天是9个小时。

有些课程是学生必修课，1、3、5、7（以及 2、4、6、8）的必修课不得相互重叠。

课程在小时数方面有不同的权重，有些是 2 小时，有些是 3 小时。

有些课程应该在特定的房间。

同一堂课不能同时开两节课。

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

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

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

谢谢

更新

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

4

2 回答 2

1

看一下Drools Planner的课程课程示例代码。基本上是一样的，但术语略有不同：每门课程（=班级）都有许多讲座需要安排在一个房间（=房间）和时段（=每个工作日的每个学期都是一个时段）。

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

于 2011-05-08T13:46:47.277 回答
-1

我最终得到了一个将“明智地选择变量”和“减少选择域”捆绑在一起的解决方案。下面是我正在做的基于 django 的时间表应用程序的片段：

class Course(models.Model):
    name = models.CharField(max_length=255, null=False, blank=False)
    duration = models.PositiveSmallIntegerField(blank=False)
    type = models.ForeignKey(CourseType, blank=False, null=False)
    mandatory = models.BooleanField(default=False)
    '''
        following are the basic constraints  
    '''
    days = models.ManyToManyField(Day, blank=True, null=True)
    terms = models.ManyToManyField(Term)
    rooms = models.ManyToManyField('ClassRoom', blank=True, null=True)


    def __unicode__(self):
        return u'%s' % self.name

我已经将基本约束嵌入到课程中，例如“这门课程可能在星期一或星期二，在房间 1 或 2 或 3 或 4 或 5 中的 1 或 2 或 3”，这使我可以直接应用这些基本从数据库中选择课程时的限制。

诸如“在同一天同一时间的同一时间之间不能有两门课程在同一个房间”之类的一般限制适用于来自数据库中选择的减少变量域。

似乎现在正在工作。

于 2011-05-11T11:37:48.413 回答