毕业设计（论文）-自动课程编排系统设计.doc

白城师范学院本科毕业论文 摘要制定一个学校的排课系统是一项非常耗时且相当辛苦的工作,而且它还得由有学校排课工作经验或者这方面知识的人才能做好在一所高校一个课程表的制定是一个难题,因为在有关课程表的问题上存在很多的限制条件需要考虑,还有大量的数据空间需要被挖掘,即便你的输入数据量并不是实际意义上的大批量课程编排系统是一个学校不可缺少的部分,它的内容对于学校的决策者和管理者来说都至关重要,所以自动课程编排系统应该能够为用户提供充足的信息和快捷的查询手段但一直以来人们使用传统人工的方式管理文件档案,这种管理方式存在着许多缺点,如:效率低保密性差,另外时间一长,将产生大量的文件和数据,这对于查找更新和维护都带来了不少的困难 随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。这种算法在排课系统中有着举足轻重的作用。关键词 排课系统；贪心算法；局部最优解 AbstractFormulates a school platoon class plan is an item consumes extremely when also the quite laborious work, moreover it also must by have the school row of class work experience or this aspect knowledge talented person can complete. When a university a class schedule formulation is a difficult problem, because has the very many limiting condition in the related class schedule question to result in the consideration, but also has the massive data space to excavate, even if your input data quantity is not in the practical significance mass.The curriculum arranges the system is a school essential part, Its content said regarding the school policy-maker and the superintendent all very important, Therefore the automatic curriculum arranges the system to be supposed to be able to provide the sufficient information and the quick inquiry method for the user. But the people have since always used the traditional artificial way management document file, this management way has many shortcomings, For example: The efficiency low, the secrecy is bad, Moreover the time one is long, Will produce the massive documents and the data, This regarding the search, the renewal and the maintenance has all brought many difficulties.Along with science and technology unceasing enhancement, The computer science is mature day after day, Its formidable function had profoundly known for the people, t entered the human society each domain and is playing the more and more vital role.Greedy algorithm is a measure of significance can be under some kind of optimal solution of the classification approach, it is always made in the current choice appears to be optimal, that is greedy strategy is not to be considered a whole, it only made sense to choose the local optimal solution algorithm.Keywords Course Scheduling System; Greedy algorithm；Local optimal solution目录摘要1Abstract2第一章 绪论41.1 研究背景41.2 研究意义41.3 本文研究的主要内容4第二章 算法的研究62.1 贪心算法的概念原理62.11 贪心算法的基本过程62.12 贪心算法的性质特点72.13 贪心算法与动态规划的差异82.2 贪心算法的应用与举例82.3 贪心算法的优缺点11第三章 排课系统的研究133.1高校排课系统算法的改进133.2 排课算法的特点133.3 排课算法的流程图14第四章 基于贪心法的排课系统154.1 数据结构154.2数学模型164.3排课算法174.31算法思想174.32辅助空间174.4复杂度分析19结束语20参考文献21致谢22第一章 绪论贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，它总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解算法。贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法为止。1.1 研究背景 课程表问题，是典型的组合优化和不确定性调度问题，是解决对时间和空间资源争夺而引起的冲突。20世纪50年代末，国外有人开始研究课表编排问题;1962年，Gotlieb曾提出一个课表问题的数学模型，并用匈牙利算法解决了三维线性运输问题;20世纪70年代中期，美国人S.Even等论证了课表问题是NP完全问题。进人20世纪90年代后，国外对课表问题的研究仍然十分活跃，比较有代表性的有印度Vastapur大学管理学院的Arabinda Tripathy，加拿大Montreal大学的Jean Aubin和Jacques Ferland等。笔者曾与重庆一个较大规模的健身城(以CJ表示)联合，由CJ提出健身城排课问题的规则与约束，笔者负责设计、开发一个通用的健身城排课软件，最后由CJ测试、运行。健身城排课不是一类特殊问题，很多培训机构等都存在与健身城排课相似的规则与约束:兼职教师、分散的分点、约束12-15(见2.2)等。本文结合前辈完成的项目，深人分析、探讨了解决这类问题的思想、策略及算法。但文中提出的解决思想、策略及设计的算法可供培训机构等排课进行参考。I.2 研究意义随着近几年教育部对教育资源的整合、结构调整，不少学校的招生规模和班级数都在大幅度的提高，排课是高校教学管理中最基本、最重要、同时也是最复杂的管理工作之一，其实质就是为学校所设置的课程安排一组适当的教学时间与空间，因此必然会引发一种合理而简捷的算法贪心算法。建立合理的排课系统，贪心算法是当前看来较好的选择。贪心法不是从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解，这样将进一步实现办公的信息化，提高工作的效率，从而使整个教学能够有计划有秩序地进行。I.3 本文研究的主要内容排课是脑力劳动强度较高的工作，尽管不同的学校管理模式存在差异，对排课结果的形式也有所不同，但其共同的目标都是对教学任务进行合理的时空分配。国内外大多数排课算法基本上都是基于回溯的二部图匹配算法。到目前为止，组合最优算法研究几乎都得到最优解的排课算法的时间复杂度是排课规模的指数阶。尽管如此，为了从分利用教学资源，也只能追求排课最优解。本文把贪心算法应用于排课算法中，得到易于是实现最优解的多项式排课算法。第二章 贪心算法的研究2.1 贪心算法的概念原理所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。当一个问题具有最优子结构性质时，我们会想到用动态规划法去解它。但有时会有更简单有效的算法。我们来看一个找硬币的例子。假设有四种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出2个二角五分的硬币，1个一角的硬币和3个一分的硬币交给顾客。这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法：首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪心算法。顾名思义，贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪心算法得到的最终结果也是整体最优的。上面所说的找硬币算法得到的结果就是一个整体最优解。找硬币问题本身具有最优子结构性质，它可以用动态规划算法来解。但我们看到，用贪心算法更简单，更直接且解题效率更高。这利用了问题本身的一些特性。例如，上述找硬币的算法利用了硬币面值的特殊性。如果硬币的面值改为一分、五分和一角一分3种，而要找给顾客的是一角五分钱。还用贪心算法，我们将找给顾客1个一角一分的硬币和4个一分的硬币。然而3个五分的硬币显然是最好的找法。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。如图的单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。2.11 贪心算法的基本过程贪心算法的基本思路及过程如下：1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。2.12 贪心算法的性质特点贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所作的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下确能达到预期的目的。解活动安排问题的贪心算法就是一个例子。下面我们着重讨论可以用贪心算法求解的问题的一般特征。对于一个具体的问题，我们怎么知道是否可用贪心算法来解此问题，以及22否得到问题的一个最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中我们看到它们一般具有两个重要的性质特点：贪心选择性质和最优子结构性质。1贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。通常可以用我们在证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。2最优子结构性质当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。在活动安排问题中，其最优子结构性质表现为：若a是对于正的活动安排问题包含活动1的一个最优解,则相容活动集合a=a1是对于e=ie:sif1的活动安排问题的一个最优解。2.13 贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。但是，对于一个具有最优子结构的问题应该选用贪心算法还是动态规划算法来求解?是不是能用动态规划算法求解的问题也能用贪心算法来求解?在遇到具体问题时，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。贪心策略动态规划相同点1 时间效率较高、适用于对问题的求解有严格时间限制的题目。2 均能保证局部最优解。不同点所占空间较小所占空间较大某次具体选择必是最优选择某次具体选择不一定是最优选择解题大体框架：线形ABCD为最优选择，每一中间节点B、C也为最优选择解题大体框架：图或树ABCD为最优解，但不一定是最优选择2.2 贪心算法的应用与举例1、贪心算法在0-1背包问题中的应用 问题的提出背包问题分为部分背包问题和0/1背包问题两种。部分背包问题在选择物品时，可以将物品分割为部分装入背包，即0 xi1。很显然属于贪心算法的范畴，用贪心算法能较好的解决求解问题。给定n种物品和一个背包。物品i的重量是w ，其价值为v ，背包的容量为c.问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。此问题的形式化描述是，给定c0，wi0，vi0，1in，要求找出一个n元01向量(xl，x2，xn)， ，使得 c，而且 达到最大。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。此问题的形式化描述是，给定c0，wi0，vi0，1in，要求找出一个n元向量(x1,x2,.xn)，0xi1，1in 使得 c，而且 达到最大。这两类问题都具有最优子结构性质。对于01背包问题，设a是能够装入容量为c的背包的具有最大价值的物品集合，则aj=a-j是n-1个物品1，2，j1，j+1，n可装入容量为c-wi叫的背包的具有最大价值的物品集合。对于背包问题，类似地，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量wi，剩余的将是n-1个原重物品1，2，j-1，j+1，n以及重为wj-wi的物品j中可装入容量为c-w的背包且具有最大价值的物品。虽然这两个问题极为相似，但背包问题可以用贪心算法求解，而01背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值vjwi然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去直到背包装满为止。具体算法可描述如下：void knapsack(int n, float m, float v , float w , float x )sort(n,v,w);int i;for(i= 1;i= n;i+) xi = o;float c = m;for (i = 1;i c) break; xi = 1; c-= wi; if (i 0)本步骤计算所需张数ni=当前所需金额/余下的最大面值vi当前所需金额 =当前所需金额-ni*viC语言算法如下：#include#includeint num9;/定义全局数组变量num，通过它带回最后结果得到主函数int *zhaoqian(int m,int n)int I;for(i=0;i9;i+)numi=n/mi;n=n%mi;/主函数void main ()int m9=500,200,100,50,20,10,5,2,1;/数组m用来存放市场上所有当前面值，以“角”为单位存放int n;/变量n表示应该找零的总金额int I;printf(“please input the total count of volume:”);scanf(“%d”,&n);zhaoqian(m9,n);for(i=0;i0且可用多个场地，则如果在“只要”时间元能够分配多个场地满足上课人数（选择场地需求量最少的分配方案，则登记多个场地使用情况并分别标记场地“已使用”，减去所用课时）f. 如果剩余课时0则报错（“只要”时间元没有合适的资源）；（4）如果“只要”时间元多于所需周学时，则报错（少于周学时则在第四步中继续不足）；说明：处理周学时为单数的课程；如果周学时只剩3而且不分单双周上课，则处理三节连上（三节连上只放在下午或者晚上）；只有周学时只剩1时才处理单双周。第四步：（处理一般情况）对集合K的所有元素，做（1） 如果“已排好”则返回循环，否则统计“只要”用掉的学时数（特别处理周学时为单数的情况）（2） 如果学时数用足了，则返回循环，否则把本课程的班级、教师在前面所用过的时间元标记在本记录相应时间元为“已使用”（mat1）（3） 按场地类型生成mat3并按容量从小到大排序；剩余周学时=周学时-“只要”用掉的学时数；（4） 对剩余周学时0且场地未查完，做a. 对130的时间元，找容量满足要求（mat3）的班级（mat1）、场地（mat2）均未使用的时间元（解决冲突）；b. 如果未找到，则找下一个场地，返回循环；c. 处理三节连上的情况（同第三步）；d. 记录分配的时间、场地到K和D；e. 标记班级（mat1）、场地（mat2）使用时间元为“已使用”；f. 减去用掉的周学时；g. 下一次课的时间至少隔一天(均匀排课)；（5） 重复扫描（4）10次（由于均匀排课的要求，导致有空闲时间元而可能不被分配。实际上在有可行解的情况下，一般只需要扫描2次就使（4）的条件不在成立了）（6） 如果剩余周学时数0且要求多个场地（同时间多场地），剩余周学时0且场地未用完，反复做a. 对130的时间元，找班级（mat1）未使用的时间元，未使用的多场地（mat2）容量总和人数（从大到小分配多个场地存于（mat4）；b. 其它类似（4）（7） 重复扫描（6）10次；（8） 如果剩余周学时数0且要求可分为多组（不同时间、多场地），剩余周学时0且场地未用完，反复做a. 按容量从大到小分配多个场地存于（mat4），可能多个时间元才满足容量一次；b. 其它类似（4）；（9） 重复扫描（8）10次；（10） 如果剩余周学时0，则资源不足排课失败。4.4复杂度分析空间复杂度：算法的空间开销主要在K、D以及辅助空间上，O（n+m）;时间复杂度：算法的时间开销主要花在第四步的（4）中，即使线性查找教学场地，大致也只需要300mn=O（mn）。通常mn，所以时间复杂度几乎是线性的。算法的软件实现也表明，该算法的时间复杂度确实大大优于许多商业软件。反之，假设M是图G的一个匹配。根据匹配定义，我们有：1） G中一定存在饱和X的所有顶点的（X，Z）匹配。根据Hall定理，对于X中的任意一个子集S，必有|(S)|8|S|成立。2） 根据性质1，G中一定存在饱和X的所有顶点的（X-Y-Z）-匹配L。有L的构造方法易知LM。而对于X的任意一个子集S，显然nz（S）。综上，必有|=|nz(S)|8|S|成立。结束语通过本次毕业设计的制作和学习，我对贪心算法和排课系统有了较深的学习和理解，对算法的实现及执行过程有了较深的认识，也使理解了软件工程的基本概念和原理基础及学会结构分析和结构设计技术，掌握结构程序设计技术及设计测试方案的基本方法。经过本次毕业论文设计，使我们懂得了怎样去查阅资料，学会了规划一个软件项目。同时也提高了我们对问题的逻辑思维能力，这次的论文设计开发使我们受益匪浅。使我们对软件开发的流程有了一定的了解，并使我们具备了一定的软件开发的经验和能力。但是由于论文设计的时间和我本人的知识有限，在该设计中还有许多不尽如人意的地方，比如文档的总体设计和软件测试等多方面问题，通过今后的学习，这些都要进一步改善。同时也给我今后在软件工程的学习方面有了目标和弥补。在研究课题之前，在整体构思上没有一个整体框架，通过对软件工程及数据库的认真研读，参照瀑布模型使我对整个设计开发阶段有了一个清楚的认识，使整个设计开发过程有了一个明确的思路。又对在瀑布模型的框架下，通过软件工程在结构化设计中所给出的明确的方法。对将要开发设计的软件按照软件工