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

李 川，杨俊清，王奕豪，张少茹

（1.西安航空学院计算机学院，西安 710077；2.西安交通大学医学部，西安 710061）

0 引言

测评是现代教育教学中，考察学生知识掌握程度的一种有效方式［1］。在线测评与传统纸质试卷测评的优势是方便、高效、节约资源等，在线测评系统中有一个重要的问题——组卷，组卷是指按照给定的组卷约束条件从试题库中选取一定数量的试题组成若干套试卷的过程［2-3］，这样组出的试卷不但要满足指定的题型要求，而且要使试卷中各题目的难度配比能满足试卷的平均难度，同时又使试卷中出现的知识点不重复。试题库的结构和题目数量、质量以及所使用的组卷算法的好坏，将直接决定着组卷系统所组成试卷的质量。组卷算法将直接影响试卷的知识点覆盖率、试卷难易及组卷成功比等问题，进而影响到考试系统的普及推广。

利用组卷算法生成科学、合理的试卷且组卷效率高是衡量一个组卷算法优劣的标准，目前常用的组卷算法主要有随机选取法、回溯试探法、遗传算法等［4］。

随机选取法根据条件对题库进行分类和规整，挑选符合条件的题目组卷。该算法设计简单，在一些小型在线考试系统中应用较多，但算法模式固定，组卷成功率低，试题覆盖率低。回溯试探法是建立在随机选取算法基础上的［5］，随机选取算法的缺点是组卷成功率低［6］，回溯性试探法对此进行了改进，该算法将每次随机选取的结果记录下来，当组卷不成功时回退到上一步，继续试探，直到组成试卷成功［7］。该算法缺点是组卷过程繁琐，耗时量大，效率和组卷质量都不高。遗传算法是通过类比的方式，模拟生物在大自然中的一种繁衍，变异的一个过程［8］，将这种类比的结果应用到计算机模型上。繁衍是通过自然环境下对自己的子孙后代进行筛选，变异则是依照适应度函数求解最优解的一个过程［9］。透过生物的表现型去找寻其内在基因编码的规律，这样才能总结出一定的经验去完成由表现型到遗传编码的对应关系，将这种对应关系简化为二进制编码的关系，找寻到初代的生物种群，然后模拟后代在生存环境中的遗传和变异的规律［10-11］。遗传算法的缺点是过程较为繁琐，实现困难。

以上这些算法都能实现组卷，但各有优缺点，也都存在一些适应情况，本文研究设计一种改进的回溯试探法组卷算法模型，以解决回溯试探组卷算法效率低、重复率高的问题。

1 改进的回溯试探组卷算法

对于一个回溯试探问题Q，要有如下理论：

定义1：定义状态空间E={（x1，x2，……，xn）|xi∈si，i=1，2，……，n}，其中（x1，x2，……，xn）是一个n 元组，其中si是xi的定义域，且|si|有限［12］；

定义2：定义一个约束集D={di| i=1，2，……，m}，其中，di是对xi的一个约束［13］；

定理1：如果状态空间E 中存在一个n 元组满足D 的全部约束，称该n 元组为问题Q 的一个解。

定理2：如果一个i 元组（x1，x2，……，xi）满足约束集D 中仅涉及到x1，x2……，xi的约束，那么对于任意j 元组（x1，x2，……，xj）也满足约束集D 中仅涉及到x1，x2，……，xj的约束，其中，j

针对定理2，可有如下推理：

推理1：如果j 元组（x1，x2，……，xj）是i 元组（x1，x2，……，xi）的一个真子集，j

由推理1 可知，对于一个回溯试探问题Q，如果某个j 元组（x1，x2，……，xj）不是问题Q 的解，且j 元组（x1，x2，……，xj）是i 元组（x1，x2，……，xi）的一个真子集，那么对于任意i 元组都不是问题Q 的解，因而对i 元组（x1，x2，……，xi）中除去子集j 元组（x1，x2，……，xj）的剩余元素（xj+1，……，xi）就不必再测试，这减少了测试的次数，提高了算法的效率。

