基于考生比例的考场编排问题的分治算法  

Sub-rule algorithm for arrangement of examination seat based on proportion of examinee

作　　者：王文发[1,2] 张根耀[1,2] 马春梅[3] 李红达[4] 

机构地区：[1]延安大学计算机学院 [2]延安大学软件研究与开发中心 [3]延安大学图书馆 [4]中国科学院软件研究所信息安全国家重点实验室

出　　处：《计算机工程与设计》2010年第12期2872-2875,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(60573052);延安大学预研基金项目(YJS07-10)

摘　　要：根据高考考场编排的一般要求和约束条件,建立了相应的数学模型,提出了基于考生比例的考场编排问题的分治算法,给出了算法的具体步骤,分析了算法的复杂度,验证了算法的合理性和有效性。实验结果表明,该算法能有效控制考生的分布,编排过程完全可以控制,最大程度地避免了前后左右相邻考生属同一中学,编排结果达到了比较理想的均衡状态。该算法速度快、效率高、易于实现、继承性强,很容易推广到其它类似问题的求解。Combining with the usual requirement and multi-constraint conditions of examination arrangement,the math model of exami-nation arrangement is built,and a sub-rule algorithm for arrangement of examination seat based on the proportion of examinee is proposed.Then the detail step of the algorithm is given,and the complexity is analyzed.The analysis and experimental result show the algorithm can control the distribution proportion of examinee and the arrangement process,can completely avoid the examinee of the same high school is arranged the adjacent position.The model and algorithm is used in all kinds of arrangement of examination seat and other cor-responding problems because of having some good excellences,such as,speediness,efficiency,inheritance and realization easily.

关 键 词：分治算法 考场编排 多约束分配 流程图 复杂度 

分 类 号：TP315[自动化与计算机技术—计算机软件与理论]