一种改进的回溯试探组卷算法  

An Improved Backtracking Search Paper-generating Algorithm

作　　者：李川 杨俊清 王奕豪 张少茹[2] LI Chuan;YANY Jun-qing;WANG Yi-hao;ZHANG Shao-ru(School of ComputingyXt an Aeronautical University,Xi'an 710077,China;Health Science Center,Xi an Jiaotong University,Xi'an 710061,China)

机构地区：[1]西安航空学院计算机学院,西安710077 [2]西安交通大学医学部,西安710061

出　　处：《火力与指挥控制》2019年第9期144-148,共5页Fire Control & Command Control

基　　金：国家自然科学基金(71373203);2016年陕西省科技工业攻关项目(2016GY-139);2016年度西安航空学院校级科研基金(2016JS3223);2018年大学生创新创业训练计划基金资助项目(DCX2018056)

摘　　要：组卷是在线测评系统中一个重点、难点问题,常见组卷算法随机抽取法、遗传算法、回溯试探等各有优缺点,只能适应一些特定的情况。针对回溯试探法平均组卷时间长、重复率高的问题,进行了两次改进,分别是一次回溯试探搜索的多个解和修正重复率降低重复率。通过试验,得出的结论是改进回溯试探法的平均组卷时间和重复率都有明显降低且比较稳定,可适用于各种规模的题库。Paper-generating is an important and difficult problem in online judge system,common paper-generating algorithms such as random extraction method,genetic algorithm and backtracking search method etc have their advantages and disadvantages,which can only adapt to some specific situations. This paper aiming at the problem that backtracking method’s average paper-generating time is long and repetition rate is high,the backtracking method has been improved twice,one is one backtracking search and more solutions,and the other is correcting the repetition rate to reduce the repetition rate.Through the experiment,it is concluded that the average paper-generating time and repetition rate of the improved backtracking search method are significantly reduced and relatively stable,and can be applied to databases of all sizes.

关 键 词：组卷 回溯 约束 效率 重复率 

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