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

并行志愿投档算法及其复杂性分析投档是高考录取中的核心工作，投档算法是指根据政策原则按志愿将考生分配到某一学校或专业，学校再根据其所排名次参照有关信息择优录取 ［2］ 在人工管理档案时期，由于受到管理模式和工作效率的限制，一般使用顺序志愿每志愿一个学校分段投档的方法进行投档，称之为分段顺序投档算法该算法每次操作涉及的考生数量较少，比较适合于人工管理，但缺乏对考生整体水平的比较，学校每个志愿要多次提档退档，从整体上讲不利于择优录取进入计算机辅助录取阶段后，人们对该算法做了一些改进，实行了分批次线上顺序投档算法该算法避免了过去“段段清”的复杂操作和局部比较的缺点，由于有了计算机提供的分类分校排档信息，档案管理过程中排名分档工作基本可以适应这种工作方式随着信息技术的迅速发展，九十年代末开始实施档案电子化和网上录取工程，使招生录取工作发生了一场管理模式的革命，产生了档案管理和录取过程“电子化” 、 “网络化”的新概念，从中也发展了过去的投档模式，开始推行分数优先并行投档的算法该算法提倡高分考生优先选择的原则，把过去学校选考生的概念转化为考生选学校这个算法要求首先将考生整体排序依次向学校投档，如果考生数超过十几万，在人工管理档案的时期工作量非常浩繁，难以操作，但由于档案的电子化管理这个问题便应刃而解了，这种投档模型减少了高分落榜和低分难于选择的困惑，受到考生和学校的普遍欢迎。

本文中将以形式的方法对该算法做出描述，进而对其复杂性进行分析一、算法描述首先我们给出一些符号记法和定义记 N 为自然数集（包括 0）, N+为正整数集记一个有限集合 S的元素数为｜S｜（有时也称集合的势）.定义 1.1　数字定长字符串集 Sn定义为所有长度为 n（n∈N +）的数字字符串集，即 Sn={r1r2……rn∣r i∈{0,1,…,9}，1≤i≤n}，n∈N +在 S 中的序“qj或 rj=qj上面的数字集合{0,1,…,9}改为某一有序字母表 V 时, 则 Sn定义为一般定长字符串集定义 1.2　学校编码集 U={u∣u∈S 5，u 为某学校代码}，考生号集 K＝ {e｜e∈S 14，e 为某考生号}定义 1.3　考生集 T 定义为一个 2 维关系表，其中各分量的值域取为有 N 或定长字符串集，即 T={（x 1，…，x n）|x i∈V i，V i为定长字符串集或 N，i =1,……,n 且 x1∈K｝ ，称 T 为按 Xj排序的，如果任意 t1，t 2∈T 其第 j 分量都保持同一序定义 1.4　计划集 P 定义为一个 2 维关系表，第一分量为学校代码，第二分量为学校招生数，即 P={(u，p)∣u∈U 5，p∈N }。

定义 1.5　考生档案集 E 定义为一个 2 维关系表，第二分量为分数，第三分量为档案号，即 E{(e, g, a)|e∈S 14，g∈N ,a∈S 10}定义 1.6 考生志愿集 C 定义为 k+1 个分量的 2 维关系表，有- 3 -C=｛（e, g, u1, …, uR）|e 为考生号，u i为报考学校号，g 为考生分数｝录取投档的过程即根据计划集、考生志愿集将考生按一定比例分配到各个学校，产生投档结果集定义 1.7　投档结果集 R 定义为 R= ∪R u，u∈U. 其中R u=｛（u,e,g）|（e,u 1, …, uk）∈C,存在 i 使 u=ui｝在投档时一般设定一个投档比例，即 Ru中的元素数按一定比例大于等于学校 u 的计划数，设比例系数为 l，则 l*p 即为 Ru的元素数投档过程的算法可描述如下初始化：置 Ru为空集，u∈U ；对所有（u 1，p）∈P，置p=l*p.步骤 1　将考生志愿集 C 按 g 降序排序，相同 g 值元素随机排序（以保证选择公平性） ，取表中第一个考生（e, g, u1, …, ur） ，定义变量 i=1步骤 2　取考生（e,g,u 1……,ur）志愿学校 ui得到（u i，p）∈P，如果 Ru中元素数＜p，则添加（e, g, u1, …, uR）到 Rui中，改写 p 中计划（u i, p）为（u i, p-1）转步骤 4。

步骤 3　 令 i=i+1, 如果 i1,hklogn 或许会大于logm 了，这也是程序设计开发中应该注意的三、总结本文以形式的方式定义描述了并行投档算法，并对其时间复杂性进行了分析，可给软件开发者提供一定的理论依据和开发方法，为了简化描述算法中并未涉及到专业和档案信息的组织，开发者在应用中不难加以补充形成实际应用背景下的计算模型另外，为了使录取过程更加公平合理，志愿学校间级差、加权投档等投档模式近年来也在推广应用，其计算模型和复杂性也是值得研究的参考文献[1]朱洪等，算法设计和分析，上海科学技术文献出版社，1989[2]张海泉、王希常、高考信息管理指南，黄河出版社，2000[3]李伟明等，考试的统计分析方法，高等教育出版社，1990。