《基于课元-原始表-衍生表算法的高校排课系统》-毕业学术论文（设计）.doc

PAGE lw 摘 要 根据当前国内的现实状况抽象出“时空表”和“课元”这两个贯穿算法上下的概念，并认为，排课的实质就是把“课元”填入“时空表”内的过程。利用着色算法处理得出满足课元之间最基本关系要求的原始表，总结原始表的性质，以后的用户要求均基于此原始表、算法操作均基于此些性质。当要求约束的时候，利用约束列、互斥列和候选列来表示约束关系，参考到图论的相关知识，映射其为图的边，利用处理图来获得对原始表的操作，最后得到满足约束的衍生表。进一步处理衍生表得到最终课表。 关键词：排课算法；时空表；课元；图；原始表；衍生表；约束列；互斥列；候选列 ABSTRACT The basic concepts so called “course unit” and “space-time table” which run through this whole paper in your hand are actually abstracted from the college status quo of our country.What arranging college curriculum schedule system process is to put the “course unit” into “space-time table” precisely.To achieve this goal, first of all,the algorithm calculate a table named “primal table” using pigmentation algorithm, and then we consider that all our future manipulations are based on this table, all future operations are based on those features summarized from this table.While the restricted rules are demanded by the user, we define several efficient concept such as “restricted column”、 “excluded column” and “candidated column” to represent the relationship and correspond them as a set of edge refering to the knowledge of Graphs theory.At last, we succeed in working out the “ramificated talbe” by utilizing those interesting relationships, and manage to build the college curriculum schedule on a further calculation. Key Words：The arranging college curriculum schedule algorithm , space-time table , course unit , Graph , primal talbe , ramificated talbe , restricted column , excluded column , candidated column 目录 第1章 概述 1 1.1 课题背景 1 1.2 相关研究 1 1.3 研究内容 1 第2章 排课条件和算法框架 3 2.1对于当前国内学校的现实假设 3 2.2 对于排课问题的抽象 3 2.2.1 基本原则 3 2.2.2 概念抽象 3 2.3 算法基本框架 4 第3章 生成原始表 5 3.1 问题分析 5 3.2 生成原始表算法描述 5 3.3 算法结果及分析 7 3.4 原始表小结 7 第4章 生成衍生表 9 4.1 在原始表中针对Not条件的算法原理 9 4.2 排课系统深入讨论约束条件 11 4.2.1 从具体例子开始 11 4.2.2 关于约束部分原理的说明 13 4.3 约束算法的基本原理 14 4.3.1 讨论EP约束的解决算法 14 4.3.2 讨论ET和TP约束的解决算法 18 4.4 算法补充说明 19 第5章 小结及展望 20 参考文献 21 致 谢 22 第1章 概述 1.1 课题背景 高校，甚至于其它