張立忠 趙家宇 姜楠

摘要：針對(duì)計(jì)算機(jī)組卷中試題被重復(fù)抽取造成的執(zhí)行效率低問(wèn)題，提出了一種分段隨機(jī)組卷算法。采用雙向循環(huán)鏈表結(jié)構(gòu)表示隨機(jī)數(shù)的生成區(qū)間，通過(guò)已生成的隨機(jī)數(shù)和隨機(jī)步長(zhǎng)值確定下一個(gè)隨機(jī)數(shù)的獨(dú)立生成區(qū)間。初始生成區(qū)間利用保存試題編號(hào)的數(shù)組下標(biāo)集合獲得。實(shí)驗(yàn)結(jié)果表明了本算法的可行性。與傳統(tǒng)隨機(jī)組卷算法相比，該算法隨機(jī)選題時(shí)不需要頻繁訪問(wèn)題庫(kù)，并具有較高的執(zhí)行效率。

關(guān)鍵詞：分段隨機(jī)； 雙向循環(huán)鏈表；隨機(jī)數(shù)；組卷；生成區(qū)間

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2012）33-8021-05

在課程自動(dòng)化考核過(guò)程中，計(jì)算機(jī)自動(dòng)組卷是其中的一個(gè)重要功能。自動(dòng)組卷的實(shí)現(xiàn)多采用隨機(jī)選取法并結(jié)合回溯試探的方法。隨機(jī)選取法就是根據(jù)命題人提供的組卷指標(biāo)由計(jì)算機(jī)程序從題庫(kù)中隨機(jī)選擇一定數(shù)量的試題構(gòu)成試卷。在這樣的組卷過(guò)程中，由于試題的選取具有不確定性，通常利用回溯試探方法解決試題被重復(fù)抽取的問(wèn)題。這種方法在題庫(kù)中題量較多或組卷數(shù)量較大的情況下，耗費(fèi)時(shí)間長(zhǎng)，組卷成功率不高。

采用分段隨機(jī)抽選法[1]和集合隨機(jī)抽選法[2-3]將題庫(kù)空間分段，通過(guò)縮小試題搜索的匹配范圍可提高組卷效率和成功率，但這些組卷方法依賴試題數(shù)據(jù)庫(kù)結(jié)構(gòu)上的支持，尚未克服試題被重復(fù)抽取的缺陷。此外，基于遺傳算法和模擬退火算法的組卷方法[4-5]對(duì)內(nèi)存占用量大，運(yùn)行時(shí)間長(zhǎng)[6]。另有研究發(fā)現(xiàn)，雖然在題庫(kù)中設(shè)置試題選中標(biāo)識(shí)[7-8]可避免試題被重復(fù)抽取，但需長(zhǎng)時(shí)間訪問(wèn)題庫(kù)，增加了系統(tǒng)負(fù)擔(dān)。

針對(duì)上述問(wèn)題，該文提出一種新的隨機(jī)組卷算法。采用雙向循環(huán)鏈表結(jié)構(gòu)表示隨機(jī)數(shù)的生成區(qū)間。通過(guò)動(dòng)態(tài)界定隨機(jī)生成區(qū)間從根本上解決試題被重復(fù)抽取的難題。整個(gè)組卷過(guò)程不需要頻繁訪問(wèn)數(shù)據(jù)庫(kù)。實(shí)驗(yàn)測(cè)試結(jié)果表明了該算法是可行的。

1 算法描述

1.1 傳統(tǒng)隨機(jī)組卷算法[3]

傳統(tǒng)隨機(jī)組卷算法是利用隨機(jī)函數(shù)在試題庫(kù)中抽取符合要求的試題組成試卷，其過(guò)程是：生成一個(gè)不重復(fù)的隨機(jī)數(shù)之后，以該隨機(jī)數(shù)為試題編號(hào)到題庫(kù)中選取試題，如果試題庫(kù)中不存在以該隨機(jī)數(shù)為試題編號(hào)的題目，則需要重新生成一個(gè)隨機(jī)數(shù)繼續(xù)選取試題。如果仍然找不到新隨機(jī)數(shù)所對(duì)應(yīng)的題目則必須再生成新的隨機(jī)數(shù)，而且每次嘗試都必須通過(guò)訪問(wèn)數(shù)據(jù)庫(kù)來(lái)確定是否成功，反復(fù)調(diào)用隨機(jī)函數(shù)的時(shí)間、進(jìn)行比較的時(shí)間以及多次訪問(wèn)數(shù)據(jù)庫(kù)的時(shí)間等累加起來(lái)，使得程序的效率大為降低。