回溯法利用上述理论，在状态空间E 中遍历一个n 元组（x1，x2，……，xn），如果满足D 的所有约束，则该n 元组是问题Q 一个解；否则，如果在检测到xi时不能满足约束集D 中的部分约束，则以i 元组（x1，x2，……，xi）的所有n 元组（x1，x2，……，xn）都不是问题Q 的解，回溯到状态xi-1，继续遍历状态空间E 中的其他n 元组，直至遍历E 结束。可以看出回溯试探组卷算法是一种DFS 算法［14］，根据组卷约束条件深度搜索，直到试卷生成为止。如果试探到某一步时，发现组卷不成功，就回溯到上一步继续试探。该算法是通过试探和纠错来寻找解决方案的，回溯试探算法的过程如图1 所示。

图1 回溯试探法流程图

在组卷过程中，解空间就是在试题库中选取n个试题的集合，当试题库规模很大时，解空间树也随之很大，一般的穷举算法时间复杂度会很大，从回溯试探法的流程中可以看出，可以通过缩小解空间树的大小提高回溯试探法的效率，根据不同的组卷应用情况，设计方案如下。

定义3：如果n 元组（x1，x2，……，xn）中的分量xi（0≤i≤n）之间是有序的，则称n 元组为有序n 元组，反之称为无序n 元组。

定理3：有序n 元组（x1，x2，……，xn）构成的状态空间大小为n！［15］。

定理4：无序n 元组（x1，x2，……，xn）构成的状态空间大小为1。

一般组卷过程中，如果两套试卷中只要出现相同的题目，而不管题目的序号是否相同，就认为存在重复试题，这种情况下组成的试卷质量较高，但可能存在组卷失败（题库规模不足等原因）、组卷效率低等问题。而在实际应用中，例如有些考试试卷题目相同，但题序不同组成了AB 卷，这样既保证了组卷效率，又保证了试题质量及防止作弊。

定理5：如果一个n 元组（x1，x2，……，xn），满足D 的所有约束，那么该n 元组就是问题Q 的一个解，而x1，x2，……，xn的任意排列组合的n 元组都是问题Q 的解。

推论2：由定理3、定理5 可知，当回溯探测出一个n 元组（x1，x2，……，xn）是问题Q 的一个解，即可得出问题Q 的n！个解。

基于上述理论的组卷过程中如算法1：

在回溯试探算法中，提高算法效率的一种重要手段是通过剪枝减少多余或无效的搜索，常用的剪枝函数，一种是使用约束条件函数剪去不满足约束条件的状态集，另一种是采用限定函数剪去得不到最优解的状态集。

本文所述的回溯试探组卷算法采用了上述两种剪枝函数，减少了回溯试探的次数，但生成问题一个解的其他全排列解的递归过程，即减少开销的同时又增加了额外的开销，相比较而言，减少的开销>>额外增加的开销，总之可以有效地降低算法的时间复杂度。

这种算法组成的试卷，如果简单地计算试卷的重复率，可能会出现重复率较高的情况，但这种重复率是不准确的。对于该算法计算重复率应该采用题目＋序号的方式来衡量，不能单纯地采用题目作为重复率的衡量指标。

设S 表示一套试卷题目总数，xi表示一套试卷中的任意一道试题，其中1≤i≤S，N 表示解空间大小，函数f（xi）表示试题xi在解空间中出现的次数，则在解空间中一套试卷的重复率计算如式（1）：

设M 表示解空间中不同试题的个数，xj表示解空间中的任意一道试题，其中1≤j≤M，函数f（xj）表示试题xj在解空间中出现的次数，则在解空间中所有试卷的重复率计算如式（2）：

如果计算重复率应该采用题目＋序号的方式来计算，设函数f（xi，index）表示试题xi在解空间中任意一套试卷中index 位置出现的次数，则在解空间中一套试卷的重复率计算如式（3），所有试卷的重复率计算如式（4）：

