资源描述：
《目前流行地几种排课算法地介绍》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实用文档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,并存在以下约束关系:b5E2RGbCAP n≤20,(1> N=6n，i=1，
2、Ni≤20.(2>自动排课问题是:设计适当的数据结构和算法,以确定{C1,C2,.,Cn}中每个课程的教案应占据的时间段,并且保证任何一个时间段仅由一门课程占据.p1EanqFDPw2.主要数据结构对于每一门课程,分配2个字节的“时间段分配字”(无符号整数>:{T1,T2,.,Tn}.其中任何一个时间段分配字(假设为Ti>都具有如下格式:DXDiTa9E3dTi的数据类型C语言格式定义为:unsignedint.Ti的最高位是该课程目前是否是有效的标志,0表示有效,1表示无效(如停课等>。其它各位称为课程分配位,每个课程分
3、配位占连续的3个位(bit>,表示某教案日(星期一～星期五>安排该课程的时间段的值,0表示当日未安排,1～4表示所安排的相应的时间段(超过4的值无效>.RTCrpUDGiT在这种设计下,有效的时间段分配字的值应小于32768(十六进制8000>,而大于等于32768的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此>,因此很容易实现停课/开课处理.5PCzVD7HxA3.排课算法在上述假设下,自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.jLBHrnAILg从安排的可
4、能性上看,共有20!/(20-N>!种排法(N的含义见(2>式>.如果有4门课,每门课一周上2次,则N=8,这8次课可能的安排方法就会有20!/(20-8>!=5079110400,即50多亿种.如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间.所以排课的前提是必须有一个确定的排课原则.我们采用轮转分配法作为排课原则:从星期一第1时间段开始按{C1,C2,.,Cn}中所列顺序安排完各门课程之后(每门课安排1次>,再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合{N1,N2,.,Nn}中给定的值为止.在
5、算法描述中将用{C[1],C[2],.,C[n]}表示{C1,C2,.,Cn},对{N1,N2,.,Nn}xHAQX74J0X和{T1,T2,.,Tn}也采用同样的表示法.算法1 排课算法输入 {C1,C2,.,Cn}、{N1,N2,.,Nn}.实用文档输出 {T1,T2,.,Tn}.① 初始化: 星期值week=1 时间段值segment=1 {T[1],T[2],.,T[n]}中各时间段分配字清零② 新一轮扫描课程: 置继续处理标志flag=0 对课程索引值c-index=1,2,.,n进行以下操作: 如果
6、N[c-index]>0,则做以下操作: 把segment的值写入T[c-index]的第(week-1>33～week33-1位中 N[c-index]的值减1LDAYtRyKfE 如果N[c-index]>0,则置flag=1 如果week=5并且segment=4 则:置flag=1并转③ 否则:如果segment=4 则:置segment=1且week增1 否则:segment增1 检测是否已全部安排完毕: 如果flag=1 则:转② 否则:转③③ 检测是否成功:
7、 如果flag=1 则:开课次数过多 否则:课程安排成功④ 算法结束显然,本算法的时间复杂度为O(N>(N为每周总开课次数,见(2>式>,而存储时间段分配字所用空间为2n个字节(n为课程门数>.Zzz6ZB2Ltk4.冲突检测算法有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i门课程在人工干预下改成星期数为week、时间段为segment的位置,则根据上述数据结构需做如下运算:dvzfvkwMI1 T[i]=T[i]&(～(7<<(week-1>*3>>+(segment<<(week-1>*3>
8、,rqyn14ZNXI其中&、～和n分别为按位与、按位取反和按位左移运算符(下同>.问题是如何判断是否已有其它课程安排在同一个时间段上.设人工调整的时间段分配字为T[1],则该问题描述为:判断时间段分配字T[1]与{T[2],T[3],.,T[n实用文档]}中的某个分配字是否存在相同课程分配位上的相等的
