一種改進(jìn)的回溯試探組卷算法*

李 川，楊俊清，王奕豪，張少茹

（1.西安航空學(xué)院計(jì)算機(jī)學(xué)院，西安 710077；2.西安交通大學(xué)醫(yī)學(xué)部，西安 710061）

0 引言

測評是現(xiàn)代教育教學(xué)中，考察學(xué)生知識掌握程度的一種有效方式［1］。在線測評與傳統(tǒng)紙質(zhì)試卷測評的優(yōu)勢是方便、高效、節(jié)約資源等，在線測評系統(tǒng)中有一個(gè)重要的問題——組卷，組卷是指按照給定的組卷約束條件從試題庫中選取一定數(shù)量的試題組成若干套試卷的過程［2-3］，這樣組出的試卷不但要滿足指定的題型要求，而且要使試卷中各題目的難度配比能滿足試卷的平均難度，同時(shí)又使試卷中出現(xiàn)的知識點(diǎn)不重復(fù)。試題庫的結(jié)構(gòu)和題目數(shù)量、質(zhì)量以及所使用的組卷算法的好壞，將直接決定著組卷系統(tǒng)所組成試卷的質(zhì)量。組卷算法將直接影響試卷的知識點(diǎn)覆蓋率、試卷難易及組卷成功比等問題，進(jìn)而影響到考試系統(tǒng)的普及推廣。

利用組卷算法生成科學(xué)、合理的試卷且組卷效率高是衡量一個(gè)組卷算法優(yōu)劣的標(biāo)準(zhǔn)，目前常用的組卷算法主要有隨機(jī)選取法、回溯試探法、遺傳算法等［4］。

隨機(jī)選取法根據(jù)條件對題庫進(jìn)行分類和規(guī)整，挑選符合條件的題目組卷。該算法設(shè)計(jì)簡單，在一些小型在線考試系統(tǒng)中應(yīng)用較多，但算法模式固定，組卷成功率低，試題覆蓋率低?；厮菰囂椒ㄊ墙⒃陔S機(jī)選取算法基礎(chǔ)上的［5］，隨機(jī)選取算法的缺點(diǎn)是組卷成功率低［6］，回溯性試探法對此進(jìn)行了改進(jìn)，該算法將每次隨機(jī)選取的結(jié)果記錄下來，當(dāng)組卷不成功時(shí)回退到上一步，繼續(xù)試探，直到組成試卷成功［7］。該算法缺點(diǎn)是組卷過程繁瑣，耗時(shí)量大，效率和組卷質(zhì)量都不高。遺傳算法是通過類比的方式，模擬生物在大自然中的一種繁衍，變異的一個(gè)過程［8］，將這種類比的結(jié)果應(yīng)用到計(jì)算機(jī)模型上。繁衍是通過自然環(huán)境下對自己的子孫后代進(jìn)行篩選，變異則是依照適應(yīng)度函數(shù)求解最優(yōu)解的一個(gè)過程［9］。透過生物的表現(xiàn)型去找尋其內(nèi)在基因編碼的規(guī)律，這樣才能總結(jié)出一定的經(jīng)驗(yàn)去完成由表現(xiàn)型到遺傳編碼的對應(yīng)關(guān)系，將這種對應(yīng)關(guān)系簡化為二進(jìn)制編碼的關(guān)系，找尋到初代的生物種群，然后模擬后代在生存環(huán)境中的遺傳和變異的規(guī)律［10-11］。遺傳算法的缺點(diǎn)是過程較為繁瑣，實(shí)現(xiàn)困難。

以上這些算法都能實(shí)現(xiàn)組卷，但各有優(yōu)缺點(diǎn)，也都存在一些適應(yīng)情況，本文研究設(shè)計(jì)一種改進(jìn)的回溯試探法組卷算法模型，以解決回溯試探組卷算法效率低、重復(fù)率高的問題。

1 改進(jìn)的回溯試探組卷算法

對于一個(gè)回溯試探問題Q，要有如下理論：

定義1：定義狀態(tài)空間E={（x1，x2，……，xn）|xi∈si，i=1，2，……，n}，其中（x1，x2，……，xn）是一個(gè)n 元組，其中si是xi的定義域，且|si|有限［12］；

