目前流行的几种排课算法的介绍.doc

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的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此),因此很容易实现停课/开课处理.3.排课算法在上述假设下,自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.从安排的可能性上看,共有(即有A（20，（N-20））)20!/(20-N)!种排法(N的含义见(2)式).如果有4门课,每门课一周上2次,则N=8,这8次课可能的安排方法就会有20!/(20-8)!=5079110400,即50多亿种.如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间.所以排课的前提是必须有一个确定的排课原则.我们采用轮转分配法作为排课原则:从星期一第1时间段开始按{C1,C2,.,Cn}中所列顺序安排完各门课程之后(每门课安排1次),再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合{N1,N2,.,Nn}中给定的值为止.在算法描述中将用{C[1],C[2],.,C[n]}表示{C1,C2,.,Cn},对{N1,N2,.,Nn}和{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进行以下操作:如果N[c-index]>0,则做以下操作:把segment的值写入T[c-index]的第(week-1)33～week33-1位中N[c-index]的值减1如果N[c-index]>0,则置flag=1如果week=5并且segment=4则:置flag=1并转③否则:如果segment=4则:置segment=1且week增1否则:segment增1检测是否已全部安排完毕:如果flag=1则:转②否则:转③③检测是否成功:如果flag=1则:开课次数过多否则:课程安排成功④算法结束显然,本算法的时间复杂度为O(N)(N为每周总开课次数,见(2)式),而存储时间段分配字所用空间为2n个字节(n为课程门数).4.冲突检测算法有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i门课程在人工干预下改成星期数为week、时间段为segment的位置,则根据上述数据结构需做如下运算:T[i]=T[i]&(～(7<<(week-1)*3))+(segment<<(week-1)*3),其中&、～和n分别为按位与、按位取反和按位左移运算符(下同).问题是如何判断是否已有其它课程安排在同一个时间段上.设人工调整的时间段分配字为T[1],则该问题描述为:判断时间段分配字T[1]与{T[2],T[3],.,T[n]}中的某个分配字是否存在相同课程分配位上的相等的非零时间段值,或者说{T[2],T[3],.,T[n]}中是否存在与T[1]冲突的时间段分配字.为简化起见,在以下算法描述中假设所有时间段分配字的最高位为0.算法2冲突检测算法输入T1和{T2,.,Tn}.输出与T1冲突的{T2,.,Tn}中的时间段分配字.①对c-index=2,3,.,n做以下操作:初始化屏蔽字mask=7对星期值week=1,2,3