一、自动排课需求分析 　　自动排课问题实质上是时间、教师、班级、教室、课程这五维关系的冲突问题。采用计算机编排课表，一个基础的要求就是避免班级、教师以及教室之间的冲突，也就是同时开课的两个班不能使用相同的教室、不能由相同的教师任教（在需求分析中，已对排课的要求作了详细描述）。所以首先解决时间冲突问题是排课算法的重点，再者死锁也是排课过程中经常出现的问题。所谓死锁，就是指在有效输入的前提下，课程无法找到满足条件的可排课时间和教室，所以在排课算法的设计当中，解除死锁也是排课算法要解决的关键。 　　在时间、教师、班级、教室、课程这五维关系中, 时间、教师、班级三者之间存在着紧密关系。相对而言, 教室与它们关系就不那么密切。 　　由于是设计排课模型，各个学校的具体排课要求不同，一些不主要的约束条件已忽略。为简化问题约束条件归纳如下： 　　1)在同一时间内一个班级仅能由某一教师上一门课； 　　2)在同一时间内一个老师只可以给一个班级讲一门课程（不考虑合班上课）；     3)在同一时间内一间教室不能安排两门课程； 　　4)一个班级的某一门课程只能由一位教师教授； 　　5)同一时间安排的课程总数不能大于所能提供的教室总数； 　　6)某一课程参加学习的总人数不应大于所安排教室的座位数； 　　7)所提供教室的属性与课程所需教室的属性一致； 　　8)同一个班级的同一课程应选择同一间固定的教室。 　　二、回溯算法 　　回溯算法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题. 　　三、自动排课算法分析 　　1.排课算法解决时间冲突的方法 　　在解决时间冲突问题上，通过建立时间表的方法来实现的。在数据库设计时，建立三个表，分别是：教师时间表、教室时间表、班级时间表。它们都是为教师、教室、班级这三者在时间上不发生冲突服务的。教师时间表主要存储每个教师每个时间段的占用情况；教室时间表主要存储每个教室每个时间段的占用情况；班级时间表主要存储每个班级每个时间段的占用情况。由于一门课程都是两节课连续上的，那就可以把两节课看作一个时间段。一天可以上8节课，一个星期有5天上课，那么一个星期就有20 个时间段。 　　算法中用1和0来区别某一时间段是否被占用，1表示该时间段没有被占用，即为空闲状态；0表示该时间段已被占用。在排课过程当中，就可以事先通过访问数据库中的时间表，来判断某一教师、某一教室、某一班级在某一时间段是否空闲，如果空闲则表示这一时间段可以被占用，否则这一时间段不能再利用，如果再利用这一时间段，就发生了时间的冲突，这是排课当中不允许的！ 　　2.解决死锁的方法 　　在排课过程当中，如果某班级的某课程永远也找不到合适的老师或班级，即在班级空闲的时间段里，教师或教室所对应的时间段没有空闲的，那么这门课程就不可排，接下来的所有课程都排不了了，这就出现了死锁现象。 　　因为排课过程是：一门课程编排好后，接着是下一门课程的编排，是一门接着一门编排下去，直到所有的课程编排结束为止。可见一门课程编排好后，将影响接下来所有没有编排的课程。所以死锁产生的原因是：当编排某一门课程时，受到了前面其他几门相关课程的约束制约。 　　于是当遇到某一门课程不能编排时，即发生死锁，可以通过返回到上一门课程，重新编排上一门来解决死锁。如果还不能解决死锁，则再返回再上一门课程，重新编排，直到解决死锁为止。 　　如果各种情况都不能解决死锁，这是资源不够用，通过增加教师，教室资源才能解决死锁问题。      3.运用递归算法和回溯算法相结合 　　递归算法主要用于把大规模问题分解化成小规模问题解决，而各个小规模问题的解法都相同。当每个小规模问题都解决了，那么整个问题都解决了。 　　可把整个排课问题分解成每个班的排课