由于改进回溯试探组卷算法重复率可能较高，需对算法再进一步改进。可以采用随机组合H 解的方式将算法1 过程中的第6 步的一个解求出其他解写入解空间，其中，H<

2 算法试验分析

本文所述回溯试探组卷算法用于B/S 结构的OJ系统中，决定B/S 结构系统运行速度的主要是服务器的性能，试验用服务器基本配置如下页表1 所示。

表1 服务器软硬件配置

组卷试验分别针对3 种规模大小区别较大的题库进行组卷，采用相同的试题结构、试卷结构分别对随机抽取法、遗传算法、传统回溯试探法及改进的回溯试探法进行试验。试题模型包括试题编号、试题内容、参考答案、章节、难度、出题人等字段，如表2 所示。

表2 试题模型

每套试卷100 分，由各种类型的题目组成，如表3 所示。组卷要求难度系数0.45～0.55，试题能覆盖各章节。

表3 试卷结构

试验使用《面向对象程序设计》课程题库，该试题库包括单项选择题2 000 题、多项选择题、填空题、判断题各1 000 题，共5 000 题。利用OJ 系统对两个班级进行《面向对象程序设计》课程考试，需要组100 套试卷，分别采用随机抽取法、遗传算法、传统回溯试探法、改进回溯试探法进行组卷试验，试验结果如表4 所示。

表4 4 种算法在《面向对象程序设计》题库中组卷试验结果比较

通过式（4）对4 种算法组成的100 套试卷计算重复率，结果如表5 所示。

表5 4 种算法组卷试验结果重复率比较

从结果可以看出，改进回溯试探法相对于其他算法重复率略高，但已在一个可以满足基本要求的范围内了。

同样的试验用于《高等数学》试题库，库题包含30 000 道试题，单项选择题12 000 题、多项选择题、填空题、判断题各4 000 题。组成的100 套试卷试验结果如表6 所示。

表6 4 种算法在《高等数学》题库中组卷试验结果比较

通过式（4）对4 种算法组成的100 套试卷计算重复率，结果如表7 所示。

表7 4 种算法组卷试验结果重复率比较

从结果可以看出，当试题库规模增大时，随机抽取法、遗传算法、传统回溯试探法平均组卷时间都有明显的增加，而重复率都有明显的降低，而改进回溯试探法的平均组卷时间和重复率相对变化较小。

同样的试验用于《嵌入式系统》试题库，该试题库题目数量2 000 题，单项选择题800 题、多项选择题、填空题、判断题各400 题。组成的100 套试卷试验结果如表8 所示。

表8 4 种算法在《嵌入式系统》题库中组卷试验结果比较

通过式（4）对4 种算法组成的100 套试卷计算重复率，结果如表9 所示。

表9 4 种算法组卷试验结果重复率比较

从结果可以看出，当试题库规模变小时，随机抽取法、遗传算法、传统回溯试探法平均组卷时间都有明显的减少，重复率明显升高，而改进回溯试探法的平均组卷时间和重复率相对变化较小。

3 结论

本文分析了随机抽取法、遗传算法、回溯试探法等几种常见组卷算法的机制，重点研究了回溯试探法，并针对回溯试探法平均组卷时间长、重复率高的问题，对回溯试探法进行了两次改进，首先是以一个问题解的全排列得到n！个解，即一次回溯试探搜索得多个解，其次，对计算重复率的算法进行了修正，将一个得n！个解变为一次随机得组合H个解，再去掉重复率较高的解，可有效地降低试卷重复率。根据试验结果可以看出，随机抽取法、遗传算法、传统回溯试探法平均组卷时间会随着题库规模的增加而明显增加，重复率会随着题库规模的增加而明显减少，而改进回溯试探法的平均组卷时间和重复率比较稳定。因此，可以得出，改进的回溯试探组卷算法适用于各种规模的题库。但需要注意的是，改进的回溯试探组卷算法是以一种修正的重复率算法计算重复率的，如果以传统的重复率算法计算重复率，可能会存在重复率较高的问题，如果多套试卷同时考试，则重复率高的问题可以忽略，因此，该算法适合于同时考试的情况。