基于贪心算法的排课系统的设计与实现

《基于贪心算法的排课系统的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学号：哈尔滨师范大学学士学位论文题目基于贪心算法的排课系统的设计与实现学生指导教师年级2004级专业计算机科学与技术系别计算机科学与技术学院计算机科学与信息工程4哈尔滨师范大学学士学位论文开题报告论文题目：基于贪心算法的排课系统的设计与实现学生姓名：指导教师：年级：2004级专业：计算机科学与技术2008年3月4课题来源：指导教师承担的科研任务课题研究的目的和意义：排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法

2、能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。  目前大家对NP完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这是

3、解决排课问题一个很多的思路。在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此工作非常繁重。加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可以一目了然，对于优化学生的

4、学习进程，评估每位教师对教学的贡献，领导合理决策等都具有重要的意义，必将会大大推进教学的良性循环。这里我们将要设计一个基于贪心算法的排课系统，这必将为教学工作带来方便，而且相对于其他的算法它将更简单、更有效的解决排课问题，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解，而且时间复杂性上要大大的由于其它的解法。4国内外同类课题研究现状及发展趋势：20年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，并利用匈牙利算法解决了三维线性运输问题。此后，人们对课表问题的

5、算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型的简化或补充，而至今还没有一个可行的算法来解决课表问题。    近40年来，人们对课表问题的计算机解法做了许多尝试并提出了大学课表的数学模型。    进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的JeanAubin和JacquesFerland等。目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次

6、分配型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有希望得到成功的办法。  实际使用的情况来看，国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统，排课要想面面俱到是一件很困难的事；另一方面每个学校由于其各自的特殊性，自动排课软件很难普遍实用，特别是在调度的过程中一个很小的变动，要引起全部课程的大调整，这

7、意味着全校课程大变动，在实际的应用中这是很难实现的事。贪心算法近些年来在模式识别、人工智能、机器学习和专家系统领域也得到了广泛的应用，贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不是整体最优上加以考虑，他所作出的选择只是在某种意义上的局部最优的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如图的算法中单源最短路径问题，最小支撑树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。4课题研究的主要内容和方法，研究过程中的主要问题

8、和解决办法：谈利用贪心算法解决这个问题的内容，不要加上其他的部分。主要问题1分析时对问题的分析不够，约束条件分析不完全。2后安排的课程会于已经安排好的课程出现冲突。3贪心法可能会不收敛或者距离最优解较远。解决方法：1、充分做好调查，分析好各个约束条件。2、选择相容课程为未安排