自动排课算法分析.docx

自动排课算法分析 自动排课算法分析 书目 1绪论1．1课题背景与探究意义 1．2课题的应用领域 1．3课题的现状1．4解决NP问题的几种算法及其比拟 2目前流行的几种排课算法的介绍 2．1.自动排课算法 2．2基于优先级的排课算法3基于时间片优先级排课算法描述与分析 3．1排课中的根本原那么 3．2排课的根本要求3．3基于时间片优先级排课算法描述 3．4算法分析 参考资料 1绪论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大学的JeanAubin和JacquesFerland等目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次安排型法等多种方法由于课表约束困难，用数学方法进展描述时往往导致问题规模猛烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。

国外的探究说明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有盼望得到胜利的方法在国内，对课表问题的探究起先于80年头初期、具有代表性的有：南京工学院的UTSS〔AUniversityTimetableSchedulingSystem〕系统，清华大学的TISER〔TimetableSchedulER〕系统，大连理工大学的智能教学组织管理与课程调度等，这些系统大多数都是模拟手工排课过程，以“班”为单位，运用启发式函数来进展编排的但是这些系统课表编排系统往往比拟依靠于各个学校的教学体制，不宜进展大量推广从实际运用的状况来看，国内外研制开发的这些软件系统在管用性上仍不尽如人意一方面缘由是作为一个很困难的系统，排课要想四平八稳是一件很困难的事；另一方面每个学校由于其各自的特别性，自动排课软件很难普遍管用，特殊是在调度的过程中一个很小的变动，要引起全部课程的大调整，这意味着全校课程大变动，在实际的应用中这是很难实现的事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〔三〕回溯法回溯法有“通用的解题法”之称用它可以求出问题的全部解或任一解概括地说，回溯法是一个既带有系统性又带有跳动性的搜寻法它在包含问题全部解的一颗状态空间树上，遵照深度优先的策略，从根启程进展搜寻搜寻每到达状态空间树的一个节点，总是先判定以该节点为根的子树是否确定不包含问题的解假如确定不包含，那么跳过对该子树的系统搜寻，一层一层地向它的祖先节点接着搜寻，直到遇到一个还有未被搜寻过的儿子的节点，才转向该节点的一个未曾搜寻过的儿子节点接着搜寻；否那么，进入子树，接着按深度优先的策略进展搜寻。

回溯法在用来求问题的全部解时，要回溯到根，且根的全部儿子都已被搜寻过才完毕；而在用来求问题的任一解时，只要搜寻到问题的一个解就可完毕2目前流行的几种排课算法的介绍 2．1.自动排课算法 1.问题的描述我们探讨的自动排课问题的简化描述如下:设要支配的课程为{C1,C2,.,Cn},课程总数为n,而各门课程每周支配次数(每次为连续的2学时)为{N1,N2,.,Nn};每周教学日共5天,即星期一～星期五;每个教学日最多支配4次课程教学,即1～2节、3～4节、5～6节和7～8节(以下分别称第1、2、3、4时间段).在这种假设下,明显每周的教学总时间段数为5×4=20,并存在以下约束关系: n≤20,(1) N=6n，i=1，Ni≤20.(2) 自动排课问题是:设计适当的数据构造和算法,以确定{C1,C2,.,Cn}中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.2.主要数据构造对于每一门课程,安排2个字节的“时间段安排字”(无符号整数):{T1,T2,.,Tn}.其中任何一个时间段安排字(假设为Ti)都具有如下格式:Ti的数据类型C语言格式定义为:unsignedint.Ti的最高位是该课程目前是否是有效的标记,0表示有效,1表示无效(如停课等);其它各位称为课程安排位,每个课程安排位占连续的3个位(bit),表示某教学日(星期一～星期五)支配该课程的时间段的值,0表示当日未支配,1～4表示所支配的相应的时间段(超过4的值无效).在这种设计下,有效的时间段安排字的值应小于32768(十六进制8000),而大于等于32768的时间段安排字对应于那些当前无效的课程(既使课程安排位已设置好也如此),因此很简单实现停课/开课处理.出可排课时间。

2． 每一子类的排课处理在对每个子类的排课处理中,我们结合了分治法、贪心法、回溯法三者的思想L首先,依据分治法的思想把整个排课过程分成时间安排和教室安排两个阶段然后,依据贪心法的算法思想,在时间安排时,总是在尚未安排的时间单元中选择上课效果最好的单元而在时间安排发生死锁时,会向上回溯搜寻到发生冲突的最近一个记录,然后对它进展重排以解决冲突详细处理过程如下:1．设定优先级对子类中的课程计算优先级L设优先级函数为: D(g)=J(g)*C1+T(g)*C2+P(g)*C3(1)其中,J(g)表示课程级别,选修课的课程级别设置为1,必修课的课程级别设置为2;T(g)表示该课程的周学时数;P(g)表示该课程的参加人数;C1、C2、C3是可以调整的参数由式(1)可以看出课程级别越高、周学时越多、参与人数越多的课程,其D(g)值越大,其优先级也越高;反之,D(g)值越小,其优先级越低这样,就可以依据计算的优先级的凹凸对课程进展排序,优先级高的优先调度2．查询可用时间单元第1步,初始化某门课程的最大可支配时间数组,为(123456 123456 123456 123456 123456)第2步,找出参与该课程学习的全部班级。

第3步,查询每个班级的时间数组,得到班级的已排课时间,并将其与课程的最大时间数组相“与”,从而得到该课程不能支配的时间单元第4步,依次处理老师时间数组和相关教室时间数组,这样,该课程最终的可支配时间数组就是班级、老师、教室可排课时间的交集3．查找适当的时间模式找到可排课时间后,就应依据课程的周学时数在时间模式库中匹配适当的时间模式完成以上工作后,就确定了课程的上课时间和地点假如在处理中发生死锁,那么可依据回溯法的思想向上回溯搜寻到发生冲突的最近一个记录,然后对它进展重排以解决死锁,假如仍不能解决死锁问题,那么可以将该课程信息输出到冲突列表中3．人工干预的处理计算机自动排课也须要进展人工干预,以便可以使得各个高。