网上选课的随机抽签算法改进分析

摘　要：每个学生都具有自身的选课权利，所以一种不仅能够适应学校选课复杂环境的算法而且能够体现选课公平公正的算法是目前亟待解决的问题。本文主要通过对网上选课算法进行分析与研究，主要采用随机抽签算法并进行了改进，不仅具备了随机抽签算法的优点而且同时也尽最大努力满足学生意愿，体现了学校的人性化管理理念。

关键词：选课系统；随机抽签；志愿等级

1.绪论
　　近年来随着教育改革的不断发展和深化，对教务管理提出了新的要求。目前各个高校已经全面实现了学分制。学分制的方式主要特点就是只要学生选课在按专业计划内进行修完一定的学生即可。实现学分制管理，学生自主性加大，有利于学生个性化方向的发展。
　　随着计算机和网络技术的发展，各个高校都具备了良好的校园网络和信息系统。而且随着学生规模的不断扩大，使得选课系统是学分制的重要措施和工具。选课系统可以满足学生在一定时间段内随时随地选课，可以充分发挥选课的主观能动性，是实现学生制的重要工具。
　　但是开课情况、冲突判断、选课数据过程调整与控制等因素使得高校选课变得日益复杂。每个学生都具有自身的选课权利，所以一种不仅能够适应学校选课复杂环境的算法而且能够体现选课公平公正的算法是目前亟待解决的问题。
2.网上选课算法综述
　　网上选课算法较多，主要有先来先服务算法、基于概率动态分布算法、随机抽签算法和按权重筛选算法等。
　　（1）先来先服务算法
　　这种算法的核心思想类似于"排队买票"的思想，是最简单的算法。学生在登录选课系统后，如果是在选课时间范围内，那么进行选课操作，如果这门课程没有满员，那么就选课成功，如果满员，则选课失败[1]。
　　这种算法是最简单也是实现最容易的算法，同时也是非常直观的算法。学生能不能成功选课能够真实快速的反应出来，这种算法比较适用于选课人数不多的情况。但是目前高校扩招，学生人数不断增加，这样的选课算法基本不能满足学生的需求。比如如果300名学生想选择随机过程这门课程，但课程限制人数为150，那么后到的150人选课成功的几率基本是0，这样就不能体现选课权利的公平性。
　　（2）基于概率动态分布算法
　　这种算法就是在选课过程中，对学生选课选中的概率依据实际情况进行调整。如果课程参选的学生远小于某一门课程的容纳上线，那么这些学生选课的概率基本为100%，反之，如果课程参选人数与课程容纳上线接近时，则需要对选课成功的概率进行降低，以更好的控制选课过程。
　　其核心思想就是如果选课人数过多，则降低选中概率，以便留出适当名额为后面学生流出机会；如果选课人数过少，则提高选中概率，以便这个课程选中人数能够满足开课的需求[2]。
　　基于概率动态分布算法能够尽让学生在选课时拥有相同的概率选课，同时保证学生在第一时间内了解课程是否选中，这种算法不仅体现了公平公正，而且也大大节约了学生的整个选课过程。
　　（3）随机抽签算法
　　随机抽签算法就的核心思想就是将选课分为两个过程：预选和抽签。在第一个预选阶段，任意选课学生都是可以通过选课系统进行选课，选择的数量不限，可以是一门，也可以是多门；当预选结束后，则进入抽签过程[3]：
　　①如果某一课程选课人数是小于该课程的选课容量的上限且大于该选课容量的下限，则所有选择该课程的学生选课成功；
　　②如果选课人数小于该选课人数的下限，则该选课课程取消，通知选择该课程的学生取消原因及告知重新选择其他课程。
　　③如果某一课程选课人数小于该课程的选课容量，则随机将多余的人数筛选出来，告知其重新选课。
　　比如有65位学生想选择体育篮球课，但该课程的选课容量上限为50人，下限为10人。用随机抽签算法的选课流程就是将学生预选阶段结束后，通过随机抽签的方式将剩余的15位学生抽取出来，将另外的50人定为选课成功的名单。
　　随机抽签算法是必须通过后台才能生成选课表，对选课过程进行了简化，学生在一定时间内随时进行选课更改，选课结果与选课时间并无关系。这种算法在一定程度上保护了每个学生应有的选课权利，通过随机抽签的方式剔除多余选课人数，体现了选课的公平、公正和合理。同时这种算法不会造成学生在特定选课时间蜂拥而上而造成的网络瘫痪，且选课服务器的压力也会小很多。
　　（4）按权重筛选算法
　　这种算法是对随机抽签算法改进的一种。其基本思想就是在学生选课时加入了一定的权重，如果权重越高，则选课成功概率就越大，反之，权重越低，则选课失败的概率越大[4]。
　　对权重的分配方法较多，可以是依据学校的规定，比如学生以往的成绩越高，其权重越大；或者自身专业的专业课，给予的权重也越大。这种分配方式和依据可以根据学校的自身情况进行设定，具有较大的自主性[6]。
　　这种算法不仅继承了随机抽签算法的公平公正特性，而且也对学生的个性差异进行了体现。
3.基于随机抽签算法的改进
　　随机抽签算法由于抽签的概率是相同的，在很大程度上体现了选课的公平公正，使每个人都拥有相同的选课权利。但是这种算法对于人性化管理体现的不够充分，对于那些选课失败的人来说，这种选课方式是非常不通人情的。所以为了体现公平的同时兼顾人性化管理，笔者对算法进行改进。
　　改进的随机抽签算法核心思想就是来源于高考志愿的填报的思想：学生在选课时给予三个志愿填写机会。每个志愿有不同的优先级，最优先的是第一志愿，以此类推。选课的过程还是给予随机抽签算法，有预选和抽签两个。
　　选课第一阶段：该阶段就是学生预选阶段，学生可以在任何时间内进行选课。与随机抽签算法不同的便是，这个阶段学生在选课时需要将这个课程归集为志愿等级。只有志愿等级选择后，才能进入下一个课程的选择。当预选阶段时间截止后，则系统会自动进入下一个阶段。
　　选课第二阶段：这一阶段就是依据学生之前的选择进行抽签。每个课程都有第一志愿表、第二志愿表和第三志愿表等三张表格。系统首先会提取这三张表格。假如某个课程的最大人数为M，而选择这个课程的三张表格中显示的数位A、B、C。接着系统会分析这个第一志愿表中A与M进行比较：
　　①第一志愿选择
　　如果A小于M，则说明A中的学生选课全部选课成功，并进入对第二志愿表B的选择。反之，如果A大于M，则说明A的数量要高于课程的限制数 ，那么系统将随机选择M个选生作为选课成功者，并结束选课。
　　②第二志愿选择
　　上面说到，如果A小于M的，则会将第二志愿的学生充实过来，方法与第一志愿的选择是一样的。
　　最后在选课结束前，系统还会将选课人数与选课上线进行比对，如果选课成功的人数小于M，说明课程未报满，还有多余名额，系统会发选课通知。当处理结束后则会进入对下一个课程选择。具体如图1所示

4.结论
　　每种选课算法都有其自己的优点和缺点，都有其自身的使用范围。随机抽签算法具有简单、灵活、合理、公平公正等特点，故本文采用了这个算法来实现网上选课。
　　笔者为了考虑选课的人性化管理，通过对随机抽签算法进行一定的改进，加入按志愿等级进行选课，这不仅具备了随机抽签算法的优点而且同时也尽最大努力满足学生意愿，体现了学校的人性化管理理念。

参考文献：
[1] 黄海东.网上选课系统的算法分析与改进[J].淮南职业技术学院学报,2009,9(1):27-28
[2] 刘军,阳小华,黄洁.基于.NET组件技术的选课管理系统的设计团[J].电脑开发与应用, 2006, 19(2): 55.
[3] 徐明.志愿随机筛选算法在选课系统中的应用[J].南通纺织职业技术学院学报,2007,7(4):33-35
[4] 梁里宁.网上选课系统的设计与实现[J].暨南大学学报(自然科学版), 2002, 23(5): 39-40.
[5] 王艳,刘双红,李玲玲.基于加权关联规则的选课推荐系统的构建[J].郑州轻工业学院学报:自然科学版,2009(5):44-47.