摘要：高校的毕业答辩安排表编排是一项十分繁重而复杂的工作，它涉及多个专业、几十名教师、几百名学生。而所使用的教师资源却在学生规模每年都在增加的趋势下越来越显得紧张。事实上,编排毕业答辩安排表的整个过程充满了矛盾运动,其中老师数量平衡、学生性别平衡、学生数量平衡、学生导师平衡、学生老师避嫌这5个方面在排列组合中所发生的冲突和矛盾现象尤为突出。毕业答辩安排表的编排必须精心组织,准确无误，实现科学化、合理化,必须充分发挥时间、空间、人力、物力的效益,以保证教学过程的正常运转。本文将随机算法下的答辩表和贪心算法的答辩表，并比较了两种算法的优缺点。
关键词：排课系统，贪心算法，优先队列
1 算法介绍
1.1技术路线
在实际使用中，有以下限制
每组组长已确定，需要从其余老师中挑选。不能有剩余老师。
各组答辩组分配学生，回避导师（指导老师不能和自己的学生为一组）
每组学生人数大致均衡，不能有剩余学生
各组学生男女比例均衡（比如各组男女比例都为5:2左右）
每组导师数均衡（不能让某位老师指导的学生全被分到某一组）
本文采用随机算法抽取九百万条老师及学生答辩位置安排，通过将已经抽取的最优安排与当前安排的指标进行比较，获取九百万条随机数据中的相对最优安排。在贪心法中，以优先队列(priority queue,STL)的形式先选择优先级最高且不冲突的老师，老师确定后选择优先级最高且不冲突的学生。
在存储结构中，通过引用老师ID，学生ID，减少数据传输的冗余。同时使用不定长
数组vector组件，可以方便的添加及删除数组内容。
1.2随机法
如图2所示，文章采用随机法作为对照实验，其老师流程如下：先存储输入的老师及对他们进行编号，确定组数与组内老师的数量，在老师存在范围内生成随机序号，确定该位置放置老师是否合法，最后重复生成老师位置，直到老师分配完毕。
确定完老师的位置后，进一步确定学生的位置，并判断是否合法：在学生存在范围内随机生成学生序号，确定该位置放置该学是是否合法，循环填充学生位置，保证学生填充完毕。
在随机算法中，文章设置了多项指标。
组间人数比。其中指的是每组平均多少人，xi 为第i组有多少人。
.png)
通过计算每次随机法计算出来的结果相应的这些指标，与之前存在的最优解相比较，如果
这次比之前的要优秀，就更新最优解。这就是随机法的思想。
1.3贪心法
在当前状态下，选择最有利于期望状态进一步发生的步骤，就是贪心法。这是一种从局部最优解到达全局最优解的方法，该实验流程与随机法在框架上是一致的。先选择老师ID及位置安排，再选择学生ID及位置安排。不同的是随机法采取随机数作为填充依据，贪心法选择优先队列中的首项作为填充依据。
该优先队列重载如图2所示。其对老师选择与插入组别采用不同方式的优先策略。老师的优先依据为所带学生数量，组别选择一级依据为组内人员数量，二级依据为组内成员男女比例。通过这中优先策略，可以满足题目除男生生限制外的其他要求。
通过上述优先策略，选择老师及插入位置进行插入。图3为老师ID及位置随机生成算法的流程图。由于在优先队列中没有考虑组内男女生比例问题。所以在填充选择学生ID时，需要判断该组缺啥性别的学生以及当前优先队列队首的学生是男是女。为此，文章在此处设置了一个栈(stack,STL)来存储已经出队的，但是不符合组内性别要求的学生。当出队学生满足要求时，再将其填充入该组的学生数组中，栈内未使用的学生将再次加入优先队列。
图 2: 优先队列小于号重载
.png)
2 结果对比
在CPU：I7-9750H，RAM：24G，OS：Windows 10平台上，对两个算法运行。随机
法运行时间为5个小时，贪心法运行时间为5秒。
分别展示了随机法筛选九百万条数据后最优解以及贪心法最后的最优解。可以得到贪心法对比随机法，在所有指标上都有巨大的进步，而且运行时间更短。所以基于贪心法的答辩安排方法是可靠有效快速的。
3贪心策略分析
答辩安排的核心算法，假设老师人数为n人，学生人数为m人。在时间复杂度上,确定老师位置的时间复杂度为O(n 2 ),确定学生位置的时间复杂度为为O(mn)。因为一般情况下学生人数远大于老师人数,所以总复杂度为为O(mn)。若后续采用二分查找学生与老师的选择与位置，可以将时间复杂度降到为O(log (mn))。
4讨论与结论
通过程序运行结果，可以看到贪心法相较于随机法有巨大优势，所以本文采用的贪心法可以较为完美地解决答辩安排中地限制问题，避免回溯法占用大量内存地情况，由于其易于熟悉地特点相对于启发式算法具有更好的适应性。
在答辩安排表质量上,由于采用优先级制,在保证了硬性条件不冲突情况下,符合排答辩安排表的基本准则，保证了老师及学生的合理的安排,为后续的排其他专业的答辩安排表以及特殊需求预留了丰富的空间，这是教学资源的利用趋于合理利用的最优化。在答辩安排表中，也可以因为某位老师对某个方向的学生愿意提供具体的见解，而把他们安排在一起,符合我们的获取知识的需求。
参考文献
[1] C. C. Gotlieb. The construction of class-teacher time-tables. Communications of theAcm, 5(6):73–77, 1962.
[2] Arabinda Tripathy. Computerised decision aid for timetabling —a case analysis. DiscreteApplied Mathematics, 35(3):313–323, 1992.
[3] 张海涛 and 刘万军. Algorithm research on university computer table scheduling辽宁工程技术大学学报, 024(1):110–111, 2005.