排课专家算法是用来做什么的
1课题背景与研究意义
排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。
目前大家对NP 完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是解决排课问题一个很多的思路。
在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此工作非常繁重。
加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。
2课题的应用领域
本课题的研究对开发高校排课系统有指导作用。
排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参考。
3 课题的现状
年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。次后，人们对课表问题的算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。
近40年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数规划模型将问题归结为求一组0-1变量的解，但是其计算量非常大。解决0-1线性优化问题的分支一定界技术却只适用也规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优化问题，Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。
此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。
进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的Jean Aubin和Jacques Ferland等。目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办法。
在国内，对课表问题的研究开始于80年代初期、具有代表性的有：南京工学院的UTSS（A University Timetable Scheduling System）系统，清华大学的TISER（Timetable SchedulER）系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校的教学体制，不宜进行大量推广。
从实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事。
4解决NP问题的几种算法及其比较
解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思想，包括动态规划、贪心算法、回溯法等。
动态规划法是将求解的问题一层一层地分解成一级一级、规模逐步缩小的子问题，直到可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一颗子问题树。树根是原问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种意义下的最优解。设计一个动态规划算法，通常可按以下几个步骤进行：
1. 分析最优解的性质，并刻划其结构特征。
2. 递归的定义最优解。
3. 以自底向上的方式计算出最优解。
4. 根据计算最优解时得到的信息，构造一个最优解。
步骤1~3是动态规划算法的基本步骤。在只需要求出最优解的情形，步骤4可以省去。若需要求出问题的一个最优解，则必须执行步骤4。此时，在步骤3中计算最优解时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。
（二）贪心算法
当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它，但有时会有更简单、更有效的算法，即贪心算法。顾名思义，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。
在贪心算法中较为有名的算法是Dijkstra算法。它作为路由算法用来寻求两个节点间的最短路径。Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为∞。再按长度的递增顺序生成每条最短路径。事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U。
（三）回溯法
回溯法有“通用的解题法”之称。用它可以求出问题的所有解或任一解。概括地说，回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的一颗状态空间树上，按照深度优先的策略，从根出发进行搜索。搜索每到达状态空间树的一个节点，总是先判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过对该子树的系统搜索，一层一层地向它的祖先节点继续搜索，直到遇到一个还有未被搜索过的儿子的节点，才转向该节点的一个未曾搜索过的儿子节点继续搜索；否则，进入子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根的所有儿子都已被搜索过才结束；而在用来求问题的任一解时，只要搜索到问题的一个解就可结束。 本文来自CSDN博客，转载请标明出处： http://blog.csdn.net/hanpoyangtitan/archive/2009/04/03/4046709.aspx
遗传算法实现自动排课
暑期带了几个学生做自动排课系统。系统以高校为假想服务对象，要求安排好一所高校一学期的课表，包括公共必修课、专业必修课、公共选修课、专业选修课。系统要求在满足教室、老师、学生各自不存在冲突、教室资源符合课程需要等基本前提（硬约束）下，尽量满足一系列优化条件，比如：学生的选修课冲突课时数、老师所带的课程是否是他经常带的课程、老师个人的要求，比如星期几不上课等等。
解决这种优化问题，常用的是遗传算法。关于遗传算法，网上有很多介绍。我这里就简述一下这个算法在自动排课系统中的应用。
应用遗传算法解决实际问题，第一步当然是选择一个合理的编码方案。我们希望能够把整个课表表示为一个二进制串，同时，我们也能够把一个二进制串解码成一个课表。
我们以“课程班级”为基准进行编码。所谓“课程班级”就是指某个班上的某个课。比如19级软件工程1班上的《高等数学》，这就是一个“课程班级”的概念。显然，每个课程班级需要分配一个老师、单双周、每周的上课时间与教室，开始上课的周编号。
---- 我们可以给老师10个二进制位，这最多可以表示1024个老师，已经不少了。然而，这样对老师编码是不科学的。比方说，这个学校虽然有1024个老师，但是具体到《高等数学》这门课，可以带的老师数量就非常有限了。对于任一课程，我们都有一个可以带这门课的老师列表，并给这个列表的老师从0开始编号。我估计，这样编码的话，5个二进制位足够了。这种编码的好处是，任意随机生成的老师一定是符合条件的。
---- 有些课程分单双周，有些课程不分。这些应该不需要编码，而是直接从输入文件中提取的。但是，如果区分单双周，我们需要设定究竟是单周还是双周上课。因此我们用1位二进制来表示这个信息。比如0表示单周上课，1表示双周上课。而如果某个课程班级不区分单双周，则解码时无视这个信息
---- 我们假设每个星期上五天课，每天5节大课（每节大课实际上代表2个课时）。这样，每节课的时间用5位二进制来表示
---- 我们可以假设教室也是10个二进制位，这最多可以表示1024个教室，也不少了。然而，与老师的编码一样，这样粗糙地对教室进行编码也是不科学的。任何一门课程都有基本的教学资源需求（比如投影仪、试验设备等等），对于任何一门课程，都有一个可用教室列表，我们按这个列表来编码更科学。其优点是，任意随机生成的教室一定是符合这门课程要求的。这种编码方案下，我们也可以用10个二进制来表示教室，当然具体数值需要根据实际问题而定。
---- 一节大课于是就是15位二进制，前5位代表时间、后面10位代表教室。每个课程班级周学时是固定的。比如每周2个学时的话，就是15位二进制表示每周的课；4个学时的话，就是30位二进制表示每周的课，等等。
---- 绝大多数课程以第一周开始上课，有些课程以春夏学期的夏学期或秋冬学期的冬学期开始上课，区分单双周的课程还可能从第2周或者夏冬学期的第2周开始上课。
这样我们一个课程班级就编码完成了。而把所有的课程班级的基因放在一起就是一个完整的课表。虽然每个课程班级的基因段长短不一，但是，最终整个个体的基因长度是一样的。
有了上面的分析，编码、解码都不是问题了。接下来就是初始化了。
遗传算法中基因的初始化常常是随机初始化。比如一个课表总长是1000个二进制位，我们随机设定这1000个二进制位（0或1）。这样做可能很多时候这个基因并不满足基本的硬约束要求。这种不合格的个体我们直接予以放弃。我们通常需要随机生成1000个乃至更多个个体，这就是第一代种群。
当然，如果实际问题中，某个资源比较紧张（比如老师数量少，或者教室少，这样极容易出现冲突而不满足基本硬约束），我们这种方案可能要经历比较长的时间才能以随机的方式找到一个合格的个体。极端情况下，资源紧张到理论上只存在一两个可能的合法解，这种情形下就完全不可以使用我们这里的遗传算法方案了。
实际问题中，如果某个资源比较紧张，我们还可以采取一些“改良”的策略。一个基本的策略就是减少资源争夺。比如《高等数学》的老师非常少，那么如果某个老师既可以带《高等数学》也可以带《概率与统计》，那么我们可以限定他只带《高等数学》，以避免资源的争夺。另一种策略是使用其他算法，比如贪心算法，先解决好存在冲突的资源。当然，这种情况下，程序又要复杂很多了。
我们需要对每一个个体进行打分。这个打分通常需要考虑到需求方的要求。比如需求方更倾向于老师带自己熟悉的课，那么我们就需要提高相应分值的权重。打分的要求是每个个体的分值差异不应该太大。比如有些个体1000分，有些个体1分，这样的分值分布非常不合理。我们不希望见到极端大或者极端小的情形。因为我们接下来需要将分值进行归一。
所谓归一，就是说每个个体的最终归一得分就是它的原始得分除以种群所有个体原始得分的总和。这样，最终，所有个体的得分之和是1。
有了得分之后，我们就可以进行选择。采用轮盘赌的方案来随机选择两个个体。所谓轮盘赌，是指你随机从0到1生成一个数字，遍历个体，每个个体的得分依次相加，总得分第一次大于刚才生成的随机数时，就选择当前这个个体。轮盘赌的选择算法能够确保个体被选中的概率大小由它的得分高低决定，得分越高的个体被选中的概率越大。
我们采用这种方法选择两个不同的个体，然后将个体的基因进行交叉、变异操作，生成两个新的个体，也就是子代。如果子代个体不满足基本约束条件，那么予以放弃。我们用这样的算法生成1000个子代个体。
我们还可以把上一代的最优个体直接放入下一代，确保当前的最优基因不会丢失。这有助于加快算法的收敛。
重复这样的步骤，直到算法不能再产生更优的个体为止。
