自动排课算法分析报告报告材料.docx

该【自动排课算法分析报告报告材料 】是由【小李飞刀】上传分享，beplayapp体育下载一共【19】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【自动排课算法分析报告报告材料 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。,即算法的计算时间是呈指数增加的,这一论断确定了排课问题的理论深度。关于NP问题完整问题目前在数学上是没有一个通用的算法能够很好地解决。但是好多NP完整问题目拥有很重要的实质意义,比如。大家熟****地路由算法就是很典型的一个NP完整问题,路由要在从多的节点中找出最短路径达成信息的传达。既然都是NP完整问题,那么好多路由算法就能够运用到解决排课问题上,如Dijkstra算法、节点子树剪枝结构网络最短路径法等等。出色beplayapp体育下载适用标准文案目前大家对NP完整问题研究的主要思想是怎样降低其计算复杂度。即利用一个近似算法来取代,力求使得解决问题的时间从指数增加化简到多项式增加。联合到课表问题就是成立一个适合的现实简洁模型,利用该简洁模型能够大大降低算法的复杂度,便于程序实现,这是解决排课问题一个好多的思路。在高等院校中,培育学生的主要门路是教课。在教课活动中,有一系列管理工作,此中,教学计划的实行是一个重要的教课环节。每学期管理人员都要整理教课计划,依据教课计划下达教课任务书,而后依据教课任务书编排课程表。在这些教课调动工作中,既有大批繁琐的数据整理工作,更有谨慎思想的脑力劳动,还要填写大批的表格。所以工作特别沉重。加之,跟着教课改革的进行及“211”工程的实行,新的教育体系对课表的编排提出了更高的要求。手工排课时,信息的上通下达是极其麻烦的,而采纳计算机排课,教课中的信息可以了如指掌,关于优化学生的学****进度,评估每位教师对教课的贡献,领导合理决议等都具有重要的意义,势必会大大推动教课的良性循环。课题的应用领域本课题的研究对开发高校排课系统有指导作用。排课问题的核心为多维资源的矛盾与抢占,对其研究对近似的问题(特别是与时间表有关的问题:如考试排考场问题、电影院排座问题、航空航线问题)也是个参照。课题的现状年月末,外国就有人开始研究课表编排问题。1962年,Gotlieb曾提出了一个课表问题的数学模型,并利用匈牙利算法解决了三维线性运输问题。次后,人们对课表问题的算法、解的存在性等问题做了好多深入商讨。可是大部分文件所用的数学模型都是Gotlieb的数学模型的简化或增补,而到现在还没有一个可行的算法来解决课表问题。近40年来,人们对课表问题的计算机解法做了很多试试。此中,课表编排的整数规划模型出色beplayapp体育下载适用标准文案将问题归纳为求一组0-1变量的解,可是其计算量特别大。解决0-1线性优化问题的分支必定界技术却只合用也规模较小的课表编排,Mihoc和Balas(1965)将课表公式化为一个优化问题,Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题,而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。别的,有些文件试图从图论的角度来求解排课表的问题,可是图的染色问题也是NP完整问题,只有在极为简单的状况下才能够将课表编排转变为二部图般配问题,这样的数学模型与实质相差太远,所以关于大部分学校的课表编排问题来说没有适用价值。进入九十年月此后,外国对课表问题的研究仍旧十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的JeanAubin和JacquesFerland等。目前,解决课表方法的问题有:模拟手工排课法,图论方法,拉格朗日法,二次分派型法等多种方法。因为课表拘束复杂,用数学方法进行描绘时常常致使问题规模强烈增大,这已经成为应用数学编程解决课表问题的巨大阻碍。外国的研究表示,解决大规模课表编排问题纯真靠数学方法是行不通的,而利用运筹学中分层规划的思想将问题分解,将是一个有希望获得成功的方法。在国内,对课表问题的研究开始于80年月早期、拥有代表性的有:南京工学院的UTSS(AUniversityTimetableSchedulingSystem)系统,清华大学的TISER(TimetableSchedulER)系统,大连理工大学的智能教课组织管理与课程调动等,这些系统大部分都是模拟手工排课过程,以“班”为单位,运用启迪式函数来进行编排的。可是这些系统课表编排系统常常比较依靠于各个学校的教课体系,不宜进行大批推行。从实质使用的状况来看,国内外研制开发的这些软件系统在适用性上仍不尽善尽美。一方面原由是作为一个很复杂的系统,排课要想八面玲珑是一件很困难的事;另一方面每个学校由于其各自的特别性,自动排课软件很难广泛适用,特别是在调动的过程中一个很小的改动,出色beplayapp体育下载适用标准文案要惹起所有课程的大调整,这意味着全校课程大改动,在实质的应用中这是很难实现的事。4解决NP问题的几种算法及其比较解决NP完整问题只好依凑近似算法,所以下边介绍几种常用算法的设计思想,包含动向规划、贪婪算法、回溯法等。动向规划法是将求解的问题一层一层地分解成一级一级、规模逐渐减小的子问题,直到能够直接求出其解的子问题为止。分解成的所有子问题按层次关系组成一颗子问题树。树根是原问题。原问题的解依靠于子问题树中所有子问题的解。动向规划算法往常用于求一个问题在某种意义下的最优解。设计一个动向规划算法,往常可按以下几个步骤进行:,并刻划其结构特点。。。,结构一个最优解。步骤1~3是动向规划算法的基本步骤。在只需要求出最优解的情况,步骤4能够省去。若需要求出问题的一个最优解,则一定履行步骤4。此时,在步骤3上当算最优解时,往常需记录更多的信息,以便在步骤4中,依据所记录的信息,迅速地结构出一个最优解。(二)贪婪算法当一个问题拥有最优子结构性质时,我们会想到用动向规划法去解它,但有时会有更简单、更有效的算法,即贪婪算法。顾名思义,贪婪算法老是做出在目前看来最好的选择。也就是说贪婪算法其实不是整体最优上加以考虑,他所作出的选择不过在某种意义上的局部最优的选择。固然贪婪算法不是对所有问题都能获得整体最优解,但对范围相当广的很多问题它能产生整体最优解,如图的算法中单源最短路径问题,最小支撑树问题等。在一些状况下,即便贪婪算法不可以获得整体最优解,但其最后结果倒是最优解的很好的近似解。出色beplayapp体育下载适用标准文案在贪婪算法中较为出名的算法是Dijkstra算法。它作为路由算法用来追求两个节点间的最短路径。Dijkstra算法的思想是:倘若G有n个极点,于是我们总合需要求出n-1条最短路径,求解的方法是:初试,写出V0(始极点)到各极点(终极点)的路径长度,或有路径,则令路径的长度为边上的权值;或无路经,则令为∞。再按长度的递加次序生成每条最短路径。事实上生成最短路径的过程就是不停地在始极点V何终极点W间加入中间点的过程,因为在每生成了一条最短路径后,就有一个该路径的终极点U,那么那些还未生成最短路径的路径就会因为经过U而比本来的路径短,于是就让它经过U。(三)回溯法回溯法有“通用的解题法”之称。用它能够求出问题的所有解或任一解。归纳地说,回溯法是一个既带有系统性又带有跳跃性的搜寻法。它在包含问题所有解的一颗状态空间树上,按照深度优先的策略,从根出发进行搜寻。搜寻每抵达状态空间树的一个节点,老是先判断以该节点为根的子树能否必定不包含问题的解。假如必定不包含,则跳过对该子树的系统搜寻,一层一层地向它的先人节点持续搜寻,直到碰到一个还有未被搜寻过的儿子的节点,才转向该节点的一个不曾搜寻过的儿子节点持续搜寻;不然,进入子树,持续按深度优先的策略进行搜寻。回溯法在用来求问题的所有解时,要回溯到根,且根的所有儿子都已被搜寻过才结束;而在用来求问题的任一解时,只需搜寻到问题的一个解即可结束。:设要安排的课程为{C1,C2,.,Cn},课程总数为n,而各门课程每周安排次数(每次为连续的2学时)为{N1,N2,.,Nn};每周教课日共5天,即礼拜一~礼拜五;每个教课日最多安排4次课程教出色beplayapp体育下载适用标准文案学,即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个字节的“时间段分派字”(无符号整数):{T1,T2,.,Tn}.此中任何一个时间段分派字(假定为Ti)都拥有以下格式:Ti的数据种类C语言格式定义为:,0表示有效,1表示无效(如休课等);其余各位称为课程分派位,每个课程分派位占连续的3个位(bit),表示某教课日(礼拜一~礼拜五)安排该课程的时间段的值,0表示当天未安排,1~4表示所安排的相应的时间段(超出4的值无效).在这类设计下,有效的时间段分派字的值应小于32768(十六进制8000),而大于等于32768的时间段分派字对应于那些目前无效的课程(既使课程分派位已设置好也这样),所以很简单实现休课/,自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.从安排的可能性上看,共有20!/(20-N)!种排法(N的含义见(2)式).假若有4门课,每门课一周上2次,则N=8,这8次课可能的安排方法就会有20!/(20-8)!=5079110400,,:从礼拜一第1时间段开始按{C1,C2,.,Cn}出色beplayapp体育下载适用标准文案中所列次序安排完各门课程以后(每门课安排1次),再按该次序持续向后边的时间段进行安排,直到所有课程的开课次数切合{N1,N2,.,Nn}{C[1],C[2],.,C[n]}表示{C1,C2,.,Cn},对{N1,N2,.,Nn}和{T1,T2,.,Tn}{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出色beplayapp体育下载适用标准文案不然:segment增1检测能否已所有安排完成:假如flag=1则:转②不然:转③检测能否成功:假如flag=1则:开课次数过多不然:课程安排成功④算法结束明显,本算法的时间复杂度为O(N)(N为每周总开课次数,见(2)式),而储存时间段分派字所用空间为2n个字节(n为课程门数).,需要人工调整某些课程的安排时间,如把第i门课程在人工干涉下改成礼拜数为week、时间段为segment的地点,则依据上述数据结构需做以下运算:T[i]=T[i]&(~(7<<(week-1)*3))+(segment<<(week-1)*3),此中&、~和n分别为按位与、按位取反和按位左移运算符(下同).[1],则该问题描绘为:判断时间段分派字T[1]与{T[2],T[3],.,T[n]}中的某个分派字能否存在相同课程分派位上的相等的非零时间段值,或许说{T[2],T[3],.,T[n]}中能否存在与T[1],{T2,.,Tn}.输出与T1矛盾的{T2,.,Tn}中的时间段分派字.①对c-index=2,3,.,n做以下操作:初始化障蔽字mask=7对礼拜值week=1,2,3,4,5做以下操作:假如T[1]&mask等于T[c-index]&mask,并且两者不等于0则:T[1]与T[c-index]相矛盾,转①mask左移3位(或乘8)算法结束本算法时间复杂度为O(n)(n为课程门数),进行搜寻般配,取最初般配的值;拥有据有空间少,运算速度快的特点。但其未对数据进行择精选用,所以不可以对教课资源(教师、教室)合理分派,也不可以满足一些特别要求(比方有些老师喜爱上午上课,有些老师倾向于集中式上课;有些课程安排到上午会更适合些,有些课程不可以安排到上午等)。,排课问题是一个在时间、教师、学生和教室四维空间,以教课计划和各样特别要求为拘束条件的组合规划问题。其实质就是解决各要素之间的矛盾。在设计算法时,为了降低课程调动的算法复杂性,我们主要采纳了化整为零的思想及优先级算法:.,在每个等价类之间只存在地址上的矛盾,而出色beplayapp体育下载适用标准文案没有时间上的矛盾。而后依照的大小,从大到小进行办理。等价类的区分能够先按年级分,然后再按系别分,以下所示:,先按年级分为四个类:99级(N1),98级(N2),97级(N3),96级(N4),而对每一个等价类N1、N2、N3、N4又能够按院系分为若干个子类,而后对每个子类分别进行排课办理,,我们采纳了教室分类的方法,以便尽可能在课程编排过程中防止上课人数少的课程盲目霸占容量大的教室现象。第一将教室依照其种类分为若干个等价类,以下所示,而后,依据教室的容量再分别对每个教室等价类进行区分:如分为0~30人、30~60人、60~90人、90~120人、120~180人等若干种教室等价类的区分:教室种类等价类R教室种类等价类R一般教室R1听力教授R5投影教室R2物理实验室R6多媒体教室R3化学实验教室R7出色beplayapp体育下载