1.2 分段隨機(jī)組卷算法

為了解決傳統(tǒng)隨機(jī)組卷算法反復(fù)地回溯匹配的問(wèn)題，需要考慮的是如何縮小搜尋匹配的范圍以及隨機(jī)數(shù)的非重復(fù)生成。任何組卷方法都是從試題庫(kù)中按照一定的組卷指標(biāo)和規(guī)則選取出指定數(shù)量的試題構(gòu)成試卷?；谶@個(gè)思想，將計(jì)算機(jī)自動(dòng)組卷分成兩步：第一步依據(jù)組卷指標(biāo)篩選出候選試題，這個(gè)操作可借助于SQL語(yǔ)句完成；第二步從候選試題中隨機(jī)抽取指定數(shù)量的試題，這一步是本算法的重點(diǎn)。

該文提出的分段隨機(jī)組卷算法是在候選題庫(kù)空間分段抽取試題，隨機(jī)確定每一次抽題范圍，且每次抽題范圍相互獨(dú)立；每段只隨機(jī)選取一題，以便提高組卷效率。這里我們利用一個(gè)雙向循環(huán)鏈表結(jié)構(gòu)表示隨機(jī)數(shù)的生成區(qū)間，并通過(guò)當(dāng)前隨機(jī)數(shù)和隨機(jī)步長(zhǎng)值隨機(jī)確定下一個(gè)隨機(jī)數(shù)的獨(dú)立生成區(qū)間，使試題的重復(fù)抽取得以避免。

1.2.1 隨機(jī)數(shù)的生成

候選題庫(kù)的更新會(huì)影響試題編號(hào)的連續(xù)性，通過(guò)在試題庫(kù)表中增加“隨機(jī)數(shù)”字段可保證隨機(jī)數(shù)產(chǎn)生區(qū)間的有效性[1-3]。這樣做增加了數(shù)據(jù)庫(kù)的存儲(chǔ)及維護(hù)負(fù)擔(dān)。該文用數(shù)組保存候選試題編號(hào)，并用數(shù)組下標(biāo)集合作為隨機(jī)數(shù)產(chǎn)生區(qū)間。隨機(jī)數(shù)Rnd的生成公式：

在公式（1）中，Random為系統(tǒng)內(nèi)部的隨機(jī)函數(shù)，可產(chǎn)生0至1之間的隨機(jī)小數(shù)。Start和Last分別表示數(shù)組下標(biāo)的起止邊界值。[…]為遵循四舍五入規(guī)則的取整運(yùn)算。顯然，[Rnd∈[Start，Last]]。

1.2.2 獨(dú)立隨機(jī)區(qū)間的生成

根據(jù)公式（1）可知，隨機(jī)數(shù)的產(chǎn)生依賴于區(qū)間[[Start，Last]]。為了避免產(chǎn)生重復(fù)的隨機(jī)數(shù)，根本的解決方法是為每個(gè)隨機(jī)數(shù)提供獨(dú)立的生成區(qū)間，即區(qū)間端點(diǎn)Start和Last的值在每個(gè)隨機(jī)數(shù)生成之前應(yīng)做相應(yīng)的改變。這種改變與當(dāng)前已生成的隨機(jī)數(shù)Rnd相關(guān)，如公式（2）。

[Rnd<（Last-Start）/2] （2）

公式（2）成立表示Rnd代表的點(diǎn)位于當(dāng)前區(qū)間的左半部分，則在[[Start，Last]]的左半?yún)^(qū)間為下一個(gè)隨機(jī)數(shù)尋找一個(gè)隨機(jī)生成區(qū)間，否則在[[Start，Last]]的右半?yún)^(qū)間尋找一個(gè)隨機(jī)生成區(qū)間。這需要由公式（3）生成一個(gè)隨機(jī)步長(zhǎng)值p。