定義2：定義一個(gè)約束集D={di| i=1，2，……，m}，其中，di是對xi的一個(gè)約束［13］；

定理1：如果狀態(tài)空間E 中存在一個(gè)n 元組滿足D 的全部約束，稱該n 元組為問題Q 的一個(gè)解。

定理2：如果一個(gè)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）的一個(gè)真子集，j

由推理1 可知，對于一個(gè)回溯試探問題Q，如果某個(gè)j 元組（x1，x2，……，xj）不是問題Q 的解，且j 元組（x1，x2，……，xj）是i 元組（x1，x2，……，xi）的一個(gè)真子集，那么對于任意i 元組都不是問題Q 的解，因而對i 元組（x1，x2，……，xi）中除去子集j 元組（x1，x2，……，xj）的剩余元素（xj+1，……，xi）就不必再測試，這減少了測試的次數(shù)，提高了算法的效率。

回溯法利用上述理論，在狀態(tài)空間E 中遍歷一個(gè)n 元組（x1，x2，……，xn），如果滿足D 的所有約束，則該n 元組是問題Q 一個(gè)解；否則，如果在檢測到xi時(shí)不能滿足約束集D 中的部分約束，則以i 元組（x1，x2，……，xi）的所有n 元組（x1，x2，……，xn）都不是問題Q 的解，回溯到狀態(tài)xi-1，繼續(xù)遍歷狀態(tài)空間E 中的其他n 元組，直至遍歷E 結(jié)束?？梢钥闯龌厮菰囂浇M卷算法是一種DFS 算法［14］，根據(jù)組卷約束條件深度搜索，直到試卷生成為止。如果試探到某一步時(shí)，發(fā)現(xiàn)組卷不成功，就回溯到上一步繼續(xù)試探。該算法是通過試探和糾錯來尋找解決方案的，回溯試探算法的過程如圖1 所示。

圖1 回溯試探法流程圖

在組卷過程中，解空間就是在試題庫中選取n個(gè)試題的集合，當(dāng)試題庫規(guī)模很大時(shí)，解空間樹也隨之很大，一般的窮舉算法時(shí)間復(fù)雜度會很大，從回溯試探法的流程中可以看出，可以通過縮小解空間樹的大小提高回溯試探法的效率，根據(jù)不同的組卷應(yīng)用情況，設(shè)計(jì)方案如下。

定義3：如果n 元組（x1，x2，……，xn）中的分量xi（0≤i≤n）之間是有序的，則稱n 元組為有序n 元組，反之稱為無序n 元組。

定理3：有序n 元組（x1，x2，……，xn）構(gòu)成的狀態(tài)空間大小為n?。?5］。

定理4：無序n 元組（x1，x2，……，xn）構(gòu)成的狀態(tài)空間大小為1。

一般組卷過程中，如果兩套試卷中只要出現(xiàn)相同的題目，而不管題目的序號是否相同，就認(rèn)為存在重復(fù)試題，這種情況下組成的試卷質(zhì)量較高，但可能存在組卷失?。}庫規(guī)模不足等原因）、組卷效率低等問題。而在實(shí)際應(yīng)用中，例如有些考試試卷題目相同，但題序不同組成了AB 卷，這樣既保證了組卷效率，又保證了試題質(zhì)量及防止作弊。

定理5：如果一個(gè)n 元組（x1，x2，……，xn），滿足D 的所有約束，那么該n 元組就是問題Q 的一個(gè)解，而x1，x2，……，xn的任意排列組合的n 元組都是問題Q 的解。

推論2：由定理3、定理5 可知，當(dāng)回溯探測出一個(gè)n 元組（x1，x2，……，xn）是問題Q 的一個(gè)解，即可得出問題Q 的n！個(gè)解。

基于上述理論的組卷過程中如算法1：

在回溯試探算法中，提高算法效率的一種重要手段是通過剪枝減少多余或無效的搜索，常用的剪枝函數(shù)，一種是使用約束條件函數(shù)剪去不滿足約束條件的狀態(tài)集，另一種是采用限定函數(shù)剪去得不到最優(yōu)解的狀態(tài)集。

