基于抽签选课算法选课系统的改进设计
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于抽签选课算法选课系统的改进设计范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：网上选课已经在各大高校的教务系统中广泛应用，选课算法的设计，直接关系到学生公平受教育的权利，也关系到选修课教学效果的优劣。该文在现今流行的抽签选课算法基础上，设计并实现了符合我院实际的排除算法，在一定程度上改进了抽签算法的弊端。
中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)16-3761-02
The Improvement Design of the Online Course Selection System Based on Drawing Algorithm
LI Yuan, XU Mei-lin
(Tianjin College of Beijing University of Science and Technology, Tianjin 301830, China)
Abstract: The online course selection system has been widely used in the academic system of the universities. The design of the course selection algorithm directly related to right of the students, also related to the teaching performance of the elective course. Based on the popular drawing algorithm, we designed a new algorithm which consistent with our situation.
Key words: course selection; course selection system; drawing algorithm; remove algorithm; algorithm design
随着网络技术的发展，目前大多数高校中已经采用了网上选课系统，随之而来也涌现出了不少选课的算法，通过不断地调整和试验，以期能有一个较优化的系统执行效率和对学生相对公平的筛选结果。在多年的实践探索中我们认为，一个实用合理的选课系统应该满足的条件有：
1) 要积极引导学生的选课需求，避免盲目选课、扎堆选课的情况出现。
2) 尽可能满足学生的选课需求，让多数学生能够中选，避免出现部分学生多次中选，部分学生无中选的情况。
3) 系统应该足够智能化，注重易用性和便利性，尤其是数据的整理、等重要操作，要求具备基本计算机操作能力的工作人即可完成。
4) 系统运行稳定，效率高，安全性好，易于维护。
1 网络选课系统常用算法分析
1.1“先来先选”算法
从选课系统的设计发展来看，最简单的选课算法是“先来先选”式的，选课系统根据学生登记选课的时间先后来确定中选学生，当选课人数达到该门课程最大限选人数时，就结束该门课程的选课。“先来先选”算法会导致选课系统开放初期会有大量学生涌入选课系统，影响系统效率，极端情况下甚至会出现网络堵塞，服务器崩溃等问题。因此“先来先选”的办法已经逐渐被各类选课系统淘汰。
1.2 优先算法
优先算法一般都采用了预选和正选两阶段结合的方式，预选阶段所有选修课不设选课人数限制，学生可以在和必修课无冲突的情况下，任意进行选修课的选择。预选阶段结束以后，选课系统暂时关闭，进行后台的筛选处理。对于选课人数小于课程容量的课程，所有选课学生都可以中选；但若选课人数大于课程容量，则需要进行筛选。
对于上述“筛选”过程，又衍生出了多种优先算法，以期能够较为公平的处理学生的选课结果。常见的优先算法有“年级优先”“专业优先”“志愿优先”等。“年级优先”和“专业优先”算法顾名思义，前者一般将高年级学生作为优先考虑的对象，首先满足他们的选课需求，再考虑低年级学生的需求。而“专业优先”则优先考虑本专业学生中选本专业的选修课，在优先满足本专业学生的选课需求以后，再满足外专业的学生。“志愿优先”算法则略为复杂，首先是在预选阶段，学生需确定所选选修课的优先志愿选择（根据学生一学期规定可选选修课门数来确定，一般为2-3级志愿），在正选阶段，首先满足第一志愿学生的选课需求，再依次满足二、三志愿学生的需求。
1.3 优先算法存在的问题
可以看到，各类优先算法都是设定了一个“优先对象”首先满足优先对象的选课需求，再考虑其他对象。各类算法“优先对象”设定的群体不同，在一定程度上解决了“选谁不选谁”的问题，但对于选课公平的考虑均欠妥。我们来考虑这样两个问题：
在极端的情况下：所有的优先原则都已使用，依然存在“选课人数大于课程容量”的现象，那么多出来的这部分人该怎么处理？各类优先算法的处理方式多采用“平均分布概率”算法来进行抽签，也就是说最后多出来的这部分学生，采取随机抽签的方式来解决“选谁不选谁”的问题。
在上述的前提下，又会出现这样的问题：在最后的选课结果上，会有学生中选多门课程，而有学生无中选课程的情况出现。实际上这样的情况在选课系统实现中，是应该极力避免的。
造成这样问题的原因在于人为地设定了一个“优先群体”，虽然保障了“优先群体”的选课权利，却未能很好地顾及非优先群体的选课权利。而使用“随机抽签”算法对非优先群体进行筛选，在一定程度上也破坏了选课的公平与公正。优先法的选课，更多的是满足了“优先群体”的选课需求，而忽视了对于非优先群体的公平，对于解决全校公共选修课的选课问题，优先算法是不适合的。
1.4 排除算法的提出
优先算法提出的初衷，在于首先考虑解决大部分学生的选课需求，将大问题转换为小问题的思路来解决问题。然而对于“小问题”的处理最终会回归到使用“平均分布概率”来进行抽签筛选，因此尚未有比“平均分布概率”算法更好的算法提出之前，问题就聚焦到前置算法的设计上，使得用“平均分布概率”算法进行抽签，能做到尽可能的公平。
如何保证每位学生都有中选的机会？如何确保冷门课程和热门课程的人数平衡？是我们对改进选课算法考虑得比较多的问题。首先从优先算法的弊端出发，我们认为不应该人为地设置一个“优先群体”来进行筛选，否则有违公平选课的初衷。另外从公平的角度考虑，我们认为已经中选课程的学生，其选课的优先级应该比未中选的学生低。出于这两方面的考虑，我们认为在使用“平均分布概率”算法来对选课学生进行筛选之前，应该尽可能的降低未中选的学生人数，亦即参与“平均分布概率”抽签的学生人数。因此我们设计了一套“排除算法”，来解决上述的问题。
2 排除选课算法的具体实现
排除算法同样适用于分为预选和正选两阶段的选课形式，在预选结束以后，对于所有的选修课按照如下流程进行筛选：
1) 考虑所有选课人数小于课容量的课程，将选择此类课程的所有学生，全部标记为中选状态。满足条件的课程标记为处理完毕。
2) 我院公共选修课允许学生每学期选择三门。第二步开始考察所有选课人数大于课容量课程，依次排除已经中选了2门以上、2门、1门的学生。每次排除以后都考察是否有课程的选课人数已经小于或等于课容量，满足条件的课程标记为处理完毕，同时标记相应学生为中选状态。
3) 再次考察剩余的选课人数大于课容量的课程，排除在待选集合中还有的学生，也就是说保留仅选择了这一门课程的学生。
4) 上述流程处理完毕以后，若还存在选课人数超课容量的课程，则用平均分布概率算法进行筛选，直到所有课程的中选人数小于和等于课容量的状态。
具体的流程图如图1。
程序在抽签阶段不涉及数据的删除，所有选课学生的信息都暂存在临时的“上课学生表选修”sk_skxsbxx中，选修课名单的筛选操作都在这个表中进行。在选课对未中签的学生只是把SFZQ（是否中签）字段标为0。每次选课的结果可以通过该字段进行统计。
sk_skxsbxx表使用的字段如表1所示。
对于最后的抽签程序，使用SQL语句来实现，可以参考下例：
select * from (select * from sk_skxsbxx where kch='2007108' and kxh='1001' and sfzq is null order by by dbms_random.random) where rownum
上面SQL的意思是：在备选学生表sk_skxsbxx中，在满足条件课程号：
kch='2007108' 和课序号：kxh='1001'和 是否中签标识sfzq 是空的集合中随机抽取5条。
实施“排除选课算法”以后，预选阶段选课人数不受课容量的限制，只要学生喜欢的课每个学生都可以选，这样可以在一定程度上反映某一门课程的受欢迎程度。
在筛选阶段由于系统在尽量满足每个学生在至少有一门课中选的前提下，再对结果进行随机筛选，因为对于绝大部分学生来说选课机会和中选几率是公平的，并且和学生选课的时间、专业、成绩等因素无关。可以保证绝大部分的学生都至少有一门选修课中选，最后需要利用平均分布概率算法进行筛选抽签的课程，一般只有少数热门课程，并且最后进行抽签的学生人数，也会大大少于实际选择该门课程的学生人数（大部分学生已经中选其他课程）学生无法中选课程的几率。
“排除选课算法”的实施，可以在“课程总容量”尚未远远大于“需选课学生人数”的情况下，比较好的解决学生公平选课的问题。在目前我院的应用当中，已经取得了比较好的效果。具体的反映就大大减轻了“补选”阶段的工作量，所有的选修课名单在“正选”阶段就可以全部确定了。
3 除选课算法外的其他工作
诚然，无论是我院采用的排除抽签选课法还是其他已有的各类算法，都只是在上课学生人选上进行的筛选，为了让学生能够更有目的、有规划地进行选课，在选课算法的优化设计之外还有应该在学生选课阶段对学生进行积极的引导。一是避免部分热门课程选课人数过于集中，导致中选率过低，二是增加部分冷门课程的选课人数，让尽可能多的学生所选课程都能中选。为此我们在选课系统中增加了实时中选率显示和推荐课程显示。
实时中选率通过计算已课程容量和已选课人数的比值，显示该门课程在目前状态下的中选几率，学生在选课时可以看到每门课程的中选率，以方便规划自己的选课。
假设一门课程课程容量为P1，已选课人数为P2，则当P1>=P2时，中选率显示为100%；当P1
另一方面，我们每天设定了两门选课人数过少的推荐课程，在选课页面设计上，将这两门课程重点突出显示，同样是期望对选课需求进行积极引导，避免学生集中选择少数几门热门课程。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文