高校排课系统设计含需求分析数据库算法和部分代码毕业论文.doc

沈阳理工大学学士学位论文高校排课系统设计含需求分析数据库算法和部分代码毕业论文目 录1 绪论11.1 课题背景和意义11.2 排课问题发展现状11.3 排课算法简介21.3.1 回溯搜索算法21.3.2 遗传算法21.3.3 贪心算法31.3.4 模拟退火算法31.4 课题主要内容31.4.1 软件设计的主要功能31.4.2 论文结构说明42 ASP.NET开发平台52.1 基于ASP.NET平台开发概述52.1.1 ASP.NET概述52.1.2 ASP.NET的优点52.1.3 ASP.NET的发展前景72.2 ADO.NET概述73 排课系统分析103.1 排课问题分析103.1.1 排课基本原则103.1.2 排课资源分析103.1.3 排课冲突分析113.2 系统分析113.2.1 需求分析113.2.2 系统功能分析124 数据库设计144.1 数据库概念结构设计144.2 数据库逻辑结构设计144.3 数据库物理结构设计155 排课系统算法及功能的实现185.1 回溯算法简介185.1.1 回溯算法的基本思想185.1.2 回溯算法的求解步骤185.1.3 回溯算法在排课系统上的特点195.2 排课系统算法分析195.3 排课过程195.3.1 自动排课算法流程195.3.2 自动排课程序215.4 功能的实现245.4.1 用户登录245.4.2 查询功能设计275.4.3 排课管理界面346 排课系统测试376.1 系统测试数据376.2 系统测试结果37结 论39致 谢40参考文献41附录A 英文原文42附录B 中文翻译5259沈阳理工大学学士学位论文1 绪论1.1 课题背景和意义每个新学期开始，对于学校教务科来说首要而急需完成的任务是：如何合理而高效的排课。其本质是将课程、教师和学生在合适的时间段内分配到合适的教室中。但由于涉及到的问题较多，同时学校扩招，学生和课程数量比以往大大增加，教室资源明显不足，在这种情况下排课很难在同时兼顾多重条件限制的情况下用人工方式排出令教师和学生都满意的课表。虽然排课问题很早以前就成为众多科研人员和软件公司的研究课题，但是真正投入使用的排课软件却很少。原因是多方面的，其中算法的选择是最关键的一个问题，S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。然而由于穷举法成本太高，时间太长，根本无法在计算机上实现。如果假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制情况下，能够推出的可能组合就有n*m*k种，如此高的复杂度是目前计算机所无法承受的。这就促使我们必须采用一些以计算机为辅助的手段来帮助。1.2 排课问题发展现状国外对于课表问题的研究始于20世纪50年代。1963年Gotlieb在他的论文中提出了课表问题的数学模型，并用匈牙利算法解决了三维线性运输问题1。直到1976年S.Even、Tim B.Cooper等人在他们的论文中证明了排课问题是一个NP完全问题2，人们才将注意力更多地转向课表编排实用算法的探索与研究。近几十年，国外对于排课算法的研究依然很活跃，Ferland等人把排课问题化成整数规划来解决3，但计算量很大，其仅仅适用于规模很小的课表编排，对于大规模复杂的排课情况，至今没有一个切实可行的算法。还有人用图论的染色体问题来解决课表问题，但是遗憾的是染色体问题本身也是NP完全问题。除此之外，还有印度Vastapur大学管理学院ArabindaTripathy的拉格朗日松弛法4等求解算法。我国对于排课问题的研究较晚，始于上个世纪80年代初期。1984年林漳希和林尧瑞发表了在排课问题上的实验性研究成果人工智能技术在课表编排中的应用5。许多高校也进行了一些排课系统软件的研究，具有代表性的有南京工学院的UTSS（A University Timetable Scheduling System）系统6、清华大学的TISER（Timetable SchedulER）系统、大连理工大学的智能教学组织管理及课程调度系统7、浙江大学的正方现代教学管理信息系统等。1.3 排课算法简介时间表问题(TTP)是典型的组合优化和不确定性调度问题，该问题已经被证明是NP完全问题，广泛应用于学校课程安排、会议日程安排、体育比赛和航班时刻表的制定等。由于问题的复杂性，一般只能得到较佳解算法。常见的算法有：1.3.1 回溯搜索算法回溯算法(Backtracking Algorithm)也叫试探法，它是一种系统地搜索问题的解的方法。它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。基于回溯法解决排课问题，在使用初期，没有足够的信息可能会出现死锁，引起回溯失败。失败的原因一般为：教室资源不足；安排课程过多或约束条件过于苛刻。1.3.2 遗传算法遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则8。近几十年，很多人使用遗传算法来解决时间表问题，虽然取得了一定成果，但是仍有不足。其主要表现在，只能在排课模型较简单、限制条件有限情况下求解，且速度较慢，系统开销较大。1.3.3 贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解9。在贪心算法中较为有名的算法是Dijkstra算法。它作为路由算法用来寻求两个节点间的最短路径。Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为。再按长度的递增顺序生成每条最短路径。事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U10。1.3.4 模拟退火算法模拟退火(Simulated Annealing)算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态11，最后在常温时达到基态，内能减为最小。模拟退火算法可以在较大的解空间内用较短的时间找到最优解，用其解决编排课 程表这样的组合优化问题是很有效的。但是模拟退火算法受收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点所限。1.4 课题主要内容1.4.1 软件设计的主要功能在论文阶段，对排课系统进行系统分析、数据库设计、系统设计和界面设计，最后对排课系统进行测试。这个课题设计用到的开发平台是visual studio 2010，在ASP.NET的特定环境下实现的。软件的内容主要包括排课管理、信息查询二大部分。通过整合，系统的基本模块为：（1）自动排课模块:该模块是系统的核心模块，通过对系统管理员录入的基本信息，通过加权优先级自动生成排课成功的课表。（2）手动调整模块:由于某些特殊因素，可能存在排课失败或临时调整的情况，手动调整可以在不影响硬性约束条件下满足这个需求。（3）信息查询模块:包括对特定班级课表的浏览、特定教师课表的浏览操作。另外系统还设置了用户管理模块归并在系统中，用户权限分为三类：学生用户、教师用户和管理员用户。其中学生用户只有浏览课表的权限；教师用户只有查找自己课程时间的权限；管理员用户则拥有排课，修改，查找单独课表的权限。1.4.2 论文结构说明论文整体分为六大章，从基本的课题题目的理解到设计系统的后期测试，层层递进。第一章，也就是绪论。主要介绍的是“基于回溯算法的高校排课系统的设计与实现”这个课题的背景以及发展前景。同时还介绍了回溯算法与其他类似算法的概念。第二章，主要介绍了本系统的开发使用平台ASP,NET开发平台。介绍了ASP.NET平台的概念、优点以及数据库ADO.NET的介绍。第三章，主要是对课题的进一步分析。对排课系统进行排课原则分析、排课资源分析、排课冲突分析。也对整个系统的需求分析进行了简单的阐述。第四章，是系统数据构造的主要章节。这一章节具体的写出了数据库的概念结构、逻辑结构和物理结构，完整的看出本系统所需要的各种数据结构，也更加直观的阐明了系统数据的设计思想与方法。第五章，是系统实现与功能介绍的主要章节。介绍了如何使用回溯算法实现排课系统的，以及排课系统的其他功能，如：学生如何查看课程表，教师如何查看课程安排等。第六章，说明了系统的测试数据和测试过程。以上就是论文的主要内容，当然论文的内容还不够全面，还需要完善。2 ASP.NET开发平台2.1 基于ASP.NET平台开发概述2.1.1 ASP.NET概述ASP.NET是微软推出的ASP的下一代Web开发技术，作为一种网络应用的商业开发模式，涉及许多网络应用方面的知识。同时，作为Microsoft.NETFramework平台的一部分，ASP.NET提供了一种基于组件的、可扩展且易于使用的方式来构建、部署及运行面向任意浏览器和移动设备的Web应用程序。ASP.NET是Web开发领域的最前沿的技术，是其中的佼佼者，在构建基于HTTP协议进行传输的分布式应用程序方面，它是目前最先进，特征最丰富、功能最强大的平台。2.1.2 ASP.NET的优点1、与浏览器无关ASP.NET是一个与浏览器无关的程序设计框架，利用它编写的应用程序可以与最新版本的InternetExplorer、NetscapeNavigator等常用的浏览器兼容。2、将业务逻辑代码与显示逻辑分开在ASP.NET中引入了“代码隐藏”这一新概念，通过在单独的文件中编写表示应用的业务逻辑代码，使其与HTML编写的显示逻辑分开，从而更好的理解和维护应用程序，并使得程序员可以独立于设计人员工作。3、新的集成开发环境VisualStodio.NET提供了一个强大的、界面友好的集成开发环境，以使开发人员能够轻松地开发Web应用程序。4、简单性和易学性ASP.NET使得运行一些平常的任务如表单的提交、客户身份的验证、分布系统和网站配置变的非常简单。ASP.NET包含称为ASP.NET换件的HTML服务器控件集合，这些控件可通过脚本以程序方式使用。另外，它还包括一组称为“Web服务器控件”都有自己的属性、方法和事件，用于控制控件在应用程序中的外观和行为。所有ASP.NET控件和其他对象都可引发事件，可通过代码以程序方式处理这些事件，从而更好的管理代码。在ASP.NET中，有一组用于进行用户验证的控件，可以大大减少验证代码和编写量。它还支持Cookie的管理和对未经授权的登录进行重定向。5、用户账户和角色ASP.NET允许创建“用户账户”和“角色”以便每个用户能访问不同的代码和可执行代码，从而提高应用程序的安全性。6、多处理器环境的可靠性ASP.NET是一种可以用于多处理器的开发工具，它在多处理环境下用特殊的无缝技术，大大提高了运行速度。即使现在的ASP.NET应用软件是为一个处理器开发的，将来多处理器运行时不需要任何改变就能提高他们的效能。7、可扩展性ASP.NET是一项可扩展技术。为了提高ASP.NET应用程序的可扩展性，改进了服务器的通行，使得可以在多台服务器上进行一个应用程序。8、高效的可管理性ASP.NET使用分组的配置系统，使服务器环境和应用设置更加简单。因为配置信息都保存在基于XML的文本文件中，新的设置不需要启动本地的管理工具就可以实现。这种被称为“Zero Local Administration”的哲学观念使ASP.NET的基于应用的开发更加具体和快捷。一个ASP.NET的应用程序在一台服务器系统的安装只需要简单的拷贝一些必须的文件，而不需要重新启动系统。9、执行效率的大幅提高不像以前的ASP即时解释程序，ASP.NET是将服务器端首次运行时进行编译执行，使得应用程序的执行效率有了很大的提高。10、易于配置和部署利用纯文本配置ASP.NET应用程序，可在程序运行时上传或修改配置文件，而无需重新启动服务器。部署或替换已编译的代码时也无需重新启动服务器，ASP.NET会自动将所有新的请求指向新代码。11、灵活的输出缓存根据应用程序的需要，ASP.NET可以缓存页数据、页的一部分或整个页。缓存的项目可以依赖缓存中的文件或其他项目，或者可以根据过期策略进行刷新。12.、国际化ASP.NET在内部使用Unicode以表示请求和响应数据。可以为每台计算机、每个目录和每页配置国际化设置。13、跟踪和调试ASP.NET提供了跟踪服务，该服务可在应用程序级别调试过程中启用。可以选择页面的信息，或者使用应用程序级别的跟踪查看工具查看信息，在开发和应用程序处于生产状态时，ASP.NET支持使用.NET Framework 调试工具进行本地和远程调试。当应用程序处于成产状态时，跟踪语句能够留在产品代码中而不会影响性能。14、.NET Framework 集成因为ASP.NET是.NET Framework的一部分，整个平台的功能灵活性对Web应用程序都是可用的。也可从Web上流畅地访问 .NET类库以及消息和数据访问解决方案。ASP.NET是独立于语言之外的，所以开发人员能选择最适于应用程序的语言。另外，公共语言运行库的互用性还保存了基于COM开发的现有投资。2.1.3 ASP.NET的发展前景ASP.NET3.5的推出背景，是整个开发平台的重新整合，VisualStudio2010，WindowsServer2010和SQLServer2010在很短的时间内相继推出，表明一个强烈的信号，这就是微软已经把操作系统、数据库和编程平台高度集成起来，在强有力的技术支持下，把.NET系列产品推向一个新的阶段。2.2 ADO.NET概述无论是什么样的开发工具或者开发语言，开发出来的的应用程序大部分都是与数据库相关的应用程序。同样，ASP.NET也不例外，为此.NETFramework提供的ADO.NET访问数据的类库，类库中定义了丰富的类，用来访问和操作各种各样的数据库，它最主要的设计理念是简单和高效。有了ADO.NET底层接口和现代对象模型的简单性，我们便能获得强大的功能和良好的性能。在与传统的ADO数据访问技术尽量保持一直的基础上，ADO.NET提供了更多的支持和更高效的访问方式。在应用程序访问数据库的技术上，微软公司做了多种尝试并持续的进行更新，为了支持日新月异的数据库系统，微软公司在数据库访问技术上经历了7次重大的技术更新，如图2.1所示。图2.1 微软公司数据访问技术的发展历程微软的每一次技术更新并不是替换原有的数据访问方式，而是在原方式上作出重要的扩充。所以在现在的Windows系统中，控制面板里仍然能够看到设置ODBC数据源的选项。ADO.NET是一个广泛的类组，用于访问数据库。它有6个基本的命名空间，除了这些命名空间之外，每个新的数据提供程序还有自己的命名空间。下面将介绍一下这6个基本命名空间，如表2.1所示：表2.1 基本命名空间命名空间说 明System.Data这个命名空间是ADO.NET的核心，它包含所有数据提供程序使用的类，这些类可表示表、列、行和DataSet。它包含几个非常有用的接口，例如 IDbCommand、IDbConnection和IDbDataAdapter。这些接口由所有的受管制提供程序使用，允许它们进入ADO.NET的核心。System.Data.Common这些接口由所有的受管制提供程序使用，允许它们进入ADO.NET的核心。System.Data.OleDb这个命名空间定义了常用的类，用作数据提供程序的基类。所有的数据提供程序都共享这些类。例如DbConnection和DbDataAdapter。System.Data.Odbc这个命名空间定义了用.NET OleDb数据提供程序处理OLE-DB数据源的类，它包含OleDbConnection和OleDbCommand等类。System.Data.SqlClient这个命名空间为SQL Server 7.0或更高版本的数据库定义了一个数据提供程序，它包含SqlConnection和SqlCommand等类。System.Data.SqlTypes这个命名空间为SQL Server 7.0或更高版本的数据库定义了一个数据提供程序，它包含SqlConnection和SqlCommand等类。除此之外，ADO.NET有5个不同类型的类，分别是Disconnected、Shared、Data Providers、SqlBulkCopy和SqlBulkCopyColumnMapping。下面将对这5个类做详细的描述，如表2.2所示：表2.2 ADO.NET 5个不同类型的类类别说明DisconnectedDisconnected类为ADO.NET框架提供了基本结构。这个类的一个示例是DataTable类，该类的对象可以在不依赖某个数据提供程序的情况下存储数据。SharedShared类构成了数据提供程序的基类，由所有的数据提供程序共享。Data ProvidersData Providers类可以处理不同类型的数据源，它们用于在特定的数据库上执行所有的数据管理操作。例如，SqlClient数据提供程序只能处理SQL Server数据库。SqlBulkCopySqlBulkCopy类有一系列属性和方法，它们提供了一些信息，如目录表名、批量大小、时间期限和列映射，可以定制批量复制操作。SqlBulkCopyColumnMappingSqlBulkCopyColumnMapping类可以在源表和目录表之间映射列。它提供了一系列重载构造函数和一组属性，通过名称或索引来制定源列和目标列。在实例化这个类的对象后，就可以调用Add方法，在SqlBulkCopyColumnMappingCollection类的对象中添加或删除它们。 ADO.NET作为.NET时代的数据库访问解决方案，具有更好的通用性，它除了包含具有典型数据库功能的类库，如索引、排序、浏览等，同时ADO.NET还在理念上更多的考虑应用程序的调用。3 排课系统分析3.1 排课问题分析3.1.1 排课基本原则高校排课是一件非常复杂的事情，涉及到几十个专业、上千位教职工和上万名学生。编排课表要处理好教师、教室、学生和时间等多种冲突，编排是否科学、合理，将关系到教学的效率和效果。要排出科学、合理和实用的课程表，必须满足下列排课原则12：1、同一教师不能同时给两门或两门以上的不同课程授课；2、同一教室不能同时安排两门或两门以上的不同课程；3、尽量保证每个教师的工作时间要错开，即在上课的时间上不能让一个教师连续完成多个教学工作；这里把1、2、3称为硬性约束，其余称为软性约束，硬性约束必须满足，而软性约束要视情况而定。3.1.2 排课资源分析排课是一个有限资源、多任务分配的问题，它常常涉及到多项资源的使用和分配问题。教学资源是指保证教学实施的教师、教室、班级和时间等。在排课过程中的资源主要有：1、教师资源：同一教师可以上不同的课程，也可以给不同班级上同一课程。教师资源描述如公式（3-1）所示。Teacher=Teacher1，Teacher2，Teacher3，Teacheri (3-1)2、教室资源：教室能包含的人数不同，要判断教室是否可以容纳班级学生。教室资源描述如公式（3-2）所示。Room=Room1，Room2，Room3，Roomi (3-2)3、时间资源：一般每两小节课为一个时间片，在这个时间片内只可安排一门课。设每天有n个时间片，每周有m个工作日，那么时间资源描述如公式（3-3）所示。Time= (3-3)3.1.3 排课冲突分析课表的编排过程本身是个充满矛盾的过程，排课冲突是指上课班级、上课时间、上课教师、上课教室和所开课程在排列组合中为争夺某一资源，而产生使教学工作不能正常进行的现象。课表编排的目的就是处理这些冲突，因此要保证排课系统合理，必须抓住以下冲突：1、班级冲突：同一班级的学生同一时间只能在一个教室学习一门课程。2、教师冲突：同一教师同一时间只能在一个教室教授一门课程。3、教室冲突：同一教室同一时间只能安排一门课程；3.2 系统分析3.2.1 需求分析在传统排课中，安排各班级上课的时间需要人工实现，而且经常会出现同时有多个班级要使用教室的冲突，既耗时又耗精力。随着计算机技术的不断发展，计算机技术在各领域的充分完美应用，以学校的教务管理为该系统的应用背景，开发一个智能排课系统。需求分析的任务是通过详细调查现实世界要处理的对象，充分了解系统的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。新系统必须充分考虑今后可能的扩充和改变。此系统主要是针对高校的课程编排系统，其主要内容就是利用计算机实现基础数据的处理、课程的自动编排、课表的查询等多种功能，作为一个完整的系统，涉及以下需求：1、基础数据的处理系统中会涉及到许多基础数据，这些数据包括学院、班级、教师、教室、课程等信息。2、排课处理排课处理是本系统的核心，分为以下三个部分：（1）排课准备进行排课之前，要根据课程以及老师安排专业课程；然后初始化班级、教师、教室的时间片占用矩阵。（2）自动排课经过排课准备之后，通过回溯算法自动编排上课时间和地点。（3）手动保存排课成功之后，可以点击保存按钮对当前排好的课程进行保存。3.2.2 系统功能分析首先对现有系统进行分析，现有系统是信息的重要来源。分析已有系统的功能和实现，从而确定新系统的设计目标和模型。由于条件有限，调研主要是在网上进行。即通过在网上已有的排课系统来了解其具备的功能。系统功能结构图如图3.1所示。高校排课系统用户登录排 课 管 理学 员 登 陆教 师 登 录管理员登录自 动 排 课保 存 课 表图3.1 系统功能结构图各模块的详细功能描述如下：根据需求分析与系统功能目标，结合实际情况本系统模块设计分为如下几个功能模块：1、用户登录：在这个模块中有三种用户的登录方式，包括以下几个方面。（1）学生用户：登陆后，可以查看自己的课程安排。（2）教师用户：登陆后，可以查看教师自己的课程的上课时间和教室地点。（3）管理员登录：登陆后，可以查看某个学员或教师的课程信息。可以针对某个专业的课程进行排课，并可以进行手动修改。2、排课管理：在这个模块中提供对排课过程有关的信息，包括以下几个方面。（1）自动排课：这一模块是整个系统的核心部分，通过选择不同的院系专业，对各个专业分别进行自动排课操作，取得最后的排课结果。（2）保存课表：这一过程是排课结束后，对排课结果进行保存的过程。保存课表将以EXCEL的形式保存起来，保存时的名称以专业名称命名，方便以后的查找。目前，我所做的系统只能实现以上功能，功能还不够全面不够强大，这个是我今后需要完善的地方。4 数据库设计高校排课系统的数据库内容较多，应为高校上课是一个老师对应多门课程，一个班级对应多个课程，同时还有教室和上课时间的限制，所以数据库设计起来内容较多，较为复杂。4.1 数据库概念结构设计概念结构设计的任务是在需求分析阶段产生的需求说明书的基础上，按照特定的方法把它们抽象为一个不依赖于任何具体机器的数据模型，即概念模型13；概念模型使设计者的注意力能够从复杂的实现细节中解脱出来，而只集中在最重要的信息的组织结构和处理模式上14。概念数据模型，通常利用实体关系图（E-R图）来实现。它描述系统中的各个实体以及相关实体之间的关系。排课系统的E-R图，如图4.1所示。图4.1 排课系统E-R图4.2 数据库逻辑结构设计数据库的逻辑结构设计就是把概念结构设计阶段设计好的基本E-R图，转换为与选用的 DBMS产品所支持的数据模型相符合的逻辑结构。这里我们使用SQL Server的关系模型结构。排课系统的E-R图（概念模型）转换为关系模型（逻辑结构）如下（其中下划线为主键、#为外键）：管理员信息（ID，姓名，密码）学生信息（ID，姓名，性别，院系，专业，密码，班级ID#）院系信息（ID，学院名称，专业名称）班级信息（班级ID，班级名称，院系ID#，人数）教室信息（ID，所属学院，名称，容量）教师信息（ID，姓名，院系，密码）课程信息（ID，课程名称，教师姓名，教师ID#，院系ID#）4.3 数据库物理结构设计数据库的物理结构设计是对已经确定的逻辑数据结构，利用数据库管理系统所提供的方法、技术，以较优的数据存储结构、数据存取路径、合理的数据存放位置以及存储分配，设计出一个高效的、可以实现的物理数据结构，即数据表。本系统的数据表如下：1. 管理员信息表表管理员信息主要用来储存管理员信息，包括代码，姓名，密码，其中代码由4位数字表示，如图4.2所示。图4.2 管理员信息表结构2. 学生信息表表学生信息主要用来储存学生信息，包括代码，姓名，性别，院系，专业，密码，班级ID，其中代码由10位数字表示，如图4.3所示。图4.3 学生信息表结构3、院系信息表表院系信息主要用来存储学院信息，包括学院代码、学院名称、专业名称，其中院系代码由6位数字组成，如1003代表信息学院。学院信息表结构，如图4.4所示。图4.4 院系信息表结构4、班级信息表表班级信息用于存储班级信息，包括班级代码、班级名称，院系ID，人数，其中班级代码由8位数字组成，如100305代表10级信息学院计算机专业五班。班级信息表结构，如图4.5所示。图4.5 班级信息表结构5、教室信息表表教室用于存储教室信息，包括教室代码、所属学院，名称，容量。其中教室代码是由1开始增加的字段。教室信息表结构，如图4.6所示。图4.6 教室信息结构6、教师信息表表教师信息用于存储教师信息，包括教师代码，姓名，院系，密码，其中教师代码是由3为数字组成的。教师信息表结构，如图4.7所示。图4.7 教师信息表结构7、课程信息表表课程信息用来存储课程信息，包括课程代码、课程名称，教师姓名，教师ID，院系ID，其中课程代码为由1开始增加的字段，课程信息表结构，如图4.8所示。图4.8 课程信息表结构8、教室时间表表教室时间用来存储排课过程中教室时间片占用情况，具体结构如图4.9 教室时间结构所示。教室ID时间片1时间片2时间片20123000000000100550图4.9 教室时间表结构9、教师时间表表教师时间用来存储排课过程中教师时间片占用情况，具体结构如图4.10 教师时间结构所示。教师ID时间片1时间片2时间片201001011020000000001110550图4.10 教师时间表结构5 排课系统算法及功能的实现本章主要介绍的是回溯算法的基本思想和算法的特点，分析了回溯算法在排课系统应用上与其他算法的不同之处。同时，对排课思想进一步的分析，分析了教师在时间上的冲突与教室在时间上的冲突的判断方式。并对排课系统的各项功能进行了进一步的详细介绍。5.1 回溯算法简介5.1.1 回溯算法的基本思想回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合条件的位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。5.1.2 回溯算法的求解步骤回溯算法求解过程一般包括以下几个步骤：1.定义一个解空间它包含问题的解。2.利用适于搜索的方法组织解空间。3.利用深度优先法搜索解空间。4.利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。5.1.3 回溯算法在排课系统上的特点回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。它适用于解一些组合数较大的问题。高校排课的组合就是很巨大的，使用回溯算法能更好的保证排课的正确性与实用性。5.2 排课系统算法分析排课问题是涉及到教师、教室、班级、课程和时间五个因素的排列组合问题。排课时，最基本的要求（硬性约束）就是避免教师、班级在时间和空间上产生冲突。解决的办法就是依次为开设的每门课程搜索到该课程教师、班级和教室共同空闲的时间片。排课算法的实质就是为课程安排上课时间和上课地点。但是，如果同时考虑这两者，必然会引起“组合爆炸”现象。所以为了避免这种情况，我采用回溯算法进行排课，首先算出符合时间要求的老师，然后选出符合时间要求的教室。5.3 排课过程5.3.1 自动排课算法流程自动排课系统，采用回溯算法，一层一层的进行查找合适的时间以及教室。1、确定上课时间首先确定上课的时间上课的教师时间是否已被占用，没有占用，则进行下一步；如果被占用，则查找下一个时间片教师时间是否被占用。2、确定上课教师确定完上课时间后，还要确定上课地点。安排上课地点的原则是时间片不能与其他课程冲突。所以如果时间片不能满足要求，要重新进行时间安排。NNN开始选择一个上课时间判断所选课程教师时间是否被占选择一门课程判断所选教室时间是否被占选择一个教室确定上课时间内容结束YY课程是否超出范围Y教室是否超出范围Y综上所述，流程图如5.1所示：图5.1 自动排课系统流程图5.3.2 自动排课程序在进行排课之前，先要根据管理员所选择的院系专业，在数据库找出需要进行排序的课程。首先要先连接数据库，然后根据专业选择正确的课程信息。这部分的代码如下： string mystr =ConfigurationManager.AppSettingsmyconnstring; OleDbConnection myconn = new OleDbConnection(); OleDbCommand mycmd = new OleDbCommand(); myconn.ConnectionString = mystr; myconn.Open(); string mysql1 = SELECT ID FROM 院系信息 WHERE 学院名称= + DropDownList1.SelectedItem.Text +AND 专业名称=+DropDownList2.SelectedItem.Text+; mycmd.CommandText = mysql1; mycmd.Connection = myconn; string id = mycmd.ExecuteScalar().ToString(); string mysql2 = SELECT ID FROM 课程信息 WHERE 院系ID= + id + ; mycmd.CommandText = mysql2; mycmd.Connection = myconn; int kid = int.Parse( mycmd.ExecuteScalar().ToString();/确定课程代码在选取要进行排序的课程之后，我们就要运用回溯算法对课程进行排序，已达到自动排课的目的，回溯算法的流程如上一小节的图5.1系统流程图所示，其代码部分如下：for (ti = 1; ti 21; ti+) for (kid = 1; kid 10; kid+) if (Jiaoshishijian(kid, ti)/教师时间冲突判断 for (rid = 1; rid 10; rid+) if (Roomshijian(ti, rid)/教室时间冲突判断 string kc = Jilukecheng(kid, rid, ti);/ 确定课程时间教室 int iCells = (ti - 1) / 4 + 1; int iRows = ti - (iCells - 1) * 4; Table1.RowsiRows.CellsiCells.Text = kc; break; else continue; break; else continue; 回溯算法中要对教师时间和教室时间是否被占用进行判断。教师和教室的时间片标记事先是写好在数据库里的，根据不同的代码和时间片代码从数据库中读取标记位，然后进行判断就可以了。教师时间冲突判断代码如下：string mystr = ConfigurationManager.AppSettingsmyconnstring;OleDbConnection myconn = new OleDbConnection();OleDbCommand mycmd1 = new OleDbCommand();OleDbCommand mycmd2 = new OleDbCommand();myconn.ConnectionString = mystr;myconn.Open();string mysql1 = SELECT 教师ID FROM 课程信息 WHERE ID=+kid+;mycmd1.CommandText = mysql1;mycmd1.Connection = myconn;string id = mycmd1.ExecuteScalar().ToString();string mysql2 = SELECT t+ ti + FROM 教师时间 WHERE 教师ID= + id + ;mycmd2.CommandText = mysql2;mycmd2.Connection = myconn;string flag = mycmd2.ExecuteScalar().ToString();if(flag=0)return true;elsereturn false;由于教室时间冲突与教师时间冲突代码类似，在这里就不再写明了。在时间冲突解决之后就是对课程进行记录了，在算法中有一个自定义类Jilukecheng()，其返回值就是已经排列完成的课程的名称和上课的教师以及上课的教师的字符串，而这个字符串的构成方式如下：string mystr = ConfigurationManager.AppSettingsmyconnstring;OleDbConnection myconn = new OleDbConnection();OleDbCommand mycmd1 = new OleDbCommand();OleDbCommand mycmd2 = new OleDbCommand();OleDbCommand mycmd3 = new OleDbCommand();myconn.ConnectionString = mystr;myconn.Open();string mysql1 = SELECT 课程名称 FROM 课程信息 WHERE ID= + kid + ; mycmd1.CommandText = mysql1;mycmd1.Connection = myconn;string kcm = mycmd1.ExecuteScalar().ToString();string mysql2 = SELECT 教师姓名 FROM 课程信息 WHERE ID= + kid + ; mycmd2.CommandText = mysql2;mycmd2.Connection = myconn;string jsm = mycmd2.ExecuteScalar().ToString();string mysql3 = SELECT 名称 FROM 教室信息 WHERE ID= + rid + ; mycmd3.CommandText = mysql3;mycmd3.Connection = myconn;string room = mycmd3.ExecuteScalar().ToString();string kc = kcm + jsm + room;/课程信息及教师安排 r