[p=Random×i，1i Rnum] （3）

公式（2）中的Rnum表示隨機(jī)數(shù)的數(shù)目，即抽取試題的個(gè)數(shù)。[…]的含義同公式（1）。隨機(jī)數(shù)的產(chǎn)生區(qū)間狀態(tài)采用雙向循環(huán)鏈表表示，其結(jié)點(diǎn)結(jié)構(gòu)如圖1所示。

在圖1的結(jié)點(diǎn)結(jié)構(gòu)中，num表示用于存儲(chǔ)隨機(jī)數(shù)的數(shù)據(jù)域，front和follow代表指針型數(shù)據(jù)域，分別指向當(dāng)前結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)。獨(dú)立隨機(jī)區(qū)間的生成步驟如下：

1）生成區(qū)間首部Bm和尾部Lm兩個(gè)初始邊界結(jié)點(diǎn)，然后令Bm.num=Start-1，Lm.num=Last+1， Bm.front=Lm，Bm.follow=Lm，Lm.front=Bm，Lm.follow=Bm。

2）將Last =Lm.num-1，Start =Bm.num+1代入公式（1），把生成的隨機(jī)數(shù)Rnd作為結(jié)點(diǎn)Store的數(shù)據(jù)域，同時(shí)將Store插入到Bm和Lm之間。

3）由公式（3）生成隨機(jī)步長(zhǎng)值p。根據(jù)公式（2）判斷下一個(gè)隨機(jī)數(shù)的產(chǎn)生范圍。如果公式（2）成立，則不斷移動(dòng)Store指針指向其前驅(qū)結(jié)點(diǎn)；否則不斷移動(dòng)Store指針指向其后繼結(jié)點(diǎn)。移動(dòng)次數(shù)均為p次。

4）無(wú)效生成區(qū)間處理及新隨機(jī)區(qū)間的生成：如果Store.numLast成立，不斷移動(dòng)Store指針指向其前驅(qū)結(jié)點(diǎn)，直到Store.numLast均不成立時(shí)為止。然后繼續(xù)判斷，如果Store.num-1>Store.front.num成立，修改隨機(jī)區(qū)間的起止邊界，即令起始結(jié)點(diǎn)指針Bm指向Store的前驅(qū)結(jié)點(diǎn)，終止結(jié)點(diǎn)指針Lm指向當(dāng)前Store結(jié)點(diǎn)；如果Store.num+1

5）重復(fù)步驟（2）-（4），直到產(chǎn)生Rnum個(gè)隨機(jī)區(qū)間為止。

1.2.3 算法實(shí)現(xiàn)

將已生成的隨機(jī)數(shù)Rnd以Store結(jié)點(diǎn)的形式插入到一個(gè)雙向循環(huán)鏈表中，并從當(dāng)前Store結(jié)點(diǎn)出發(fā)，根據(jù)動(dòng)態(tài)生成的隨機(jī)步長(zhǎng)值p為下一個(gè)隨機(jī)數(shù)的產(chǎn)生界定一個(gè)獨(dú)立隨機(jī)區(qū)間，從而使得生成的每個(gè)隨機(jī)數(shù)互不重復(fù)，直到生成Rnum個(gè)隨機(jī)數(shù)為止。分段隨機(jī)組卷算法過(guò)程rd的實(shí)現(xiàn)過(guò)程如下：

程序結(jié)束

2 實(shí)驗(yàn)結(jié)果與分析

硬件環(huán)境：Intel 雙核1.73 GHz CPU和768M內(nèi)存。仿真測(cè)試是在候選題庫(kù)中有足夠符合條件和數(shù)量試題的前提下進(jìn)行。

測(cè)試了分段隨機(jī)算法抽取不同數(shù)目試題的組卷時(shí)間。保存試題編號(hào)的數(shù)組下標(biāo)Start=1，Last=10000。抽題數(shù)目Rnum分別取100，200，……，1000。圖2的實(shí)驗(yàn)結(jié)果表明隨著被抽取試題數(shù)量的增加，組卷時(shí)間呈現(xiàn)小幅度的線性增長(zhǎng)趨勢(shì)。這表明本算法具有較好的穩(wěn)定性和實(shí)用性。