本文所述的回溯試探組卷算法采用了上述兩種剪枝函數(shù)，減少了回溯試探的次數(shù)，但生成問題一個(gè)解的其他全排列解的遞歸過程，即減少開銷的同時(shí)又增加了額外的開銷，相比較而言，減少的開銷>>額外增加的開銷，總之可以有效地降低算法的時(shí)間復(fù)雜度。

這種算法組成的試卷，如果簡單地計(jì)算試卷的重復(fù)率，可能會出現(xiàn)重復(fù)率較高的情況，但這種重復(fù)率是不準(zhǔn)確的。對于該算法計(jì)算重復(fù)率應(yīng)該采用題目＋序號的方式來衡量，不能單純地采用題目作為重復(fù)率的衡量指標(biāo)。

設(shè)S 表示一套試卷題目總數(shù)，xi表示一套試卷中的任意一道試題，其中1≤i≤S，N 表示解空間大小，函數(shù)f（xi）表示試題xi在解空間中出現(xiàn)的次數(shù)，則在解空間中一套試卷的重復(fù)率計(jì)算如式（1）：

設(shè)M 表示解空間中不同試題的個(gè)數(shù)，xj表示解空間中的任意一道試題，其中1≤j≤M，函數(shù)f（xj）表示試題xj在解空間中出現(xiàn)的次數(shù)，則在解空間中所有試卷的重復(fù)率計(jì)算如式（2）：

如果計(jì)算重復(fù)率應(yīng)該采用題目＋序號的方式來計(jì)算，設(shè)函數(shù)f（xi，index）表示試題xi在解空間中任意一套試卷中index 位置出現(xiàn)的次數(shù)，則在解空間中一套試卷的重復(fù)率計(jì)算如式（3），所有試卷的重復(fù)率計(jì)算如式（4）：

由于改進(jìn)回溯試探組卷算法重復(fù)率可能較高，需對算法再進(jìn)一步改進(jìn)?？梢圆捎秒S機(jī)組合H 解的方式將算法1 過程中的第6 步的一個(gè)解求出其他解寫入解空間，其中，H<

2 算法試驗(yàn)分析

本文所述回溯試探組卷算法用于B/S 結(jié)構(gòu)的OJ系統(tǒng)中，決定B/S 結(jié)構(gòu)系統(tǒng)運(yùn)行速度的主要是服務(wù)器的性能，試驗(yàn)用服務(wù)器基本配置如下頁表1 所示。

表1 服務(wù)器軟硬件配置

組卷試驗(yàn)分別針對3 種規(guī)模大小區(qū)別較大的題庫進(jìn)行組卷，采用相同的試題結(jié)構(gòu)、試卷結(jié)構(gòu)分別對隨機(jī)抽取法、遺傳算法、傳統(tǒng)回溯試探法及改進(jìn)的回溯試探法進(jìn)行試驗(yàn)。試題模型包括試題編號、試題內(nèi)容、參考答案、章節(jié)、難度、出題人等字段，如表2 所示。

表2 試題模型

每套試卷100 分，由各種類型的題目組成，如表3 所示。組卷要求難度系數(shù)0.45～0.55，試題能覆蓋各章節(jié)。

表3 試卷結(jié)構(gòu)

試驗(yàn)使用《面向?qū)ο蟪绦蛟O(shè)計(jì)》課程題庫，該試題庫包括單項(xiàng)選擇題2 000 題、多項(xiàng)選擇題、填空題、判斷題各1 000 題，共5 000 題。利用OJ 系統(tǒng)對兩個(gè)班級進(jìn)行《面向?qū)ο蟪绦蛟O(shè)計(jì)》課程考試，需要組100 套試卷，分別采用隨機(jī)抽取法、遺傳算法、傳統(tǒng)回溯試探法、改進(jìn)回溯試探法進(jìn)行組卷試驗(yàn)，試驗(yàn)結(jié)果如表4 所示。

表4 4 種算法在《面向?qū)ο蟪绦蛟O(shè)計(jì)》題庫中組卷試驗(yàn)結(jié)果比較

