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

《并行投档算法及其复杂性分析_zhang》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行志愿投档算法及其复杂性分析　　投档是高考录取中的核心工作，投档算法是指根据政策原则按志愿将考生分配到某一学校或专业，学校再根据其所排名次参照有关信息择优录取［2］。在人工管理档案时期，由于受到管理模式和工作效率的限制，一般使用顺序志愿每志愿一个学校分段投档的方法进行投档，称之为分段顺序投档算法。该算法每次操作涉及的考生数量较少，比较适合于人工管理，但缺乏对考生整体水平的比较，学校每个志愿要多次提档退档，从整体上讲不利于择优录取。进入计算机辅助录取阶段后，人们对该算法做了一些改进，实行了分批次线上顺序投档算法。该算法避免了过去“段段清”的复杂操作

2、和局部比较的缺点，由于有了计算机提供的分类分校排档信息，档案管理过程中排名分档工作基本可以适应这种工作方式。随着信息技术的迅速发展，九十年代末开始实施档案电子化和网上录取工程，使招生录取工作发生了一场管理模式的革命，产生了档案管理和录取过程“电子化”、“网络化”-5-的新概念，从中也发展了过去的投档模式，开始推行分数优先并行投档的算法。该算法提倡高分考生优先选择的原则，把过去学校选考生的概念转化为考生选学校。这个算法要求首先将考生整体排序依次向学校投档，如果考生数超过十几万，在人工管理档案的时期工作量非常浩繁，难以操作，但由于档案的电子化管理这个问

3、题便应刃而解了，这种投档模型减少了高分落榜和低分难于选择的困惑，受到考生和学校的普遍欢迎。本文中将以形式的方法对该算法做出描述，进而对其复杂性进行分析。一、算法描述首先我们给出一些符号记法和定义。记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…qn，u

4、，1≤i≤n,使riqj或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）

5、xi∈Vi，Vi为定长字符串集或N，i=1,……,n且x1∈K｝，称T为按Xj排序的，如果任意t1，t2∈T其第j分量都保持同一序。定义1.4　计划集P定义为

6、一个2维关系表，第一分量为学校代码，第二分量为学校招生数，即P={(u，p)∣u∈U5，p∈N}。定义1.5　考生档案集E定义为一个2维关系表，第二分量为分数，第三分量为档案号，即E{(e,g,a)

7、e∈S14，g∈N,a∈S10}定义1.6考生志愿集C定义为k+1个分量的2维关系表，有-5-C=｛（e,g,u1,…,uR）

8、e为考生号，ui为报考学校号，g为考生分数｝录取投档的过程即根据计划集、考生志愿集将考生按一定比例分配到各个学校，产生投档结果集。定义1.7　投档结果集R定义为R=∪Ru，u∈U.其中　　Ru=｛（u,

9、e,g）

10、（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中

11、，改写p中计划（ui,p）为（ui,p-1）转步骤4。　　步骤3　令i=i+1,如果i<=r转步骤2,否则转下一步骤。　　步骤4　取下一个考生，令i=1,转步骤2处理。　　步骤5　结束投档过程。-5-为了简化叙述过程，上述定义和算法中仅涉及了一个志愿的信息和投档过程，通过增加循环可转化多志愿多学校投档，实际应用中一般一个志愿投档后重新组织生源再进行下一志愿投档，所以较少使用多志愿同时投档。二、算法复杂性分析由上一节的算法描述可以看到并行志愿投档算法主要的步骤为步骤1和步骤2、3、4，形成迭代过程，由此可采用加法原则分别分析两个过程的复杂性，让考生数

12、为m，学校数为n。步骤1是一个排序过程，考虑有充分大的内存的情况，根据排序的复杂性研究［2］，可以考虑其复杂性为O(mlo