基于回溯算法的智能排课系统研究与实现

摘 要 随着计算机的发展和教育改革的不断深入，计算机网络技术的不断成熟，综合教学网络已广泛应用于学校教学、管理的各个领域，特别是微机排课系统的应用。它代表着学校教学管理的水平，是现代化管理的手段。多年来人们为实现课表编排的智能排课进行了大量的探索。从50年代末开始，就有人着手研究用计算机来解决课表问题。此后，人们对课表问题的数学模型、课表问题的解及解的存在性等问题进行了深入的探讨，但一直未能得到满意的结果。直到1975年课表问题被证明是NP-完全类以后，人们才将注意力更多地转向课表编排实用算法的探索与研究。 目前大多数微机排课系统是采用各教学单位进行教学任务的指派，然后将教学任务单提交教务科，教务人员将数据输入微机，进行排课、打印课程表等工作。这种微机排课系统只是在一定程度上减轻了教务人员排课的负担。如何更有效地利用人力、物力资源，充分发挥微机的辅助作用，减轻教务人员的工作强度，在对需求进行详细的分析后，本文提出了基于教学大纲的微机排课设计思想，并对其算法进行了描述，共同行参考。 论文首先介绍了智能排课系统的研究背景和意义、国内外发展状况及其相关技术。接着仔细探讨了智能排课系统的工作流体系结构、工作流子系统的设计与实现；结合我校教务管理事务的实际状况，分析事务工作流程，研究并给出了其工作流模型。 然后，介绍了基于回溯法的智能排课系统研究的内涵及特征，研究了回溯法在系统中的作用；结合教务排课管理事务的实际处理情况，通过对各种类型的课程及排课条件的适当处理，提出了一种大学课程表的排法方案，尽量降低排课的复杂度;并突出了教室资源的限制，给出了一个基本通用的模型;提出用优化的回溯算法求解模型并辅助以松弛法。 最后实现基于回溯法的智能排课系统的开发。介绍了开发背景和设计原则，然后从总体框架出发，分析了系统的具体目标，在此基础上给出了实施方案。针对教学管理子系统，分析了其基本的数据结构和处理流程，给出了实现程序。最后运行系统并分析显示了运行结果。 关键词：智能排课系统，回溯法，管理模型，工作流模型，排课方案 目 录第1章 绪论??? 11.1 引言??? 11.1.1 智能排课系统的排课问题??? 11.1.2 智能排课系统研究与开发新动态??? 21.2 智能排课系统的国内外发展状况??? 31.2.1 国外发展状况??? 31.2.2 国内发展状况??? 31.3 基于回溯法的智能系统研究发展现状??? 51.4 课题的提出及其意义??? 61.4.1排课流程与工作基础??? 61.5 课题的相关内容研究??? 71.5.1事务的处理流程和细节??? 71.5.2 各类型事务工作流分析和建立??? 71.5.3系统性能和结构研究与设计??? 8第2章 自然排课问题的分析与研究??? 92.1排课问题的描述??? 92.1.1 课程结构类型的定义??? 92.1.2时间片的定义??? 92.1.3结论??? 92.2排课问题的约束条件及分类??? 92.2.1 排课的基本条件??? 102.2.2排课的直接相关约束条件??? 102.2.3排课的系统相关约束条件??? 102.3排课问题的“自然排课”模型??? 102.3.1“自然排课”模型的理论研究??? 102.3.2 “自然排课”模型的理论应用??? 112.4 本章小结??? 13第3章 回溯法的研究与应用??? 143.1 引言??? 143.2 回溯算法概述??? 143.2.1 回溯法的思想??? 143.2.2回溯法的递归流程??? 143.2.3回溯法的解题步骤??? 153.2.4定和子集问题??? 153.2.5定和子集问题的回溯算法伪代码??? 163.3 智能排课系统的算法设计??? 173.4 排课基本模型的具体算法??? 183.4.1建立状态空间树??? 183.4.2构造约束函数??? 183.5 本章小结??? 19第4章 智能排课系统实现??? 204.1 开发背景与设计原则??? 204.2课程编排原则??? 204.2.1自然班和教学班??? 204.2.2教学任务、时间片和时空片??? 204.2.3排课原则??? 214.2.4排课要求的详细流程??? 214.3 智能排课系统的总体框架及实施方案??? 214.3.1 总体框架??? 214.3.2 具体目标??? 234.3.3 实施方案??? 234.4 基于回溯算法的智能排课系统实施??? 244.4.1智能排课系统的窗体结构图，如图4-3所示??? 244.4.2 系统应用??? 244.5 本章小结??? 34第5章 结论与展望??? 355.1 总结??? 355.2 展望??? 35参考文献??? 36致 谢??? 37