# 基于JAVA着色理论的排课问题研究
# 一、绪论
## 1.1 研究背景和意义
随着计算机科学技术的不断发展，各个行业信息化、科学化不断推进。高校如何才能提高办学的效率，这是每个高校都会面临的，也是每个高校需要迫切解决的问题。而采用信息化手段来代替传统的教学管理模式是一个重要的途径。在高校各项教学管理工作中，排课一直是最基本的、最重要的工作，其实质就是给教学计划中设置的课程安排合适的时间和地点，保证整个教学工作能够顺利地进行;同时，排课工作也是一项很复杂的工作，排课是一个NP完全问题，就是始终找不到一个最优的方法能够解决的问题，因为这个问题涉及了多种因素进行组合规划，有教师、学生的因素，也有教室的因素，尤其在目前各高校规模不断扩大，教学资源面临紧张，教师总数不足的前提下，排课工作问题更为凸出。
排课问题是S.Even在1975年证明了的NP难问题,在排课过程中需要综合考虑很多要素,比如年级、课程种类、教室容量、教师类型、上课时间、教师等等,以实现教学资源的合理规划。因此,如何对高校课程进行优化排列,提高学校教师、教室以及配套教学资源的利用率是各个学校追求的目标。排课问题涉及到教学资源的配置问题,更关系到各学校教学目标能否实现,已经成为国内外众多学者关注的焦点。高校排课问题属于时间表问题,该问题的解决不仅可以有效处理高校扩招、学分制推行等改革过程中遇到的资源紧缺问题,还能对其他时间表类问题给予一定的借鉴意义,如教育系统的考试安排问题、行政或商业部门的会议安排问题、交通部门的车辆时刻安排问题等。课程表是编排课程的表。科学的课程安排才能调度全校师生的教学活动,使学校的教学工作有序进行。所以,高校相关机构和人员需要对课程进行合理编排。早先,高校是通过人工的方式进行课程编排,不仅浪费了大量的人力和精力,还可能会由于某种情况考虑不周出现排课冲突。
## 1.2 国内外研究现状
### 1.2.1 国外研究现状
排课问题是一个多目标有限资源、带有约束条件的组合规划问题。排课系统已经成为国内外众多高校及软件公司的研究课题，取得了许多方面的理论。国外针对排课问题展开的研究较早。1963年Gotlieb在他的文章《The Construction of Class-Teacher Time-Tables》中提出了课表编排的数学模型。虽然之后人们对课表问题的算法等问题做了很多的探索，但是大多是都是在Gotlieb提出的数学模型的基础上简化或者是补充。1976年，Bondy用图的边染色算法来解排课表问题。排课问题被S.Even等人证明具有NP难度，并被理论化。1976年S.Even在其论文《The Complexity of Timetable And Multi Commodity Flow Problem 》中，第一次证明了课表问题是NP完全的。S.Even的论证进一步地将人们对课表问题复杂性的认识提高到理论高度。
### 1.2.2 国内研究现状
国内对排课问题的研究较晚，开始于20世纪80年代初期，1984年，清华大学在《清华大学学报》上发表了林漳希和林尧瑞在该课题上的实验性研究成果《人工智能技术在课表编排中的应用》。伴随着计算机普及、教务管理信息化的脚步,许多的学校也进行了一些排课自动生成软件的研究,相应的教务管理软件如雨后春笋般地涌出,成型的系统早期的有南京工学院的UTSS (A University Timetable Scheduling System).清华大学的TISER (TimerableSchedu1ER)，大连理工大学的智能教学组织管理与课程调度系统以及大连理工大学的课程调度系统等。总体来说，这些排课系统可分为两类，一类适合投课时同相同，单班教学的学校情况，显然，这与很多高校的实际教学不一致，所以不具有大众性。一类适合以“教学班”的形式投课，这一类总体比第一类而言，结合了图论中的调度问题，且多与图论中染色问题有关。第二类排课系统的出现，在当时影响很大，虽然有些没有连具体的模型都没有，但是确实与很多学校的实际情况更接近了一步。其次，各种不同算法的数学模型也相应而生，黄干平等提出使用模拟退火算法求解课表间题，采用该方法对中学排课问题进行了实验，该方案的不足之处在于对“温度”设定单调递减，禁止出现预计中的回火问题。束礼菊提出整数规划模型，该模型根据高校村课系统中各位教师对每门课的乐教度与熟练度，统计出相应的绩效评价系数，在此基础上，列出了排课系统中的六项目标，以实现教师群体最优绩效为总目标，以其他目标为约束条件，采用整数规划模型将指派教师讲授各班级特定的课程这一人文决策过程转化为数学组合问题:来优化高校排课，该模型只把教师群体最优绩效为总目标，没有考虑学生群体的特点，因此模型还须进一步改进，李琪等采用遗传算法对排课系统进行建模，得到各班级的课程安排和时间安排、最后在此基础上通过矩阵运算得到上课地点，不足之处在于对部分约束条件未能完全与算法结合。动态规划理论被应用于高校教学管理当中，得出了教学管理中重要的环节-排课的最优策略，另外，图论算法也被用于排课系统中来设计模型。
### 1.3 本文主要任务
本文从排课问题的研究背景、意义及研究现状，分析排课问题的必要性，研究探讨了几种解决排课问题的算法，结合实例分析比较它们的优点和缺点，最终结合图论着色理论给出一种排课算法。
- **第一章绪论**：介绍本文的研究背景及意义、排课问题研究现状和本文研究内容
- **第二章图论基本概念和理论**：概述图论有关概念以及着色理论，包括图的分类、点染色、边染色和全染色等着色理论
- **第三章排课问题算法分析与比较**：分析研究几种经典的排课问题算法，比较其优缺点
- **第四章排课问题研究**：分析排课问题因素和约束条件，并且结合学校排课实例给出图染色排课算法的应用，解决教师、班级、教室的时间冲突现象
- **第五章总结与展望**：总结本文工作，指出本文研究不足之处，以及下一步要做的进一步研究工作
# 二、图论基本概念和理论
## 2.1 图的分类
- **无向图**：边集E(G)为无方向边的集合，任意一条边都代表u连v，以及v连u，每条边都是双向的。如图1所示
- **有向图**：边集E(G)为有方向边的集合，每条边都是单向的，即只能由一个点指向另一个点。如图2所示
- **带权图**：边集E(G)是每条边上有权值的边的集合，同理，带权图也有有向带权图和无向带权图之分，当然，不加权的图可以看成所有边上的权值都是 1。如图3
- **完全图**：对于图中任意两个顶点都是相邻的，称之为完全图，如图4所示
- **无向完全图**：在阶无向图中，图中任意两个顶点间都有一条边相连，则该图称为无向完全图，如图4所示
- **有向完全图**：在阶有向图中，图中任意两个顶点间都有方向相反的边相连，该图称为有向完全图,如图5所示
- **二部图**：设无向图图中,如果图中顶点集 V 可划分为两个互不相交的非空子集X和Y，并且图中的每条边有一个端点属于子集X，另一个端点属于子集Y，则称图G为一个二部图，如图6所示
- **简单图**：在无向图中，如果关联一对顶点的无�
