目前流行地几种排课算法地介绍

目前流行地几种排课算法地介绍

ID:47721608

大小:79.50 KB

页数:10页

时间:2019-11-08

目前流行地几种排课算法地介绍_第1页
目前流行地几种排课算法地介绍_第2页
目前流行地几种排课算法地介绍_第3页
目前流行地几种排课算法地介绍_第4页
目前流行地几种排课算法地介绍_第5页
资源描述:

《目前流行地几种排课算法地介绍》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

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实用文档]}中的某个分配字是否存在相同课程分配位上的相等的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。