對(duì)傳統(tǒng)隨機(jī)算法與分段隨機(jī)算法的組卷執(zhí)行效率進(jìn)行了測(cè)試。保存試題編號(hào)的數(shù)組下標(biāo)Start=1，Last分別取1000，2000，……，9000。抽題數(shù)目Rnum=50。圖3的實(shí)驗(yàn)結(jié)果表明，兩種算法在計(jì)算機(jī)組卷中所需的時(shí)間隨著題量的加大差距不大，但對(duì)同等規(guī)模的題庫(kù)，分段隨機(jī)算法的組卷時(shí)間稍小于傳統(tǒng)隨機(jī)算法。這是因?yàn)榉侄坞S機(jī)算法的時(shí)間消耗主要在獨(dú)立隨機(jī)區(qū)間的生成上，基于這些不斷變化的隨機(jī)區(qū)間即可生成互不重復(fù)的隨機(jī)數(shù)，而傳統(tǒng)隨機(jī)算法的時(shí)間主要消耗在隨機(jī)數(shù)的對(duì)比上，這個(gè)對(duì)比操作通常需要頻繁訪問(wèn)數(shù)據(jù)庫(kù)或者存儲(chǔ)試題編號(hào)的整個(gè)數(shù)組空間。

從圖3還可以發(fā)現(xiàn)，在抽取試題數(shù)目不變的情況下，分段隨機(jī)算法的消耗時(shí)間并未隨著試題數(shù)量的增加而顯著增大。這是因?yàn)殡S機(jī)數(shù)及隨機(jī)區(qū)間生成具有“隨機(jī)性”，即不確定性。這種不確定性使得獨(dú)立隨機(jī)區(qū)間生成的時(shí)間消耗不會(huì)呈現(xiàn)出一定的規(guī)律性，從而體現(xiàn)出分段隨機(jī)組卷算法的穩(wěn)定性。

3 結(jié)束語(yǔ)

該文提出的分段隨機(jī)組卷算法其核心思想是為每個(gè)隨機(jī)數(shù)提供相互獨(dú)立的生成區(qū)間，從根本上解決了組卷過(guò)程中試題被重復(fù)抽取的問(wèn)題，提高了組卷效率和質(zhì)量。實(shí)驗(yàn)結(jié)果表明本算法運(yùn)行穩(wěn)定，可靠性好。與傳統(tǒng)隨機(jī)組卷算法相比，分段隨機(jī)組卷算法對(duì)試題數(shù)據(jù)庫(kù)依賴性較弱，并具有較高的執(zhí)行效率。

參考文獻(xiàn)：

[1] 金漢均，鄭世玨，吳明武.分段隨機(jī)抽選法在智能組卷中的研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2003，20（9）：102-103，126.

[2] 王萌，金漢均，王曉榮.集合隨機(jī)抽選法在智能組卷中的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（19）：3583-3585.

[3] 丁庶煒，閆宏印，王世兵.基于集合隨機(jī)抽選法的智能組卷的研究與應(yīng)用[J].電腦開(kāi)發(fā)與應(yīng)用，2010，23（5）：10-11.

[4] 李霞婷，宋榮.改進(jìn)型遺傳算法在組卷系統(tǒng)中的研究與設(shè)計(jì)[J].電腦知識(shí)與技術(shù)，2011，7（20）：4947-4948.

[5] 陳瑛琦，趙蕾，鄧林.基于模擬退火遺傳算法的自動(dòng)組卷系統(tǒng)的研究[J].電腦知識(shí)與技術(shù)，2010，6（11）：2719-2720.

[6] 胡楠，謝政權(quán).基于混合求解算法的智能組卷研究[J].科學(xué)技術(shù)與工程，2009（13）：3642-3645，3651.

[7] 李目海.組卷中的隨機(jī)抽取算法分析與實(shí)現(xiàn)[J].棗莊學(xué)院學(xué)報(bào)，2007，24（2）：39-41.

[8] 莊越，黃君羨.基于知識(shí)點(diǎn)和改進(jìn)隨機(jī)抽取算法的智能組卷方案研究[J].計(jì)算機(jī)與數(shù)字工程，2009，37（6）：16-18，56.