送交者: 老椰子 于 November 28, 2007 10:16:50:
一个高考录取算法 －《云雾中的返顾》
银色的世界耀眼地闪光
我踏着积雪向黄色的小楼走去。。。
（一）问题的提出
今年，是恢复高考的30周年。今天，是恢复后的第一次高考在吉林省开考的30周年日。那天早上，刚下过一场清雪，长春银装素裹。
发生于1977年的恢复高考是个非常重要的历史事件。它对随后的中国社会产生了重大影响，改变了我们这一代人中间的许多人的命运。在这样的一个整十倍数年的纪念日，觉得好像该写点儿什么，最后选个简单的，就写个“理想的”计算机高考录取处理算法。算法的程序设计部分实现起来大约是一个熟练程序员三、五天的工作量。从现在的环境看，这东西好像不现实，要不怎么说是“理想的”呢。
（二）讨论
我们这一代人从自己的生活经验知道，为社会选择人才，或者从另一方面说，为确定个人在社会网络中的位置，考试比类似举孝廉那样的推荐进步、公平，尽管考试制度本身也有弊端，主要是，人的实际能力并不能通过几个小时的考试来准确表现。但是，似乎没有其他较好的替代方法。
既然采用了考试制度，就应该努力使这种制度公平。我认为，分数面前人人平等应该是一个保证最大的公平性的基本原则。基于这个原则，应该尽量遏制两种现象，一是歧视，二是人为干预。歧视包括地域歧视和种群歧视，可能还有别的。美国这里就有种群歧视现象：仅仅因为一个考生在生物学或遗传学上属于某些个种群的就可以以较低的分数进入某校。我认为这是荒谬的，表面上讲是为多元化，是照顾这个考生和这个种群，殊不知实际上是对这个考生和这个种群的尊严的亵渎，是对其他竞争者的利益的侵犯。在中国，地域歧视较为突出，其实质和所造成的负面社会效果类似。
人为干预发生在录取阶段。我所了解到的国内的情况是，相关的负责人有很大的权力。这样的话，不可避免地孳生出腐败和不公。美国这里在这方面的情况要好的多。这里有的学校有时会有面试，属于一种人为干预，但实施面试的通常是在本地随意指定的有空闲的校友，其意见所起的作用也不是很大。
高考录取中的歧视和人为干预是可以完全消除的，那就是由计算机来处理这件事。据说，福州市用计算机分配初等学校，即根据居住地点确定所入学校的问题。这是排除歧视和干扰的一个有意义的案例，它提示我们，高考录取亦可类似地进行。
以下是一种设计。此设计包括基本设置和算法两个部分。基本设置部分和现有的情况基本相同，只是这里有些东西明确了一些。算法部分用一句话简单地描述就是：以志愿分类，按分数排序，分梯次录取（简称，三个分算法）。
（三）基本设置
1）全国统一规定全部的高考的科目，比如6门：数学、物理、化学、中文、历史、英文。全国统一命题。全国统一批卷。
2）每个学校的每个专业选择自己要求的科目，确定选择了的科目的重要性顺序，确定招生名额。比如：吉林大学软件专业选择数学、物理、英文3门，重要性如序，预备招生200人。这些信息每次高考前公布。另外，还要公布这个专业的其他限制条件（如专业对身体条件的要求）和本次招生数量。注意，这里的专业是狭义名词，指的是一个学校里的一个本科生培养方向。
3）考生在每个录取梯次填写N个志愿。
（四）三个分算法
【1. 一个梯次的录取】对于变量I从1到N循环以下两个步骤：
［1.1 第I志愿排序］对尚未完成录取数额的每个专业X，将所有第一志愿报了X的考生按总分数高低排成序列S(X，I)。对总分数相同者，按第一重要科目的分数排序。对第一重要科目分数相同者，按第二重要科目分数排序。以此类推，直到最后一个科目。如最后一个科目的分数仍然相同，由软件产生随机数排序。
［1.2 第I志愿录取］X按顺序人工录取S(X, I)的前N(X, I)名。第I志愿录取结束。被录取的考生的名字删除。其余考生的第I志愿作废。
【2. 录取为空？】如果对于所有的X和所有的I，N(X, I) ＝ 0，则属于录取为空现象，整个录取作业结束。否则，就是存在至少一个X和一个I，使N(X, I) > 0，即至少有一个专业X按第I志愿录取了一名考生。
【3. 专业完成？】如果所有的专业已经满额，则操作停止，整个录取作业结束。否则，就是尚有专业没有完成录取，这时要将这些专业和欠额公布，考生依此重新决定下一个梯次的N个志愿。
【4. 考生完成？】如果已经没有考生对所公布的余下专业感兴趣，则操作停止，整个录取作业结束。否则，就是尚有考生对新公布的某些专业感兴趣，这时操作要返回上述步骤1开始下一个梯次。
这个算法显然是收敛的。
老椰子
2007年11月28日于纽约