自学考试考场编排尾数组合算法.doc

自学考试考场编排尾数组合算法自学考试考场编排尾数组合算法德阳市自学考试办公室 景小松 考场编排是自学考试管理系统中一个重要的部分。自学考试的考场编排有别于其它考 试的最大特点是参与编排的课程数巨大，普通高考、成人高考等考试每一场考试只有一门 或几门课程，而自学考试每一场考试的课程达到一百多门。一百多门的课程数给自学考试 的考场编排出了一道在其他考试中不会遇到的难题，就是如何把大量的课程尾数（对课程 报考科数用考场容量取余的结果称为课程尾数课程尾数，简称尾数尾数，在这里尾数为 0 的除外）按要 求组合起来。 目前自学考试编排考场的要求是：1.考场人数不超过考场容量考场容量（考场最多可容纳的人 数称为考场容量，现为 30 人） ；2.考场课程门数不超过规定门数，即课程容量课程容量（现为 6 门） ； 3.课程尾数不能分割；4.编排的考场数应尽量与最佳考场数最佳考场数接近（最佳考场数是指考场总报 考科数对考场容量向上取整的结果） 。 考场编排的考场数与最佳数相等或尽可能接近是自学考试考场编排中最基本的要求， 一方面减少考场数，节约考试经费，另一方面减少人工调整，提高了工作效率。自学考试 考场编排中最为核心的工作就是大量课程尾数组合，尾数组合算法的优劣直接关系到编排 的效率以及对考场数的影响。本文所探求的就是找到一种最佳尾数组合算法来达到这一目 的。 为了更好地设计考场编排的尾数组合算法，我们先来分析一下考场编排中最重要的对 象课程尾数。考场课程尾数分析。考场课程尾数分析。自学考试每次开考课程达几百门，平均每场近百门。以四川省 2008 年 10 月份为例， 共开考课程 470 门，平均每场 115 门，每场课程尾数也近百（除开整除的情况） 。不同规模 的考点，课程尾数出现是有一定的规律的。 小规模考点小规模考点（每场十个考场左右或以下）一般情况下课程报考人数少，容易产生大量 的小尾数，我们称之的小尾数（型）考点，所以在考场编排时经常遇到几个不足十人的考 场，为了节约经费，有的考点常常把两三个考场合为一个考场（当然是考务上的操作） 。在 考场编排算法中，课程容量的可调整，对这些小考点来说也是一种方便。县区考点一般情 况下都是小考点（除开有高校的县区） ，这部分县区考点占所有考点的大部分，所以在考场 编排中要充分考虑大部分考点的情况。 大中型考点大中型考点（每场二十考场左右或以上）一般情况下课程报考人数多，课程尾数的分 布相对均匀，我们称为尾数均匀（型）考点。大型考点可能出现比较特殊的大量大尾数， 我们称为大尾数（型）考点。有些中型考点小尾数也较多，主要出现在冷偏专业的课程上。 大中型考点主要分布在大中型城市。 我们把考场编排结果按照考场内的尾数特征来进行一个分类：一类是由几个小尾数组 成的考场，如 5+2+2+1+1+1，尾数和不大于 15，称为小尾数考场小尾数考场；一类是由一个大尾数组 成的考场，如 29、28 等，称为大尾数考场；一类是由一个中尾数组成的考场，如 16，17 等，称为中尾数考场中尾数考场。这三类考场都达不到考场容量称为不满考场，其余的尾数组合达到 考场容量的称为满考场。考场编排合理的情况下，每场不满考场只有一到两个，且考场余 数和不大于考场容量。现有系统中考场编排算法分析。现有系统中考场编排算法分析。我们先来分析一下现在四川省自学考试管理系统中考场编排算法。从只有一个考点的 自动编排结果分析来看，最后几个考场往往是小尾数集中的小考场。从尾数的组合情况来 看，是从大尾数开始，向下找到合适的最大的一个尾数，达到或尽量接近考场容量（30） ， 不足考场容量的再如此循环一次，循环次数不超过课程容量（6） 。我们把这种算法称为先先 大法大法。先大法算法简单，比较容易通过语言实现。先大法的算法流程图如下：未达到存在存在达到尾数从大到小排序选择最大尾数赋 给 P结束不存在不大于 30-P 的最 大尾数 Q不存在达到课程容量P=P+Q先大法对于尾数均匀分布的大中型考点比较合适，也容易达到最佳考场数，一般情况 下比最佳考场数要多出一至两个考场。但先大法对于存在大量小尾数的小考点是不合适的， 编排结果往往会出现多个小尾数考场，比最佳考场数多出二至三个甚至四个考场。小尾数 较多的中型考点也容易出现这种情况。大多数情况下，通过人工调整，每场都可以减少一 至两个考场。基本上每一场都需要人工调整来减少考场，增加了工作量，算法设计不合理， 编排效率不高。所以先大法对于大多数中小型考点的考场编排是不合适的。 在先大法中，人工调整是必须要做的工作，由于要人工参与，效率不高。那么，我们 是否可以把人工调整设计成算法来实现，减少人工成分，提高系统效率和工作效率呢？ 我们先来分析一下人工调整的过程，这实际上就是调整算法的设计。先大法容易产生 多个小尾数考场，当两个小尾数考场相加不足考场容量的，我们一般可以通过调整来减少 一个考场。我们把两个小尾数考场的尾数统一调整，通过排序，从大到小，先把最大的几 个尾数组合（比课程容量少一，5 个） ，计算出它们的和数（如 5+3+2+2+1） ，在已编排好 的有两个尾数的考场中寻找是否有这个和数，如有(如 13+17)，则把这个尾数与尾数组合对 换（17+5+3+2+2+1，13） ，如无，则在尾数排序中减少尾数组合和（如 5+3+2+1+1） ，又循 环一次，直至找到与尾数组合相对应的已组合尾数，如无，则尾数组合个数减少 1，在已赋给这组尾数一个考场号， 并从排序中删除它们编排好的有三个尾数的考场中寻找与组合和匹配的尾数。尾数组合的个数递减参与外围循 环。循环直到所要调整的尾数个数等于或小于课程容量（6 个）为止，然后再看有无要调 整的小尾数考场。虽然还有其它的人工调整的方法，但不好程式化，这里只介绍这一种小 尾数考场的合并算法合并算法，算法流程图如下：否否否否存在存在不存在不存在是是是两考场尾数统一从大到小排序， N=5，M=2两考场人数相加不大于 30，尾数个数大于 6从大到小选择 N 个尾数，记和为 P在编排好的尾数个数为 M 的考场中有否有值为 P 的尾数组合个数 N 不变，找到小 于 P 的最大值，并记为 P将尾数组合与找到的尾数对 换，将这组尾数从排序中删 除，尾数个数是否为 N对换尾数与剩余尾数组合为一考场组合个数 N 不变，组 合和 P 是否为最小值N=N- 1，M=M+1N=2开 始结 束对换尾数与剩余 尾数个数大于 6是 先大法编排尾数调整算法比较复杂，它把人工调整的整个过程程式化，虽然算法实现起来比较困难， 但却提高了编排设计的效率，减少了人工调整的环节。 在先大法中，第一个组合的尾数有可能不是最合适的，使得考场尾数组合达不到考场 容量。如：18、7、6、3、3 中，先大法组合为：18+7+3=28，达不到 30。而次大尾数组合 18+6+3+3=30，就比先大法组合要好。所以在先大法组合中可以加入两次次大组合，选择 最接近考场容量的组合。我们称这种算法为试探法试探法。 如果我们在先大法中加入试探法后，对每一场又进行调整算法进行程式调整，则使得 考场编排更加自动化，更加合理和高效。其它思路的尾数组合算法。其它思路的尾数组合算法。对于大多数县区考点，先大法往往会产生许多小尾数考场，在考场编排时要进行大量 的人工调整。这是由先大法本身算法所决定的，先大法中总是先选大尾数来组合，最后小 尾数余下的就比较多，从而出现了许多的小尾数考场。为了防止大量小尾数的剩余，可以 在选择尾数时，用试控法，选择最接近考场容量，并且尾数个数最多的一组。 当然，我们也可以重新设计一种尾数组合的算法来消除小尾数考场。我们可以用与先 大法相反的思路来设计新的算法，先选择最小的尾数来组合，如此循环，在最后一次循环 时用先大法来达到或接近考场容量。我们称这种算法为先小法先小法。先小法的算法流程图与先 大法大同小异，可参考先大法算法流程图。 先小法虽然可以解决先大法中小尾数考场的问题，但新的问题也就产生了。先小法中 小尾数优先，使得中尾数大量剩余，如 14、17、18 等，形成几个无法组合的中尾数考场。 在现在的考务管理中，尾数不允许分割。实际上，尾数分割在考务操作上是可行的，分割 后，可以通过增加试卷袋解决考务操作。如果允许尾数分割，中尾数考场的问题就迎刃而 解了。如上例中，我们可以把 14 分割为 12+2，可产生 18+12 与 17+2 的合理组合，这样就 减少了一个考场，一般情况下，只进行一至两次分割操作就可以达到最佳考场数。我们称 这种算法为分割算法分割算法。 在先大法与先小法中都是以最大的尾数开始组合尾数，往往会产生小尾数或中尾数的 剩余而产生一些组合上不合理的问题。我们是否可以考虑从中间的某一个尾数开始用先小 法组合，最后进行最大尾数的组合，一方面可以消除中尾数无法组合的情况，另一方面也 防止了小尾数的剩余。我们称这种算法为中点法中点法。中点法中，中小尾数先被组合，容易形 成大尾数考场，但考场余数和一般不会大于考场容量，与最佳考场数相等或最接近，所以， 中点法相对于先大法和先小法较为合理。 在中点法中，关键是开始组合的尾数的选择，也就是中点的选择。我们设计了一种比 较简单合理的中点选择法：我们把所有的尾数相加的和对考场容量向上取整（既取整有余 则取整数加一） ，所得的数称为最小组合考场数，能达到最小组合考场数就能达到最佳考场 数。把尾数从大到小排序后，中点就是最小组合考场数所对应的记录。我们以中点为界， 把大尾数的考场余数比为“坑” ，小尾数比为“石头” ，最小组合考场数就是我们要填的 “坑”的最小数目。中点可以形象地比做成“坑”与“石头”之间的供求平衡点。 以考场容量为 30 例，如果中点大于 15，就会出现“坑小石头大”无法组合的情况， 所以，一般情况下中点不能大于 15。中小型考点由于存在大量的小尾数，中点一般不会大 于 15，但对于大型考点有可能出现大量的大尾数，这时中点就可能大于 15。中点大于 15 时，在尾数不允许分割的情况下，只能通过增加考场数来容纳从 16 到中点的这部分无法填 “坑”的大“石头” ，从而下移中点至 15，下移几个记录，则考场数就增加几个。当然， 如果允许尾数分割，就不用增加考场。遍历算法。遍历算法。在上述的几种算法中，都是一个考场尾数组合完毕后进行下一个考场尾数组合，我们 统称为逐场（个）法。逐场法中，往往是先满足所组合考场的条件，没有考虑全局，难免 产生这样那样的问题。为解决这个问题，我们可以选择较为合理的中点法，用遍历法遍历法来分 配所有的尾数。我们以中点为界，从中点这个最大的“坑”开始向每个“坑”填“石头” ， 总是用最大的“石头”来填“坑” ，一次遍历一个“坑”只用一个“石头” ；填满的“坑” 就不再参与遍历；如此遍历几次（最多为课程容量的次数，6 次，如果没有课程容量的限 制，则可一直遍历下去，但一般情况下，遍历次数不会超过 9 次） ，由于供求平衡，所以最 后“石头”会用完；如果在遍历了课程容量所规定的次数后仍有尾数剩余，则剩余尾数按 先大法组合，从而出现个小尾数考场，这种情况往往会出现在有大量小尾数的考点。遍历 时，可以用上述的固定“坑”遍历，也可以用动态“坑”遍历，也就是每次遍历前都对未 填满的“坑”从大到小排序，然后从最大的“坑”开始用先大法填“坑” 。动态遍历比较合 理，但较固定遍历用语言实现起来比较困难。中点遍历法中虽然仍是用先大法来填“坑” ， 但一次遍历时只准用一次先大法，这样，大中小尾数的组合都兼顾到了，出现中尾数考场 及小尾数考场等问题的机率大大降低，基本上不会出现需要调整的情况。动态遍历算法动态遍历算法的 流程图如下（有些步骤简化省略）：存在否存在是不存在存在不存在不存在建立“坑”数组（30-尾数值，是一个 二维数组）和“石”数组，并降序排 序选择最大的 “坑”P选择不大于 P 的“石”RP-R=0赋给所对应的尾数组合一个 考场号，并在排序中删除选择下一个“坑” 并赋给 P结 束开 始“坑”数组重新排序（此时 “坑”值应减去所填“石头” ）找中点，调整中点（略）在遍历法中，也会出现一些特殊的情况。比如，中点为第一个 15 记录，中点附近尾数 分布情况为：18、17、16、15、15、15、14、14、13，明显的一点是，有一个 15 和一 个 14 的“石头”无法用上。也就是说，有许多大“石头” ，而能容纳大“石头”的“坑” 少，这时用遍历法，最后这部分大“石头”就无法找到合适的“坑” ，而有些“坑”却没有 填满。在允许尾数分割时，问题比较容易解决，用“碎石”的方法即可，而且能达到最佳 考场数。但不允许分割尾数时，就必须把这部分“石头”的一些转化为坑，一般情况下， 只须转化一到两个，也就是中点的下移一到两个记录，问题即可解决，但每转化一个就要 比最佳考场数多出一个考场。所以，在尾数不允许分割的情况下，中点选定后（除开中点 大于 15 的情况，因为中点大于 15 时，本身就要增加考场，使中点移到 15。 ） ，先计算最大 和次大“石头”的个数 SS，然后计算能容纳这两种“石头”的“坑”的个数 SK。如 SS>SK，即大“石头”个数大于大“坑”个数，就需把中点下移，下移记录数为 SS- INT（SS-SK）/2） ，INT 为取整运算。对考场编排的一些建议。对考场编排的一些建议。上面我们对课程尾数进行了分析，对尾数的组合算法进行了比较，在解决一些算法缺 点中，加入了调整算法、试探算法、分割算法、中点选择算法、转化算法等。在对比先大 法、先小法、中点法、遍历法等算法中，比较而言，遍历法是比较合理和高效的算法。在 所有算法中先大法是基础算法，遍历法是在中点法的基础上发展的。由于目前的自学考试 管理系统中考场编排用的是最容易实现但效率最低的先大法，需要大量的人工调整工作， 所以建议考场编排采用动态遍历法，这种算法是所有算法中最复杂的，用编程语言实现起 来困难一些，但却是编排最为合理的、效率最高的算法。 我省大部分考点是中小型考点，在考场编排时，应从经济和效率角度多考虑。考场编 排的四个规则中，除开最佳考场数这一要求外，其余的三个都是可以变化和改动的。考场 容量越大，编排的考场数就越少，原来自学考试的考场容量是 25 人，现在为 30 人，考场 数可减少 1/6，相应的考试经费也可节约不少，如果能把考场容量设为 35（5*7）人，则又 可以减少近 1/7 的考场数。现在大学和高中的标准教室可以达到考场容量为 35 人，可以考 虑把考场容量扩大为 35 人，这样可以提高监考效率，节约考试经费。对于考场课程容量则 完全可以不限制，在遍历法中会合理地分配尾数，使尾数比较均匀的分布，这样可以方便 小尾数考点的考场编排，减少考场数，节约经费。另外应允许课程尾数分割，这样可以解 决大尾数考点中遇到的中点大于 15 的问题，以及解决遍历法中的转化问题，考务上只是增 加几份试卷袋，却可以使编排结果为最佳考场数，起到减少考场、节约费用的作用。 我们这里解决的是自学考试考场编排中核心的尾数组合算法。考场编排中还有许多其 它方面的因素需要考虑，比如多考点自动编排，座位随机编排，课程指定编排等。在目前 的自学考试管理系统中，座位随机编排和课程指定编排等都解决的比较好，在这里对多考多考 点自动编排点自动编排提点建议。在大中型考区要遇到多考点自动编排的问题，一般情况下，我们都 要在多考点中指定第一考点，第二考点等，在考场编排时，优先排满第一考点，然后是第 二考点，依此类推。在目前的自学考试管理系统中，多考点自动编排相当混乱，不能满足 多考点考场分配的基本要求，第一考点常常排不满，各考点尾数编排结果极不合理，有些 考点的编排结果往往考场数大于考点容量即考点最大考场数，不得不对每一场的每一个考 点的编排结果进行考点间的人工调整，增加了工作量，算法不合理，效率不高。因此，需 要对多考点自动编排算法进行改进。一种比较合理的算法是通排法通排法，既所有课程先按一个 考点的情况用动态遍历法编排考场，然后根据考点优先顺序分配考场，这样既使得尾数组 合合理，又满足考点分配要求。