并行投档算法及其复杂性分析_zhang.doc

并行志愿投档算法及其复杂性分析 　　投档是高考录取中的核心工作，投档算法是指根据政策原则按志愿将考生分配到某一学校或专业，学校再根据其所排名次参照有关信息择优录取［2］。在人工管理档案时期，由于受到管理模式和工作效率的限制，一般使用顺序志愿每志愿一个学校分段投档的方法进行投档，称之为分段顺序投档算法。该算法每次操作涉及的考生数量较少，比较适合于人工管理，但缺乏对考生整体水平的比较，学校每个志愿要多次提档退档，从整体上讲不利于择优录取。进入计算机辅助录取阶段后，人们对该算法做了一些改进，实行了分批次线上顺序投档算法。该算法避免了过去“段段清”的复杂操作和局部比较的缺点，由于有了计算机提供的分类分校排档信息，档案管理过程中排名分档工作基本可以适应这种工作方式。随着信息技术的迅速发展，九十年代末开始实施档案电子化和网上录取工程，使招生录取工作发生了一场管理模式的革命，产生了档案管理和录取过程“电子化”、“网络化”的新概念，从中也发展了过去的投档模式，开始推行分数优先并行投档的算法。该算法提倡高分考生优先选择的原则，把过去学校选考生的概念转化为考生选学校。这个算法要求首先将考生整体排序依次向学校投档，如果考生数超过十几万，在人工管理档案的时期工作量非常浩繁，难以操作，但由于档案的电子化管理这个问题便应刃而解了，这种投档模型减少了高分落榜和低分难于选择的困惑，受到考生和学校的普遍欢迎。本文中将以形式的方法对该算法做出描述，进而对其复杂性进行分析。 一、算法描述 首先我们给出一些符号记法和定义。 记N为自然数集（包括0）, N+为正整数集。记一个有限集合S的元素数为｜S｜（有时也称集合的势）. 定义1.1　数字定长字符串集Sn定义为所有长度为n（n∈N+）的数字字符串集，即Sn={r1r2……rn∣ri∈{0,1,…,9}，1≤i≤n}，n∈N+。在S中的序“”定数为：如u= r1……rn，v=q1…q n，uv，即存在i，1≤i≤n, 使riqi，且不存在ji使rjqj或rj=qj。上面的数字集合{0,1,…,9}改为某一有序字母表V时, 则Sn定义为一般定长字符串集。 定义1.2　学校编码集U={u∣u∈S5，u为某学校代码}，考生号集K＝ {e｜e∈S14，e为某考生号}。 定义1.3　考生集T定义为一个2维关系表，其中各分量的值域取为有N或定长字符串集，即T={（x1，…，xn）|xi∈Vi，Vi为定长字符串集或N，i =1,……,n且x1∈K｝，称T为按Xj排序的，如果任意t1，t2∈T其第j分量都保持同一序。 定义1.4　计划集P定义为一个2维关系表，第一分量为学校代码，第二分量为学校招生数，即P={(u，p)∣u∈U5，p∈N }。 定义1.5　考生档案集E定义为一个2维关系表，第二分量为分数，第三分量为档案号，即E{(e, g, a)|e∈S14，g∈N ,a∈S10} 定义1.6 考生志愿集C定义为k+1个分量的2维关系表，有 C=｛（e, g, u1, …, uR）|e为考生号，ui为报考学校号，g为考生分数｝ 录取投档的过程即根据计划集、考生志愿集将考生按一定比例分配到各个学校，产生投档结果集。 定义1.7　投档结果集R定义为R= ∪Ru，u∈U. 其中 　　Ru=｛（u,e,g）|（e,u1, …, uk）∈C,存在i使u=ui｝ 在投档时一般设定一个投档比例，即Ru中的元素数按一定比例大于等于学校u的计划数，设比例系数为l，则l*p即为Ru的元素数。 　　投档过程的算法可描述如下 初始化：置Ru为空集，u∈U ；对所有（u1，p）∈P，置p=l*p. 　　步骤1　将考生志愿集C按g降序排序，相同g值元素随机排序（以保证选择公平性），取表中第一个考生（e, g, u1, …, ur），定义变量i=1。 步骤2　取考生（e,g,u1……,ur）志愿学校ui得到（ui，p）∈P，如果Ru中元素数＜p，则添加（e, g, u1, …, uR）到Rui中，改写p中计划（ui, p）为（ui, p-1）转步骤4。 　　步骤3　 令i=i+1, 如果i=r转步骤2, 否则转下一步骤。 　　步骤4　取下一个考生，令i=1, 转步骤2处理。 　　步骤5　结束投档过程。 为了简化叙述过程，上述定义和算法中仅涉及了一个志愿的信息和投档过程，通过增加循环可转化多志愿多学校投档，实际应用中一般一个志愿投档后重新组织生源再进行下一志愿投档，所以较少使用多志愿同时投档。 二、算法复杂性分析 由上一节的算法描述可以看到并行志愿投档算法主要的步骤为步骤1和步骤2、3、4，形成迭代过程，由此可采用加法原则分别分析两个过程的复杂性，让考生数为m