课程表问题的数学分析.docxVIP

-1-

课程表问题的数学分析

花鹏飞

九江学院计算机系，中国江西九江,332005

摘要：本文在第一次提出解决课程表问题的实体关系图基础上，利用矢量空间的点阵方法描述问题，进一步分析大学课程表的可能的排法，并且使用一种新的称之为“之”字图来分析课程表的排法，这种分析方法形象具体，具有实用性。

关键词：E-R模型，数据结构，大学课程表，之字图。

1.问题

大学课程表问题研究和讨论对于给定数目的教师，其担任一定数目的课程，并且被分配给一定数目的教室，这些课程由一定数目的学生（更多情况下我们考虑班级）来选修，问题求解的目标是指定某位教师在什么时间内在哪一个教室给哪个班级教授哪门课程。这是大学课程表问题的求解命题。这个命题是否存在解，判断最佳解的标准，以及求解的具体步骤是完整解决这个问题的基本问题。

大学课程表因其复杂而难以求解，这个问题是一个复杂的要求满足各种限制条件的排列组合问题。早有文章【1】说明时间表的复杂性，课程表问题是典型的组合优化问题和不确定性调度问题。20世纪70年代中期S.EVEN等认证了课程表问题是NP完全类问题。有关NP问题讨论参考书籍【2】第11章节。

在文章【3】【4】中作者指出大学课程表的排法因其规模大，设计因素多和结构复杂被归结为NPC(NondeterministicPoly-nomialComplexity)问题。这些文章给出了课程表问题一些有意义的数学定义，并且指出了考虑的方法和求解的可能步骤。但是有关推理的根据并没有明确而且一些说法多半基于经验和计算机计算时间的使用。有些文章采用各种方法列举了寻求问题的一些解决方法，问题的定义，和实施条件，但是有关推理的设计并不清楚。这些算法基于学习模式【5】，遗传算法【6】，退火算法【7】认为能够较好地解决课程表问题，但是步骤并不容易理解。

文章【8】给出了课程表问题较好的数学定义，但是推导公式较复杂，而且不易理解，对于多种和复杂限制条件的引入不易推广和实用。本文在第一次提出课程表需要考虑的问题和可能的分析方法基础上，更进一步分析课程表问题的内涵和提出两种分析方法，这些方法可能发展成为解决NP类问题的有效途径。

-2-

2.描述方法和问题求解

在文章【9】中对于课程表问题的概念分析，作者使用数据库的实体－对象模型讨论了课程表问题的基本要点，这就是课程表问题由班级、课程、教师，时间，教室五个实体组成，这个E-R图如图1。课程表的上课即排课表由这五个实体之间的一一对应关系所组成，这是一个复杂的排列组合问题，其中组合的条件由选课、和任课的一一对应关系组成。

选课教室课程时间这样的约束条件还有文章【8】中列举的综合考虑条件，其中一个简单的约束条件是某些课程必须在特定的教室进行。

选课

教室

课程

时间

班级

上课

单双任课星期

单双

任课

星期

教师

节次

图1，课程表的实体关系图

在排课系统的实体图中，由教师，教室，课程，班级组成上课的关联，首先时间是教师的属性，这说明教师什么时间上课；时间是班级的属性，说明班级什么时间有课；时间是课程的属性，说明课程什么时间提供给学生上；时间是教室的属性，说明教室什么时间被占用；既然时间是各个实体的属性，我们可以将其考虑为实体。其次，时间确实可以是实体，这是因为实体可以具有属性，时间可以具有星期几，每天第几节课、以及复杂课程表考虑的单双周属性。

上课这个联系转化的表格SCTRWD中的主键分析，一个特定的班级Sno很可能选修若干门课程Cno，因此主键应该是Sno和Cno的组合；对于特定的Sno、Cno组合，一般只有一个特定的Tno来担任课程的教学，当然我们目前不考虑由几个教师担任某个班级某门课程的教学，因此对于某个Sno、Cno的组合，Tno是一定的；再讨论时间，课程必须在星期的某一天以及某个节次，由Wno、Dno的组合指定一个特定的上课时间(没有考虑单双周)，而教室应该随之唯一确定；总之，SCTRWD表的主键应该是Sno、Cno、Wno、Dno的组合，对于确定的每一个的这些组合，Tno、Rno是随之确定的。

-3-

这个问题的数学描述是给定一组学生S(S1,S2...Si)，一组课程C(C1,C2...Cj)，一组教师T(T1,T2...Tk)，一组教室R(R1,R2...Rm)，一个时间序列N(N1,N2...Nn)，问题的求解目的是找出这些序列的每个元素之间的一一对应关系，其中这些元素的组合要满足一定的对应关系。诸如：

1）S-C之间的对应关系；

2）T-C