通過式（4）對4 種算法組成的100 套試卷計(jì)算重復(fù)率，結(jié)果如表5 所示。

表5 4 種算法組卷試驗(yàn)結(jié)果重復(fù)率比較

從結(jié)果可以看出，改進(jìn)回溯試探法相對于其他算法重復(fù)率略高，但已在一個(gè)可以滿足基本要求的范圍內(nèi)了。

同樣的試驗(yàn)用于《高等數(shù)學(xué)》試題庫，庫題包含30 000 道試題，單項(xiàng)選擇題12 000 題、多項(xiàng)選擇題、填空題、判斷題各4 000 題。組成的100 套試卷試驗(yàn)結(jié)果如表6 所示。

表6 4 種算法在《高等數(shù)學(xué)》題庫中組卷試驗(yàn)結(jié)果比較

通過式（4）對4 種算法組成的100 套試卷計(jì)算重復(fù)率，結(jié)果如表7 所示。

表7 4 種算法組卷試驗(yàn)結(jié)果重復(fù)率比較

從結(jié)果可以看出，當(dāng)試題庫規(guī)模增大時(shí)，隨機(jī)抽取法、遺傳算法、傳統(tǒng)回溯試探法平均組卷時(shí)間都有明顯的增加，而重復(fù)率都有明顯的降低，而改進(jìn)回溯試探法的平均組卷時(shí)間和重復(fù)率相對變化較小。

同樣的試驗(yàn)用于《嵌入式系統(tǒng)》試題庫，該試題庫題目數(shù)量2 000 題，單項(xiàng)選擇題800 題、多項(xiàng)選擇題、填空題、判斷題各400 題。組成的100 套試卷試驗(yàn)結(jié)果如表8 所示。

表8 4 種算法在《嵌入式系統(tǒng)》題庫中組卷試驗(yàn)結(jié)果比較

通過式（4）對4 種算法組成的100 套試卷計(jì)算重復(fù)率，結(jié)果如表9 所示。

表9 4 種算法組卷試驗(yàn)結(jié)果重復(fù)率比較

從結(jié)果可以看出，當(dāng)試題庫規(guī)模變小時(shí)，隨機(jī)抽取法、遺傳算法、傳統(tǒng)回溯試探法平均組卷時(shí)間都有明顯的減少，重復(fù)率明顯升高，而改進(jìn)回溯試探法的平均組卷時(shí)間和重復(fù)率相對變化較小。

3 結(jié)論

本文分析了隨機(jī)抽取法、遺傳算法、回溯試探法等幾種常見組卷算法的機(jī)制，重點(diǎn)研究了回溯試探法，并針對回溯試探法平均組卷時(shí)間長、重復(fù)率高的問題，對回溯試探法進(jìn)行了兩次改進(jìn)，首先是以一個(gè)問題解的全排列得到n！個(gè)解，即一次回溯試探搜索得多個(gè)解，其次，對計(jì)算重復(fù)率的算法進(jìn)行了修正，將一個(gè)得n！個(gè)解變?yōu)橐淮坞S機(jī)得組合H個(gè)解，再去掉重復(fù)率較高的解，可有效地降低試卷重復(fù)率。根據(jù)試驗(yàn)結(jié)果可以看出，隨機(jī)抽取法、遺傳算法、傳統(tǒng)回溯試探法平均組卷時(shí)間會隨著題庫規(guī)模的增加而明顯增加，重復(fù)率會隨著題庫規(guī)模的增加而明顯減少，而改進(jìn)回溯試探法的平均組卷時(shí)間和重復(fù)率比較穩(wěn)定。因此，可以得出，改進(jìn)的回溯試探組卷算法適用于各種規(guī)模的題庫。但需要注意的是，改進(jìn)的回溯試探組卷算法是以一種修正的重復(fù)率算法計(jì)算重復(fù)率的，如果以傳統(tǒng)的重復(fù)率算法計(jì)算重復(fù)率，可能會存在重復(fù)率較高的問題，如果多套試卷同時(shí)考試，則重復(fù)率高的問題可以忽略，因此，該算法適合于同時(shí)考試的情況。