大学排课需要注意什么？
早在20世纪70年代，排课问题就被证明是一个NP完全问题，即算法的计算时间呈指数增长，这就确立了问题的理论深度。目前，还没有一个通用的算法可以完全解决NP问题。但是，许多NP完全问题具有很大的实际意义，比如。众所周知的路由算法是一个典型的NP完全问题。路由需要从众多节点中寻找最短路径来完成信息的传递。由于它们都是NP完全问题，因此可以应用许多路由算法来解决排课问题，如Dijkstra算法、节点子树剪枝构造网络的最短路径法等。
目前，研究NP完全问题的主要思路是如何降低其计算复杂度。即改用一种近似算法，将求解问题的时间由指数增长简化为多项式增长。结合课表问题就是建立一个合适的现实的简化模型，可以大大降低算法的复杂度，便于程序实现。这是很多解决课表问题的思路。
在高校，培养学生的主要途径是教学。在教学活动中，有一系列的管理工作，其中教学计划的实施是一个重要的教学环节。每学期管理者要整理教学计划，根据教学计划下达教学任务书，然后根据教学任务书安排课程。在这些教学排班工作中，不仅有大量繁琐的数据整理工作，还有思维严谨的脑力劳动和大量的表格要填写。所以工作很繁重。
另外，随着教学改革的推进和“211”工程的实施，新的教育体制对课程的安排提出了更高的要求。人工排课时，发送信息极其麻烦，而计算机排课时，教学中的信息可以一目了然，这对于优化学生的学习过程，评价每位教师对教学的贡献，引导合理决策具有重要意义，必将极大地促进教学的良性循环。
2该学科的应用领域
本课题的研究对开发高校排课系统具有指导作用。
排课的核心是多维度资源的冲突与抢占，对它的研究也是对类似问题(尤其是与时间表相关的问题，如考场安排、影院座位安排、航线等)的借鉴。
3项目的现状
90年代末，国外有人开始研究课程安排问题。1962中，Gotlieb提出了时间表问题的数学模型，用匈牙利算法解决了三维线性运输问题。之后，人们对课表问题的算法和解的存在性做了大量深入的讨论。然而，大多数文献中使用的数学模型是对Gotlieb数学模型的简化或补充，至今没有可行的算法来解决课表问题。
近40年来，人们做了许多尝试用计算机解决课表问题。其中，排课的整数规划模型将问题归结为一组0-1变量的求解，但其计算量非常大。求解0-1线性优化问题的分支定界技术只适用于小规模的排课问题。Mihoc和Balas(1965)将课程公式化为优化问题，而Krawczk提出了线性规划方法。Junginger将课表问题简化为一个三维运输问题，而Tripathy将课表问题视为一个整数线性规划问题，提出了大学课表的数学模型。
另外，一些文献试图从图论的角度解决课表问题，但是图的着色问题也是NP完全的。只有在极其简单的情况下，时间表才能转化为二部图匹配问题。这种数学模型与现实相差甚远，对于大多数学校的课表编排问题没有实用价值。
进入20世纪90年代后，国外对课程表的研究仍然十分活跃。代表人物有印度瓦斯塔普尔大学管理学院的ArabindaTripathy，加拿大蒙特利尔大学的Jean Aubin和Jacques Ferland等。目前解决课表法问题的方法有很多，如模拟人工课表法、图论法、拉格朗日法、二次分配法等。由于课程的复杂约束，用数学方法描述时问题的规模往往急剧增大，这成为应用数学规划解决课程问题的巨大障碍。国外的研究表明，单纯用数学方法解决大规模排课问题是不可行的，但运用运筹学中的分层规划思想对问题进行分解将是一种很有前途的方法。
我国对课程表的研究始于20世纪80年代初，比较有代表性的有南京理工大学的UTSS(一种大学时间表编排系统)、清华大学的TISER(课程表编排系统)、大连理工大学的智能教学组织管理与课程表编排等。这些系统大多模拟人工排课流程，使用启发式函数来排课。但这些系统化的排课系统往往依赖于各个学校的教学体系，不适合大范围推广。
从实际使用情况来看，国内外开发的这些软件系统的实用性还不尽如人意。一方面原因是作为一个非常复杂的系统，安排各方面的课程非常困难；另一方面，由于各个学校的特殊性，自动排课软件很难得到广泛应用，尤其是在排课过程中，一个小的变动就会引起所有课程的大调整，意味着整个学校课程的大变动，在实际应用中很难实现。
4求解NP问题的几种算法及其比较
解决NP完全问题只能依靠近似算法，所以下面介绍几种常用算法的设计思路，包括动态规划、贪婪算法、回溯法等等。
动态规划法是将已求解的问题逐步分解成规模递减的子问题，直到其解的子问题可以直接求解。分解后的所有子问题按照层次关系形成一棵子问题树。根源是原来的问题。原问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于寻找某个问题在某种意义上的最优解。设计一个动态规划算法，通常按以下步骤进行:
1.分析最优解的性质，刻画其结构特征。
2.递归定义最优解。
3.以自下而上的方式计算最优解。
4.根据计算最优解时获得的信息，构造一个最优解。
步骤1~3是动态规划算法的基本步骤。在只需要找到最优解的情况下，可以省略步骤4。如果您需要找到问题的最佳解决方案，您必须执行步骤4。此时，在步骤3计算最优解时，通常需要记录更多的信息，以便在步骤4中，根据记录的信息快速构造出最优解。
贪婪算法
当一个问题具有最优子结构性质时，我们会想到用动态规划来求解，但有时也有更简单有效的算法，那就是贪心算法。顾名思义，贪婪算法总是做出目前最好的选择。也就是说，全局优化中没有考虑贪婪算法，他所做的选择只是某种意义上的局部最优选择。贪婪算法虽然不能得到所有问题的全局最优解，但可以产生很多范围很广的问题的全局最优解，比如图中所示算法中的单源最短路径问题和最小生成树问题。在某些情况下，即使贪婪算法不能得到全局最优解，最终结果也是最优解的一个很好的近似解。
在贪婪算法中，Dijkstra算法是最著名的一种。它被用作查找两个节点之间最短路径的路由算法。Dijkstra算法的思想是:如果G有n个顶点，我们总是需要找到n-1条最短路径。求解方法如下:首先尝试，写出从V0(起始顶点)到每个顶点(最终顶点)的路径长度，或者如果有路径，则使路径长度成为边的权重；或者没有路径，那么就是∞。然后按照长度递增的顺序生成每条最短路径。最短路径的生成过程实际上就是在起始顶点V和终止顶点W之间不断增加中间点的过程，因为每一条最短路径生成后，都有一个路径的最终顶点U，所以那些尚未生成最短路径的路径会因为经过U而比原路径短，所以让它经过U。
(3)回溯法
回溯法被誉为“万能解题法”。它可以用来找到问题的全部或任何解决方案。一般来说，回溯是一种系统性、跳跃性的搜索方法。它根据深度优先的策略在包含问题的所有解的状态空间树上从根开始搜索。每次搜索到状态空间树的一个节点时，总是判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含，则跳过系统对该子树的搜索，逐层继续搜索到其祖先节点，直到遇到有未搜索到的子节点，然后转向该节点的未搜索到的子节点继续搜索；否则，进入子树，按照深度优先策略继续搜索。